新優美圖的建構

Abstract

Ｇ＝（Ｖ，Ｅ）是一個有ｅ邊的圖形，圖Ｇ上的標籤（LABELLING ）是從頂點集合Ｖ 映到集合Ｎ＝｛１，２，……，ｅ＋１｝的１－１對映θ。對每一邊｛ｕ，ｖ｝，θ （ｕｖ）表示θ（ｕ）與θ（ｖ）差的絕對值，我們稱此θ（ｕｖ）為｛ｕ，ｖ｝的 重量（WEIGHT）。若圖Ｇ的所有邊上的重量完全相異，則稱此標籤為β－標籤（β－ LABELLING ）。若存在一整數ｘ，使得對每一邊｛ｕ，ｖ｝，滿足θ（ｕ）≦ｘ且θ （ｖ）＞ｘ或θ（ｕ）＞ｘ且θ（ｖ）≦ｘ，則稱此標籤為α－標籤（α－LABELLIN G ）。 一個兩部圖（BIPARTITE GRAPH ）就是一個能將頂點集合Ｖ分割成兩個子集合Ａ和Ｂ ，使得每一邊的兩頂點一在Ａ且一在Ｂ。若圖形Ｇ是一個連通的兩部圖而且｜Ａ｜＝ ｍ，｜Ｂ｜＝ｎ，則稱圖Ｇ是一（ｍ，ｎ）－圖。很顯然地，樹（TREE）是一個兩部 圖，一樹被稱為（ｍ，ｎ，θ）一樹若它是一個（ｍ，ｎ）－圖而且有一個α－標籤 θ。 在此篇論文裡，我們首先建構一些新的（ｍ，ｎ，θ）一樹，然後再建構一些具有α －標籤或β－標籤的圖形。