| 摘要: | 論文題目：Some results on distance-two labeling of a graph 研究生：黃元貞 指導教授：葉鴻國 論文題要： 當n大於等於3時，若一個3-regular圖是由兩個不相交且點數(vertex)皆為n的圓（稱為內圈和外圈）加邊(edge)構成，且二圓中的外圈上每點只與內圈的某一點相連接，則此圖形為稱為order為n的generalized Petersen graph。 圖G上的L^k(2,1)-labeling 定義為圖形上由V(G)映至{0,1,...,k} 的一個函數，此函數包含兩個條件，第一個條件為圖形上相鄰的兩點，其函數值差大於等於2，第二個條件為圖形上距離2的兩點，其函數值需不相同。若一個圖形G有L^k(2,1)-labeling，則將k的最小值定義為此圖形G的λ-number，寫成λ(G)。 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的上下界。 Some results on distance-two labeling of a graph 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. |
