博碩士論文 962201020 完整後設資料紀錄

 DC 欄位 值 語言 DC.contributor 數學系 zh_TW DC.creator 黃元貞 zh_TW DC.creator Yuen-Chen Huang en_US dc.date.accessioned 2009-7-1T07:39:07Z dc.date.available 2009-7-1T07:39:07Z dc.date.issued 2009 dc.identifier.uri http://ir.lib.ncu.edu.tw:88/thesis/view_etd.asp?URN=962201020 dc.contributor.department 數學系 zh_TW DC.description 國立中央大學 zh_TW DC.description National Central University en_US dc.description.abstract 論文題目：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的上下界。 zh_TW dc.description.abstract 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. en_US DC.subject generalized Petersen graph en_US DC.subject 1)-labeling en_US DC.subject L(2 en_US DC.subject tiling of the plane en_US DC.subject λ-number en_US DC.title Some results on distance-two labeling of a graph en_US dc.language.iso en_US en_US DC.type 博碩士論文 zh_TW DC.type thesis en_US DC.publisher National Central University en_US