  博碩士論文 962201020 詳細資訊

 以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：8 、訪客IP：34.204.191.31

(Some results on distance-two labeling of a graph)

 ★ 圓環面網路上的病毒散播 ★ 以2D HP 模型對蛋白質摺疊問題之研究 ★ On Steiner centers of graphs ★ On the Steiner medians of a block graph ★ 圖形列表著色 ★ 秩為5的圖形 ★ 關於非奇異線圖的樹 ★ On Minimum Strictly Fundamental Cycle Basis ★ 目標集選擇問題 ★ 路徑圖與格子圖上的目標集問題 ★ 超立方體圖與格子圖上的目標集問題 ★ 圖形環著色數的若干等價定義 ★ 網格圖上有效電阻計算方法的比較 ★ d 維立方體圖上有效電阻與首達時間的計算方法

1. 本電子論文使用權限為同意立即開放。
2. 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
3. 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

Georges 和Mauro 在2002年猜測所有order大於等於7的generalized Petersen graph圖形G，皆有λ(G)小於等於7的性質。Adams，Cass和Troxell首先在2006年證明了在generalized Petersen graph的order等於7和8的情況下Georges 和Mauro的猜測為真。在本篇論文中我們將證明這Georges 和Mauro的Conjecture中order為9、10、11和12的部分。
Calamoneri和Petreschi在2004年考慮了用regular 多邊形拼成平面的圖形，其L(2,1)-labeling。在本篇論文中我們，我們進一步探討用四邊形和八邊形拼成平面的圖形其λ-number。也探討用五邊形和七邊形拼成平面的圖形，推得其λ-number的上下界。

AUTHOR: Yuen-Chen Huang
ADVISOR: Professor Hong-Gwa Yeh
ABSTRACT
For integer n such that n ≥ 3, a graph G is called a generalized Petersen graph of order n if and only if G is a 3-regular graph consisting of two disjoint cycles (called inner and outer cycles) of length n, where each vertex of the outer (respectively, inner) cycle is adjacent to exactly one vertex of the inner (respectively, outer) cycle.
An L^k(2,1)-labeling of a graph G is a mapping f from the vertex set of G to the set
{0,1,2,...,k} such that │f(x) − f(y)│≥ 2 if d(x,y) = 1 and f(x)≠f(y) if d(x,y) = 2,
where d(x,y) is the distance between vertices x and y in G. The minimum k for which G admits an L^k(2,1)-labeling, denoted λ(G), is called the λ-number of G.
Georges and Mauro [GM2002] conjectured that λ(G) ≤ 7 for all generalized Petersen graphs G of order n ≥ 7. In 2006, Adams, Cass and Troxell [AT] proved that this conjecture is true for orders 7 and 8. In this paper we prove that Georges and Mauro’s conjecture is true for order n = 9,10,11, and 12.
In 2004, Calamoneri and Petreschi considered L(2,1)-labeling on regular tilings of the plane. Because of the motivation by their results, we give the λ-number for the tiling of the plane which tiled by square and octagon and also a bound for the tiling of the plane which tiled by pentagon and heptagon.

★ 1)-labeling
★ L(2
★ tiling of the plane
★ λ-number

Contents......i
1 Introduction and preliminaries......1
2 Generalized Petersen graphs of orders 9, 10, 11 and 12......4
3 L(2,1)-labeling on tilings of the plane......21
References......24

 S. S. Adams, J. Cass, D. S. Troxell, An extension of the channel-assignment
problem: L(2,1)-labelings of generalized Petersen graphs, IEEE Trans. Circuits
and Systems I 53 (2006) 1101-1107.
 S. S. Adams, J. Cass, D. S. Troxell, C. Wheeland, The minimum span of L(2,1)-
labelings of certain generalized Petersen graphs, Discrete Appl. Math. 155 (2007)
1314-1325.
 J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics,
Vol. 244, Springer-Verlag, New York, 2008.
 T. Calamoneri, The L(h,k)-labeling problem: a survey and annotated bibliograhy,
Comput. J. 49 (2006) 585-608.
 T. Calamoneri and R. Petreschi, L(h; 1)-labeling subclasses of planar graphs, J.
Parall. Distrib. Comput. 64 (2004) 414-426.
 J. P. Georges, D. W. Mauro, On generalized Petersen graphs labeled with a con-
dition at distance two, Discrete Math. 259 (2002) 311-318.
 J. R. Griggs, R. K. Yeh, Labeling graphs with a condition at distance two, SIAM
J. Discrete Math. 5 (1992) 586-595.
 W. K. Hale, The Frequency assignment: theory and application, Proc. IEEE 68
(1980) 1497-1514.
 R. K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete
Math. 306 (2006) 1217-1231.