| 姓名 |
黃元貞(Yuen-Chen Huang)
查詢紙本館藏 |
畢業系所 |
數學系 |
| 論文名稱 |
(Some results on distance-two labeling of a graph)
|
| 相關論文 | |
| 檔案 |
 [Endnote RIS 格式]
[Bibtex 格式]
 [相關文章]  [文章引用]  [完整記錄]  [館藏目錄]  [檢視] [下載]- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
|
| 摘要(中) |
論文題目：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.
|
| 關鍵字(中) |
|
關鍵字(英) |
★ generalized Petersen graph
★ 1)-labeling
★ L(2
★ tiling of the plane
★ λ-number |
| 論文目次 |
Contents
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
|
| 參考文獻 |
References
[1] 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.
[2] 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.
[3] J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics,
Vol. 244, Springer-Verlag, New York, 2008.
[4] T. Calamoneri, The L(h,k)-labeling problem: a survey and annotated bibliograhy,
Comput. J. 49 (2006) 585-608.
[5] T. Calamoneri and R. Petreschi, L(h; 1)-labeling subclasses of planar graphs, J.
Parall. Distrib. Comput. 64 (2004) 414-426.
[6] J. P. Georges, D. W. Mauro, On generalized Petersen graphs labeled with a con-
dition at distance two, Discrete Math. 259 (2002) 311-318.
[7] J. R. Griggs, R. K. Yeh, Labeling graphs with a condition at distance two, SIAM
J. Discrete Math. 5 (1992) 586-595.
[8] W. K. Hale, The Frequency assignment: theory and application, Proc. IEEE 68
(1980) 1497-1514.
[9] R. K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete
Math. 306 (2006) 1217-1231.
|
| 指導教授 |
葉鴻國(Hong-Gwa Yeh)
|
審核日期 |
2009-7-1 |
| 推文 |
 facebook  plurk  twitter  funp  google  live  udn  HD  myshare  reddit  netvibes  friend  youpush  delicious  baidu
|
| 網路書籤 |
 Google bookmarks  del.icio.us  hemidemi myshare
|
