廣義彼得森圖的(2,1)-全標號

On (2,1)-total labeling of generalized Petersen graphs

劉志華(Chi-Hua Liu)

指導教授 ： 史青林

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

https://doi.org/10.6840/cycu201000202

摘要

(p,1)-全標號是一種將圖中的點集合與邊集合對應到整數集的函數，使得：(1)任兩個相鄰的點必須標不同的數字(2)任兩個相鄰邊必須標不同的數字，且(3)每一個邊與其端點間的標號差的絕對值必須大於等於p。一個(p,1)-全標號的生成數指的是圖中任兩標號間的最大差。而一個圖的所有(p,1)-全標號中的最小生成數則稱為(p,1)-全標號數，表示成λp,t(G)。
令n和k是正整數。如果圖包含點集合{v(1),...,v(n)}和{u(1)...,u(n)} ;以及邊u(i)u(i+1) ，u(i)v(i) 和v(i)v(i+k)，我們稱此種圖為廣義彼德森圖並表示成P(n,k)。
在此篇論文中，我們把重點放在廣義彼德森圖的(2,1)-全標號中，並證明對所有正整數n同餘0(mod 3)而言，λ2,T(P(n,k)=5， 當k不被3整除時。

關鍵字

全標號 ； 廣義彼得森圖

並列摘要

A (p,1)-total labeling of a graph G is to be an assignment of V(G)∪E(G) to integers such that: (i) any two adjacent vertices of G receive distinct integers, (ii) any two adjacent edges of G receive distinct integers, and (iii) 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 to be the (p,1)-total number and denoted by λp,T(G).

Let n and k be two positive integers. The graph with vertices {u(1),...u(n)} and {v(1),...,v(n)} and edges u(i)u(i+1),u(i)v(i), and v(i)v(i+k), where addition is modulo n is called generalized Petersen graph and denoted by P(n,k).

In this thesis, we mainly focus on the (2,1)-total labeling of the generalized Petersen graph, and we show that for each positive integer n≡0 (mod 3), λ2,T(P(n,k))=5 if k is not divisible by 3.

並列關鍵字

generalized Petersen graph ； total labeling

參考文獻

[1] F. Bazzaro, M. Montassier, A. Raspaud, -Total labeling of planar graphs with large girth and high maximum degree, Discrete Math. 307 (2007) 2141-2151.

[2] G. J. Chang, W. T. Ke, D. Kuo, D. D. F. Liu, R. K. Yeh, On -labeling of graphs, Discrete Math. 220 (2000) 57-66.

[3] D. Chen, W. Wang, -Total labeling of outer planar graphs, Discrete Appl. Math. 155 (2007) 2585-2593.

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

[5] F. Havet and S. Thomass'e, Complexity of -total labeling.