分裂圖的(2, 1)-全標號

On (2, 1)-total labelings of split graphs

許佳偉(Chia-Wei Hsu)

指導教授 ： 史青林

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

https://doi.org/10.6840/cycu201000206

摘要

(p,1)-全標號是一種將圖G中的點集合與邊集合對應到整數集的函數，使得：(1)任兩個相鄰的點必須標不同的數字(2)任兩個相鄰邊必須標不同的數字，且(3)每一個邊與其端點的標號差的絕對值必須大於等於p。一個(p,1)-全標號的生成數指的是圖中任兩標號間的差的最大值。而一個圖的所有(p,1)-全標號中的最小生成數則稱為(p, 1)-全標號數，表示成λT2(G)。
令G和H是兩個互斥圖，我們定義G和H的連結圖為圖G∨H=(V,E)，其中點集合V =V(G)∪V(H)以及邊集合E =E(G)∪E(H)∪{(u,v)|u∈V(G),v∈V(H)}。令Om是有m個點但沒有邊的圖，則我們稱Om∨Kn為分裂圖。
在這篇論文中,我們把研究重點放在分裂圖的(2,1)-全標號且得到一些結果。

關鍵字

全標號 ； 分裂圖

並列摘要

A (p,1)-total labeling of a graph G is to be an assignment of integers to V(G)∪E(G)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 a graph G is called the (p,1)-total number and denoted by λTp(G).
Let G and H be two disjoint graphs. The join of G and H is the graph G∨H=(V,E),where V=V(G)∪V(H)and E=E(G)∪E(H)∪{(u,v)|u∈V(G),v∈V(H)}.
Let Om be a graph with m vertices and no edges. Then we say the graph Om ∨ Kn to be a split graph.
In this thesis, we mainly focus on the (2,1)-total labeling of split graph and we obtain some results about it.

並列關鍵字

split graph ； total labeling

參考文獻

[1] F. Bazzaro, M. M3ontassier, A. Raspaud, (d,1)-total labelling 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 L(d,1)-labellings of graphs, Discrete Math. 220 (2000), 57-66.

McGraw-Hill, Inc, 1993.

[4] D. Chen, W. Wang, (2,1)-total labelling of outerplanar graphs, Discrete Appl.Math. 155 (2007), 2585-2593.

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