摘要
令 G=(V,E) 是一個圖且包含點和邊，l為將圖G的點集合和邊集合對應到一個整數集{0,…,λ}使得(1)相鄰的點不能標記相同的整數，(2)相鄰的邊不能標記相同的整數，(3)相鄰的點和邊標號差值的絕對值必須大於等於2，則稱l為圖G的一個(2,1)-全標號。在一個(2,1)-全標號中，兩個標記整數之間最大的差值稱為跨度。在圖G的(2,1)-全標號中，最小的跨度我們稱之為圖G的(2,1)-全標號數，以符號λ(G)表示之。
在這篇論文中，我們證明對若G為一個著色數為3的四正則圖。若存在一個G的點集合的分割{A,B,C}是且滿足A、B、C是G的點獨立集且
並列摘要
LetG=(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 l(x) not equal l(y) ;(ii) if e and f are adjacent edges, then l(e) not equal l(f) ;(iii) if an edge e is incident to a vertex x, then |l(x)-l(e)| ≧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 . In this thesis, we prove that for each 4-regular graph G with x(G)=3，if there exists if there exists a partition {A,B,C} of V(G) such that A,B and C are independent sets and △(A∪B)≦ 3, △(B∪C)≦2 and △(A∪C)≦2。Then λ(G)=6 .By using this result,we prove that λ(C3p×C3q)=6 for all positive integers p and q .Moreover,we also prove that λ(C3×Cn)=6 for each positive integer n≧3 .