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

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

紀芳琪(FANG-CHI CHI)

指導教授 ： 史青林

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

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

摘要

(p,1)-全標號是一種將圖中的點集合與邊集合對應到整數集的函數,使得任兩個相鄰的點必須標不同的數字,任兩個相鄰的邊必須標不同的數字且每一個邊與其端點間的標號差的絕對值必須大於等於p。一個(p,1)-全標號的生成數指的是圖中任兩標號間的最大差。而一個圖的所有(p,1)-全標號中的最小生成數則稱為(p,1)-全標號數,表示成λ^T_P(G)。

令n和k是正整數。若一個圖包含點集合{u(1),...,u(n)}和{v(1),...,v(n)}以及邊集合{u(i)u(i+1)|i=1,2,...,n},{u(i)v(i)|i=1,2,...,n}和{v(i)v(i+k)|i=1,2,...,n;k

關鍵字

廣義彼得森圖 ； 全標號

並列摘要

A (p,1)- total labeling of G is an assignment of integers to V(G)∪E(G) such that any two adjacent vertices of G receive distinct integers, any two adjacent edges of G receive 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 λ^T_P(G).
Let n and k be two positive integers. The graph with vertex sets {u(1),...,u(n)} and {v(1),...,v(n)} and edge sets {u(i)u(i+1)|i=1,2,...,n},{u(i)v(i)|i=1,2,...,n} and {v(i)v(i+k)|i=1,2,...,n;k

並列關鍵字

generalized Petersen graph ； total labelings

參考文獻

[1] F. Bazzaro, M. Montassier and A. Raspaud, (d,1)-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 and R. K. Yen, On L(d,1)-labeling of graphs, Discrete Math. 220(2000) 57-66.

[3] D. Chen and W. Wang, (2,1)-Total labeling of outerplanar graphs, Discrete Appl. Math. 155 (2007)2585-2593.

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

[5] F. Havet and S. Thomass’e, Complexity of (p,1)-total labeling.