三正則圖的(2，1)-全標號

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

陳冠廷(Guan-Ting Chen)

指導教授 ： 史青林

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

https://doi.org/10.6840/cycu201200225

摘要

令G=(V,E)是一個圖且包含點和邊，l為將圖G的點集合和邊集合對應到一個整數集{0,…,λ}使得(1)相鄰的點不能標記相同的整數，(2)相鄰的邊不能標記相同的整數，(3)相鄰的點和邊標號差值的絕對值必須大於等於2，則稱l為圖G的一個(2,1)-全標號。在一個(2,1)-全標號中，兩個標記整數之間最大的差稱為生成數。在圖G的(2,1)-全標號中，最小的生成數我們稱之為圖G的(2,1)-全標號數，以符號λ(G)表示之。

在這篇論文中，我們把重點放在著色數為3的三正則圖的(2,1)-全標號並證明以下一些結果：

一、令n是一個大於等於2的整數，對所有i=1,2,...,n，B_i=(U_i,V_i)為一個完全二分圖K_3,3，e_i1和e_i2為B_i中的任兩個不相鄰的邊，則λ(e_11(B_1)e_12-e_21(B_2)e_22-...-e_n1(B_n)e_n2-e_11(B_1)e_12)=5。

二、令G=(A,B)是一個(3,l)-皇冠圖，其中點集合為A={a_1,a_2,...,a_l}以及B={b_1,b_2,...,b_l}，則λ(π(G;k))=5，對所有k=2,3,...[l/2]+1。

關鍵字

(2，1)-全標號 ； 三正則圖

並列摘要

Let G=(V,E) be a graph. A (2,1)-total labeling of G is a mapping from VUE into {0,…, λ} for some integer λ such that (i) if x and y are adjacent vertices, then l(x) =/=l(y);(ii) if e and ｆ are adjacent edges, then l(e)=/=l(f);(iii) if an edge e is incident to a vertex x, then |l(e)-l(x)|>=2. The span of a (2,1)-total labeling is the maximum difference between two labels. The (2,1)-total number of a graph G is the minimum span of a (2,1)-total labeling of G, denoted by λ(G).

In this thesis, we mainly focus on the (2,1)-total labelings of 3-chromatic cubic graphs, and we prove the following results:

1.Let n be an integer and n>=2. For i=1,2,...,n, let B_i=(U_i,V_i) be the complete bipartite K_3,3 and let e_i1 and e_i2 be non-adjacent edges in B_i. Then λ(e_11(B_1)e_12-e_21(B_2)e_22-...-e_n1(B_n)e_n2-e_11(B_1)e_12)=5.

2.Let G=(A,B) be a (3,l)-crown ,where A={a_1,a_2,...,a_l} and B={b_1,b_2,...,b_l}. Then λ(π(G;k))=5, fork=2,3,...[l/2]+1.

並列關鍵字

(2，1)-total labeling ； cubic graph

參考文獻

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

黃誠兆(C. C. Huang), 三正則圖的(2,1)-全標號 , 中原大學應用數學系碩士論文, 2011.

紀芳琪(F. C. Chi), 廣義彼得森圖的 (2,1)-全標號 , 中原大學應用數學系碩士論文, 2011.

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

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