系統識別號 | U0002-2907201721205000 |
---|---|
DOI | 10.6846/TKU.2017.01063 |
論文名稱(中文) | 雙蜘蛛圖的強反魔方標號 |
論文名稱(英文) | The strongly anti-magic labeling of double spider graphs |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 數學學系碩士班 |
系所名稱(英文) | Department of Mathematics |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 105 |
學期 | 2 |
出版年 | 106 |
研究生(中文) | 金斌輝 |
研究生(英文) | Pin-Hui Chin |
學號 | 604190123 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2017-06-29 |
論文頁數 | 36頁 |
口試委員 |
指導教授
-
潘志實
委員 - 高金美 委員 - 張飛黃 |
關鍵字(中) |
強反魔方 雙蜘蛛圖 標號 |
關鍵字(英) |
strongly anti-magic double spider graphs |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
給定任意圖G=(V,E),|V(G)|=n, |E(G)|=m,圖G的一個標號f:E→{1,2,…,m}為一雙射函數。假設對於任意頂點u,令 s(u)=∑_(e∈E(u))〖f(e)〗,其中E(u)為所有與u相連的邊的集合,若對於任意i≠j,s(i)≠s(j),則稱此標號為反魔方標號。假設f是一個圖G的反魔方標號,令deg(u)為所有與u相連的邊的數量總和,若對於任意兩個不同的頂點u,v,deg(u)<deg(v),滿足s(u)<s(v),則稱f為圖G的一個強反魔方標號。 在本文中我們想要討論的是雙蜘蛛圖。由於此圖的部分形式被證明有反魔方,因此我們要證明對於任意的雙蜘蛛圖都有強反魔方標號。 |
英文摘要 |
Let G=(V,E) be a simple graph with n vertices and m edges. A labeling of G is a bijection from the set of edges to the set {1,2,…,m} of integers, for each vertex, its vertex sum is defined to be the sum of labels of all edges incident to it. If all vertices have distinct vertex sums, we call this labeling anti-magic. Suppose f is an anti-magic labeling of G, and for any two vertices u,v with deg(u) < deg(v), if vertex sum of u is strictly less than vertex sum of v, then we say f is a strongly anti-magic labeling of G. In this thesis, we restrict our graphs to double spider graphs. Since some of double spider graphs have already been proven to be anti-magic, we will prove a stronger result here, that is, all double spider graphs are strongly anti-magic. |
第三語言摘要 | |
論文目次 |
目錄 …………………………………………………………I 圖表目錄 ……………………………………………………II 第一章 基本定義……………………………………………1 第二章 反魔方標號…………………………………………5 第三章 雙蜘蛛圖的強反魔方標號…………………………9 參考文獻 ……………………………………………………35 圖表目錄 圖1.1(路徑) …………………………………………………1 圖1.2(迴圈) …………………………………………………2 圖1.3(樹圖) …………………………………………………2 圖1.4(蜘蛛圖) ………………………………………………3 圖1.5(雙蜘蛛圖) ……………………………………………4 圖2.1(P_7) ……………………………………………………5 圖2.2(S(4,4,3,3,2,2,2))………………………………………7 圖3.1…………………………………………………………14 圖3.2…………………………………………………………16 圖3.3…………………………………………………………18 圖3.4…………………………………………………………21 圖3.5…………………………………………………………24 圖3.6…………………………………………………………27 圖3.7…………………………………………………………29 圖3.8…………………………………………………………30 圖3.9…………………………………………………………30 圖3.10 ………………………………………………………31 圖3.11 ………………………………………………………32 圖3.12 ………………………………………………………32 圖3.13 ………………………………………………………33 |
參考文獻 |
[1] N.Alon, Combinatorial Nullstellensatz, Combin Probab Comput 8 (1999), 7-29. [2] N.Alon, G. Kaplan, A.Lev, Y.Roditty, and R. Yuster, Dense graphs are antimagic, J.Graph Theory 47 (2004), 297-309. [3] F. Chang, Y.-C. Liang, Z. Pan, X. Zhu, Antimagic labeling of regular graphs, J.Graph Theory 82 (2016), 339-349. [4] D. W. Cranston, Regular bipartite graphs are antimagic, J. Graph Theory 60 (2009),173-182. [5] D. W. Cranston, Y.-C. Liang and X. Zhu, Regular graphs of odd degree are antimagic, J. Graph Theory 80 (2015), 28-33. [6] J. A. Gallian, A dynamic survey of graph labeling, Electron J. Combin. 17 (2014),DS6 [7] N. Hartsfield and G. Ringel, Pearls in Graph Theory: A Comprehensive Introduction, Academic Press, Boston, 1994, pp. 109-110. [8] D. Hefetz, Anti-magic graphs via the combinatorial nullstellensatz, J. Graph Theory 50 (2005), 263-272. [9] D. Hefetz, H. T. T. Tran, and A. Saluz, An application of the Combinatorial Nullstellensatz to a graph labeling problem, J. Graph Theory 65 (2010), 70-82. [10] G. Kaplan, A. Lev, and Y. Roditty, On zero-sum partitions and antimagic trees, Discrete Math. 309 (2009), 2010-2014. [11] Y.-C. Liang, Anti-magic labeling of graphs, Doctoral Dissertation, Department of Applied Mathematics, National Sun Yat-sen University, 2014. [12] Y.-C. Liang, T.-L. Wong, X. Zhu, Anti-magic labeling of trees, Discrete Math. 331(2014), 9-14. [13] P.D. Chawathe, Vijaya Krishna, Antimagic Labeling of Complete m-ary Trees, 2002,77-80 [14] J.-L. Shang, Spiders are antimagic, Ars Combinatoria 118 (2015), 367-372. [15] T.-L. Wong and X. Zhu, Antimagic labelling of vertex weighted graphs, J. Graph Theory 70 (2012), 348-359. [16] 黃梓彥, 蜘蛛圖的反魔方標號, 2015. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信