正則圖之（ p，１）－全標號

On (p,1)-total labelings of regular graphs

曾韻維(Yun-Wei Tseng)

指導教授 ： 史青林

中原大學/理學院/應用數學研究所/碩士(2012年)

https://doi.org/10.6840/cycu201200646

摘要

令 G=(V,E) 為一個包含點集合V及邊集合E的圖，l為將圖G點集合和邊集合對應到一個整數集 {0,…,λ} 的函數使得相鄰的點不能標記相同的整數，相鄰的邊不能標記相同的整數，以及相鄰的點和邊標號差值的絕對值必須大於等於p則稱l為圖G的一個(p,1)-全標號。
在一個(p,1)-全標號中，兩個標記整數之間最大的差值稱為跨度。在圖G的(p,1)-全標號中，最小的跨度我們稱之為圖G的(p,1)-全標號數，以符號λ_p^T (G)表示之。
在這篇論文中，我們證明了對任一Δ-正則圖G以及每一個整數k≥4，如果p≥max{k+1,Δ}且G是Class 1，則χ(G)=k若且為若λ_p^T (G)=Δ+p+k-2.

關鍵字

(p 1)-全標號

並列摘要

Let G=(V,E) be a graph. A (p,1)-total labeling of G is a mapping form V(G)∪E(G) into {0,…,λ} for some integer λ such that any adjacent vertices of G are labeled with distinct integers, any two adjacent edges of G are labeled with distinct integers and a vertex and its incident edge receive integers that differ by at least p in absolute value.
The span of a (p,1)-total labeling is the maximum difference between two labels. The (p,1)-total number of a graph G is the minimum span of a (p,1)-total labeling of G, denoted by λ_p^T (G).
In this thesis, we prove that for each connected Δ-regular graph G and each integer k≥4, if p≥max{k+1,Δ} and G is Class 1, then
χ(G)=k if and only if λ_p^T (G)=Δ+p+k-2.

並列關鍵字

(p 1)-total labeling

參考文獻

[1]S. S. Adams, J. Cass and D. S. Troxell, An extension of the channel-assignment problem: L(2,1) - labelings of generalized Petersen graphs, Circuits and Systems I, Regular papers, IEEE Transactions on Vol.53, 5, 1101 - 1107, 2006.

[2]R. Broks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37, 194 - 197, 1941.

[4]F. C. Chi, On (2,1)-total labeling of generalized Petersen graphs, Master's thesis of Chung Yuan Christian University, 2011.

[5]J. R. Griggs and R. K. Yeh, Labeling graphs with a condition at distance two, SIAM J. Discrete Math. Vol.5, pp.585 - 595, 1992.

[6]F. Havet and M. L. Yu, (p,1)-Total Labeling of graphs, Discrete Math. 308, 496-513, 2008.