臺灣博碩士論文加值系統

在本論文中，討論有關於三層限制的圖形標號問題。包含基本的樹狀圖、環狀圖以及矩陣圖形，在已給定的三層限制下，找出最好的標號。

For positive integers , an -labeling of a digraph is a function from into the set of nonnegative integers such that if the distance between and is i in , for i = 1,2,3. The -number, of a graph , which is the minimum of the maximum label used in an -labeling of . This thesis considers the L(d, 1, 1)-labeling and the L(3, 2, 1)-labeling on several classes of graphs.

Abstract i
Contents ii
I. Introduction ……………………..…...……………………………………………1
1.1 Graphs ………………………………………………………………………...1
1.2 Distance Labeling …………………………………………………………….3
II. Distance Labeling with Three Levels of Constraints...……………………………5
2.1 Introduction and Basic Results……………………………………….. ……...5
2.2 -labeling of Path……………………………………………............. 5
2.3 -labeling of Circle .…………………………………………………..6
2.4 -labeling of the Product of Two Paths………………………………12
2.5 -labeling……………………………….………………….………...24
References……………………………………………………………………………34

[1] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North-Holland, New York, 1976.
[2] T. Calamoneri, The L(h, k)-labeling problem: A survey and annotated bibliography, The Computer Journal, 49 (2006), 585-608.
[3] G. J. Chang and D. Kuo, The L(2,1)-labeling on graphs, SIAM J. Discrete Math. 9 (1996) 309-316.
[4] G. Chartrand and P. Zhang, Introduction to Graph Theory, McGraw-Hill, 2005.
[5] X. T. Jin, Real number graph labeling with distance conditions, Ph.D. thesis, Dept. of Math., Univ. of S. Carolina, Columbia, SC, USA (2005).
[6] X. T. Jin and R. K. Yeh, Graph distance-dependent labeling related to code assignment in computer networks, Naval Research Logistics 52 (2005), 159-164.
[7] D. B. West, Introduction to Graph Theory, 2nd. ed., Prentice Hall, New Jersey, 2001.
[8] R. K. Yeh, A survey on labeling graphs with a condition at distance two, Disc. Math. 306 (2006), 1217-1231.