正則圖之(p,1)－全標號

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

彭彥碩(Yan-Shuo Peng)

指導教授 ： 史青林

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

https://doi.org/10.6840/CYCU.2011.00152

摘要

一個圖G的(p,1)–全標號是一個函數,它將圖G的點集與邊集對應到一個包含整數的集合,使得任兩相鄰的點必須標上不同的數字,任兩相鄰的邊必須標上不同的數字以及每個邊與其端點標號相差的絕對值必須大於等於p。一個(p,1)–全標號的生成數是指圖中任兩標號的差的最大值。而圖G 之所有(p,1)–全標號中的最小生成數稱為(p,1)–全標號數,以λ_p^T(G)表示。
在這篇論文中,我們證明下面兩個結果：
(1)對任一Δ–正則圖 ,如果p>=max{3,Δ},則G為二分圖若且為若 λ_p^T(G)=Δ+p；
(2)對任一Δ–正則圖 ,如果p>=max{4,Δ}且G是Class 1,則χ(G)=3若且為若λ_p^T(G)=Δ+p。

關鍵字

正則圖 ； 全標號

並列摘要

A (p,1)–total labeling of a graph G is an assignment of V(G)∪E(G) to integers such that any two 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 minimum span of a (p,1)–total labeling of G is called the (p,1)–total number and denoted by λ_p^T(G).
In this thesis, we prove the following two results:
(1) For each connected Δ–regular graph G, if p>=max{3,Δ}, then G is bipartite if and only if λ_p^T(G)=Δ+p.
(2) For each connected Δ–regular graph G, if p>=max{4,Δ} and G is Class 1, then χ(G)=3 if and only if λ_p^T(G)=Δ+p.

並列關鍵字

total labeling ； regular graph

參考文獻

5. References

[1] R. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37

(1941) 194-197.

[2] Gary Chartrand and Ping Zhang, Introduction to Graph Theory, Mcgraw-hill, New York, 2005.

[4] J. R. Griggs and R. K. Yeh, Labelling graphs with a condition at distance two, SIAM J. Discrete Math., 5 (1992) 586-595.