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

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

楊京翰(Ching-Han Yang)

指導教授 ： 史青林

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

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

摘要

令圖G包含點和邊,ℓ為將圖G的點集合和邊集合對應到一個整數集{0,...,λ}使得(1)相鄰的點不能標相同的數字,(2)相鄰的邊不能標相同的數字,(3)相連的點和邊標號數必須大於等於2,則圖G稱為一個(2,1)-全標號。一個(2,1)-全標號圖G對應到整數集{0,...,λ}且λ為最小標號數則表示成λ^T_2(G)。
令n和k是正整數。如果圖包含點集合{u_1,...,u_n}和{v_1,...,v_n}; 邊集合{u_iu_(i+1)},{u_iv_i}和{v_iv_(i+k)},我們稱此種圖為廣義彼得森圖並表示成P(n,k)。
在此篇論文中, 我們把重點放在三正則圖的(2,1)-全標號中且在廣義彼得森圖得到一些結果。

關鍵字

全標號 ； 廣義彼得森圖

並列摘要

Let G = (V,E) be a graph. A (2,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 ℓ(x)≠ℓ(y), (ii) if e and f are adjacent edges then ℓ(e)≠ℓ(f), (iii) if an edge e is incident to a vertex x then |ℓ(x)-ℓ(e)|≧2. The minimum λ for which G has a (2,1)-total labeling into {0,...,λ} is denoted by λ^T_2(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_iu_(i+1), u_iv_i and v_iv_(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 cubic graphs and we obtain some results for the generalized Petersen graphs.

並列關鍵字

total labeling ； generalized Petersen graphs

參考文獻

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)-

labelling of graphs, Discrete Math. 220 (2000) 57-66.

[3] D. Chen, W. Wang, (2,1)-Total labelling of outerplanar graphs, Discrete