| 研究生: |
蔡侑穎 Tsai, Yu-Ying |
|---|---|
| 論文名稱: |
實數反魔圖與k平移反魔圖之比較 A comparison between R-antimagic graphs and k-shifted antimagic graphs |
| 指導教授: |
張宜武
Chang, Yi-Wu 李渭天 Li, Wei-Tian |
| 口試委員: |
張宜武
Chang, Yi-Wu 李渭天 Li, Wei-Tian 陳天進 Chen, Ten-Ging |
| 學位類別: |
碩士
Master |
| 系所名稱: |
理學院 - 應用數學系 Department of Mathematical Sciences |
| 論文出版年: | 2023 |
| 畢業學年度: | 111 |
| 語文別: | 英文 |
| 論文頁數: | 40 |
| 中文關鍵詞: | k平移反魔圖 、實數反魔方 、雙星圖 S2,2 |
| 外文關鍵詞: | R-antimagic graphs, K-shifted antimagic graphs, S2,2 |
| 相關次數: | 點閱:169 下載:2 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
具有m 條邊的連通圖的反魔法標號是一個單射函數從邊集合中的m 條邊標上{1, 2, 3, ...,m} 的正整數使得標號的總和在不同的頂點是不同的。一個圖如果它帶有反魔法標號,則稱為反魔圖。Hartsfield and Ringel [7] 推測除了K2 之外的所有連通圖都有反魔法標號。在第1 章中,我們介紹了一些圖論的基本術語以及一些符號與名詞定義。在第2 章中,我們有一些k 平移反魔圖和實數反魔圖的定理。我們對k 平移反魔圖和實數反魔圖之間是否有差異感到興趣。在第3.1章,我們從最多四個邊的圖開始。幾乎所有這些都已經從實數標號的反魔圖[12]和圖的移位反魔方標號[2] 中得到證明。在第3.2 章中,我們嘗試證明如果一個有五個邊的圖是任意k 平移反魔圖,那麼它也是實數反魔圖。最後,我們找到了一個反例,雙星圖S2,2 是任意k 平移反魔圖,但它不是實數反魔圖。
An antimagic labeling of a connected graph with m edges is a injection from the set of edges E(G) to the set of integers {1, 2, 3, ...,m} such that the sum of labels on edges incident to u differs from that edges incident to
v. A graph is called antimagic if it has an antimagic labeling. Hartsfield and Ringel conjectured that every connected graph other than K2 has an antimagic labeling. In Chapter 1, we introduced some definitions and notations
of graph. In Chapter 2, we survey some theorems and propositions of k-shifted antimagic graphs and R-antimagic graphs. We are interested in the difference between of k-shifted antimagic and R-antimagic. In Chapter 3.1, we start the investigation from graphs on at most four edges. From the two references [2] and [12], we know all these graphs are k-shifted antimagic and R-antimagic. In Chapter 3.2, we want to show that if a graph on five edges is k-shifted antimagic, then it is also R-antimagic. Finally, we found
a counterexample: The double star S2,2 is k-shifted-antimagic, but it is not R-antimagic.
致謝 i
中文摘要 ii
Abstract iii
Contents iv
List of Figures vi
1 Graph terminologies 1
2 Background 3
2.1 Antimagic graphs 3
2.2 k-shifted antimagic graphs 4
2.3 R-antimagic graphs 5
3 Main Results 7
3.1 Graphs on at most four edges 7
3.2 Graphs on five edges 9
4 Conclusions and future work 37
4.1 Summary of the results 37
4.2 Future work 38
Bibliograph 40
[1] N. Alon, G. Kaplan, Y. Roddity, R. Yuster, Dense graphs are antimagic, Journal of Graph Theory, 47 (2004), P.297-309.
[2] F.-H. Chang, H.-B. Chen, W.-T. Li, and Z. Pan, Shifted-Antimagic Labelings for Graphs, Graphs and Combinatorics, 37 (2021) , P.1065–1082.
[3] F.-H. Chang, P. Chin, W.-T. Li, and Z. Pan, The Strongly Antimagic labelings of Double Spiders, arXiv:1712.09477 2018.
[4] F.-H. Chang, Y.-C. Liang, Z. Pan, and X. Zhu, Antimagic labeling of regular graphs, Journal of Graph Theory, 82 (2016), P.339-349.
[5] D. W. Cranston, Y.-C. Liang, X. Zhu, Regular Graphs of Odd Degree Are Antimagic, Journal of Graph Theory, 80 (2015), P.28-33.
[6] D.W. Cranston„ Regular bipartite graphs are antimagic, J. Gr. Theory 60, 173–182 (2009)
[7] N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, INC., Boston, 1990, P.108-109, Revised version 1994.
[8] T.-Y.Huang, Antimagic Labeling on Spiders, Master Thesis, Department of Mathematics, National Taiwan University (2015)
[9] D. Hefetz, Anti-magic Graphs via the Combinatorial NullStellenSatz, Journal of Graph Theory, 50 (2005), P.263-272.
[10] D. Hefetz, T. Mütze, J.Schwartz, On antimagic directed graphs, Journal of Graph Theory, 64 (2010), P.219-232.
[11] G. Kaplan, A. Lev, Y. Roditty, On zero-sum partitions and antimagic trees, Discrete Math. 309, 2010–2014 (2009)
[12] Shan-Pang Liu, Graphs with R-Antimagic Labeling, DOI:10.6814/NCCU202200274
[13] A. Lozano, M. Moray, C. Seara, Antimagic labelings of caterpillars, Appl. Math. Comput. 347, 734–740 (2019)
[14] Y.-C.Liang, X. Zhu, Anti-magic labeling of cubic graphs, J. Gr. Theory 75, 31–36 (2014)
[15] Y.-C. Liang, T.-L. Wong, X. Zhu, Anti-magic labeling of trees, Discrete Mathematics, 331 (2014), P.9-14.
[16] M.-J.Lee, C. Lin, W.-H.Tsai, On antimagic labeling for power of cycles, Ars Comb. 98, 161–165 (2011)
[17] M. Matamala, J. Zamora, Graphs admitting antimagic labeling for arbitrary sets of positive numbers, Electronic Notes in Discrete Mathematics, 64 (2007), P.159-164.
[18] J.-L.Shang, Spiders are antimagic, Ars Comb. 118, 367–372 (2015)
[19] T.-L. Wong, X. Zhu, Antimagic labeling of vertex weighted graphs, Journal of Graph Theory, 70 (2012), P.348-350.
[20] T.-L. Wong, X. Zhu, Total weight choosability of graphs, Journal of Graph Theory, 66 (2011), P.198-212.
[21] T.-M.Wang, Toroidal grids are anti-magic, Lect. Notes Comput. Sci. 3595, 671–679 (2005)
[22] T.-M.Wang, C.-C.Hsiao, On anti-magic labeling for graph products., Discrete Math. 308, 3624–3633 (2008)
[23] D.B. West. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River,2001.