臺灣博碩士論文加值系統

　(p,1)-全標號是從圖中的點集合與邊集合到一個整數集合的映射，使得任兩個相鄰的點標不同的整數，任兩個相鄰的邊標不同的整數，且每一個邊與相連接的點的標號差的絕對值大於等於 p。一個(p,1)-全標號的跨度為任兩標號間的最大差。而一個圖G的所有(p,1)-全標號中的最小跨度稱為(p,1)-全標號數，寫成λ_P^T (G)。

　　令n和k為正整數，一個圖若包含點集合{u_1,…,u_n }∪{v_1,…,v_n}以及邊集合{u_i u_(i+1)|i=1,2,…,n}∪{u_i v_i |i=1,2,…,n}∪{v_i v_(i+k)|i=1,2,…,n;k<n}，其中下標加法以n為模(modulo)，則稱為廣義彼德森圖，並寫成P(n,k)。

　　本論文主要探討廣義彼德森圖的(2,1)-全標號並證明了下列兩個結果。

　　(1)對所有正整數n和k，1≤k<n，如果n是11的倍數，且k不是11的倍數，則λ_2^T (P(n,k) )=5。

　　(2)對所有大於2的正整數n，則λ_2^T (P(n,2) )=5。

A (p,1)-total labeling of a graph G is to be an assignment of V(G)∪E(G) to integers such that any two adjacent vertices of G receive distinct integers, any two adjacent edges of G receive distinct integers and 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 of a graph G is the maximum difference between two labels. The minimum span of a (p,1)-total labeling of G is called the (p,1)-total number of G and denoted by λ_P^T (G).
Let n and k be two positive integers. The graph with vertex set {u_1,…,u_n }∪{v_1,…,v_n } and edges set {u_i u_(i+1) |i=1,2,…,n}∪{u_i v_i |i=1,2,…,n}∪{v_i v_(i+k) ┤|i=1,2,…,n; k<n}, 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 the generalized Petersen graph, and we prove the following two results.
(1)For each pair of positive integers n and k, 1≤k<n, if n≡0(mod 11) and k is not divisible by 11, then λ_2^T (P(n,k) )=5.

(2)For each integer n≥2, then λ_2^T (P(n,2) )=5.

摘要 I
Abstract II
謝誌 III
Contents IV
1. Introduction 1
1.1 Motivation 1
1.2 The Preliminaries in Graph Theory 2
1.3 Known Results 4
2. Main Results 6
3. Concluding Remark 21
References 22

[1] F. Bazzaro, M. Montassier and A. Raspaud, (d,1)-Total labeling of planar graphs with large girth and high maximum degree, Discrete Math. 307, 2141-2151, 2007.

[2] G. J. Chang, W. T. Ke, D. Kuo, D. D. F. Liu and R. K. Yeh, On L(d,1)-labeling of graphs, Discrete Math. 220, 57-66, 2000.

[3] D. Chen and W. Wang, (2,1)-Total labeling of outerplanar graphs, Discrete Appl. Math. 155, 2585-2593, 2007.

[4] F. C. Chi, On (2,1)-total labeling of generalized Petersen graphs, Master’s thesis of Chung Yuan Christian University, 2011.

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

[6] F. Havet and S. Thomass’e, Complexity of (p,1)-total labeling.

[7] F. Havet and M. L. Yu, (p,1)-Total labeling of graphs, Discrete Math. 308, 496-513, 2008.

[8] Y. C. Lin, On (2,1)-total labeling of generalized Petersen graphs, Master’s thesis of Chung Yuan Christian University, 2011.

[9] Z. H. Lin, On (2,1)-total labeling of generalized Petersen graphs, Master’s thesis of Chung Yuan Christian University, 2010.

[10] M. Montassier and A. Raspaud, (d,1)-Total labeling of graphs with a given maximum average degree, Technical Report RR-1308-03, LaBRI, 2003.

[11] D. B. West, Introduction to Graph Theory 2nd, Prentice Hall, New Jersey, 2001.

[12] M. A. Whittlesey, J. P. Georges and D. W. Mauro, On the λ-number of Q_n and related graphs SIAM J. Discrete Math. 8, 449-506, 1995.

[13] J. H. Yang, On (2,1)-total labeling of generalized Petersen graphs, Master’s thesis of Chung Yuan Christian University, 2010.