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

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

蔡政昊(Cheng-Hao Tsai)

指導教授 ： 史青林

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

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

摘要

中 文 摘 要
令G 是一個圖。一個G 的( p ,1 )全標號是一個函數指定整數到圖G的各個邊和點，使得圖G的任何相鄰點是不同的數字，圖G的任何相鄰邊是不同的數字，且一個點和它的相鄰邊之差的絕對值至少p。全標號的跨度是指兩個標號之間最大的差值。在G的所有( p ,1 )全標號中，最小的跨度稱為G的( p ,1 )全標數，符號寫作λ_P^T (G)。
在這篇論文中，首先我們證明了對於任一Class 2的△-正則圖G，如果p≥max｛χ+1 ,△｝，則λ_P^T (G)≥ △+p+χ-2。接著我們找出一些使得一個Class 2的△-正則圖G滿足其λ_P^T (G) =△+p+χ-2的充分條件。

關鍵字

全標號

並列摘要

Abstract
Let G be a graph. A ( p ,1 )-total labeling of G is an assignment of integers to each vertex and edge of G 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 of G is the maximum difference between two labels. The minimum span of ( p ,1 )-total labeling of G is called the ( p ,1 )-total number and denote by λ_P^T (G).
In this thesis, we first prove that for each Class 2 △-regular graph G if p≥max⁡{χ+1 ,△}, then λ_P^T (G) ≥ △+p+χ-2. Next, we find some sufficient conditions for a Class 2 △-regular graph G which has the property that if p≥max⁡{χ+1 ,△}, then λ_P^T (G)= △+p+χ-2.

並列關鍵字

Class2 ； 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.52,5, 1101 – 107,2006.

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

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

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

[7] Wolfram MathWorld on Internet