臺灣博碩士論文加值系統

(p,1)-全標號是一種將圖中的點集合與邊集合對應到整數集的函數，使得：(1)任兩個相鄰的點必須標不同的數字(2)任兩個相鄰邊必須標不同的數字，且(3)每一個邊與其端點間的標號差的絕對值必須大於等於p。一個(p,1)-全標號的生成數指的是圖中任兩標號間的最大差。而一個圖的所有(p,1)-全標號中的最小生成數則稱為(p,1)-全標號數，表示成λp,t(G)。
令n和k是正整數。如果圖包含點集合{v(1),...,v(n)}和{u(1)...,u(n)} ;以及邊u(i)u(i+1) ，u(i)v(i) 和v(i)v(i+k)，我們稱此種圖為廣義彼德森圖並表示成P(n,k)。
在此篇論文中，我們把重點放在廣義彼德森圖的(2,1)-全標號中，並證明對所有正整數n同餘0(mod 3)而言，λ2,T(P(n,k)=5， 當k不被3整除時。

A (p,1)-total labeling of a graph G is to be an assignment of V(G)∪E(G) to integers such that: (i) any two adjacent vertices of G receive distinct integers, (ii) any two adjacent edges of G receive distinct integers, and (iii) 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 is the maximum difference between two labels. The minimum span of a (p,1)-total labeling of G is called to be the (p,1)-total number and denoted by λp,T(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(i)u(i+1),u(i)v(i), and v(i)v(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 the generalized Petersen graph, and we show that for each positive integer n≡0 (mod 3), λ2,T(P(n,k))=5 if k is not divisible by 3.

中文摘要I
Abstract II
誌謝III
contents IV
1 Introduction 1
1.1 Motivation 1
1.2 The Preliminaries in Graph Theory 2
1.3 The Preliminaries in -total labeling 3
2 The Main Result 5
3 Concluding Remark 8
References 9

[1] F. Bazzaro, M. Montassier, A. Raspaud, -Total labeling of planar 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 -labeling of graphs, Discrete Math. 220 (2000) 57-66.
[3] D. Chen, W. Wang, -Total labeling of outer planar graphs, Discrete Appl. Math. 155 (2007) 2585-2593.
[4] J. R. Griggs and R. K. Yeh, Labeling graphs with a condition at distance two, SIAM J Discrete Math 5 (1992), 586-595.
[5] F. Havet and S. Thomass'e, Complexity of -total labeling.
[6] F. Havet, M.-L. Yu, -Total labeling of graphs, Discrete Math. 308 (2008) 496-513.
[7] M. Montassier, A. Raspaud, -total labeling of graphs with a given maximum average degree, Technical Report RR-1308-03, LaBRI, 2003.
[8] D. B. West, Introduction to Graph Theory 2nd, Prentice Hall, New Jersey,
2001.
[9] M. A. Whittlesey, J. P. Georges, and D. W. Mauro, On the λ-number of and related graphs, SIAM J Discrete Math 8 (1995), 449-506.
[10] J. H. Yang, On -total labeling of generalized Petersen graphs,中原應用數學系碩士論文, 2010.