均衡完全三分圖的(p，1）-全標號

On (p,1)-Total Labelings of Balanced Complete Tripartite Graphs

黃邦傑(Huang-Bang Jie)

指導教授 ： 史青林

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

https://doi.org/10.6840/cycu201400400

摘要

令G=(V,E)是一個圖，如果 為將圖G的點集合和邊集合對應到一個整數集{0,…,λ}的函數使得(1)相鄰的點不能標記相同的整數，(2)相鄰的邊不能標記相同的整數，(3)相鄰的點和邊標號差值的絕對值必須大於等於 p，則稱 為圖G的一個(p,1)-全標號，其中p為正整數。在一個(p,1)-全標號中，兩個標記整數之間最大的差值稱為跨度。在圖G的(p,1)-全標號中，最小的跨度我們稱之為圖G的(p,1)-全標號數，以符號λ_p^T (G)表示之。
在這篇論文中，我們證明對所有的正整數 n ≥2 以及p≥1，λ_p^T (K_(n,n,n) )
≤2n+p+1 。此外, 我們證明如果p≥2n，則λ_p^T (K_(n,n,n) )=2n+p+1。

關鍵字

全標號 ； 均衡完全三分圖

並列摘要

Let G=(V,E) be a graph. A (p,1)-total labeling of G is a mapping from V∪E into {0,…, λ} for some integer λ such that : (i) if x and y are adjacent vertices, then ; (ii) if e and f are adjacent edges, then ; (iii) if an edge e is incident to a vertex x, then , where p is a positive integer. The span of a (p,1)-total labeling is the maximum difference between two labels. The (p,1)-total number of a graph G is the minimum span of a (p,1) -total labeling of G, denoted by λ_p^T (G).
In this thesis, we prove that for each integer n≥2, λ_p^T (K_(n,n,n) )≤2n+p+1. Moreover, if n is even or p≥2n then λ_p^T (K_(n,n,n) )=2n+p+1.

並列關鍵字

balanced complete tripartite graphs ； total labeling

參考文獻

[9] 楊京翰(J. H. Yang), 廣義彼得森圖的(2,1)-全標號, 中原大學應用數學系碩士論文, 201

[3] 林育君(Y. C. Lin), 廣義彼得森圖的(2,1)-全標號, 中原大學應用數學系碩士論文, 2011.

[4] 劉志華(C. H. Liu), 廣義彼得森圖的(2,1)-全標號, 中原大學應用數學系碩士論文, 2010.

[6] 彭彥碩(Y. S. Peng), on (p,1)-Total labelings of regular graphs,中原大學應用數學系碩士論文, 2011.

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