Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/143718
|
| Title: | 實數反魔圖與k平移反魔圖之比較
A comparison between R-antimagic graphs and k-shifted antimagic graphs |
| Authors: | 蔡侑穎
Tsai, Yu-Ying |
| Contributors: | 張宜武
李渭天
Chang, Yi-Wu
Li, Wei-Tian
蔡侑穎
Tsai, Yu-Ying |
| Keywords: | k平移反魔圖
實數反魔方
雙星圖 S2,2
R-antimagic graphs
K-shifted antimagic graphs
S2,2 |
| Date: | 2023 |
| Issue Date: | 2023-03-09 18:12:34 (UTC+8) |
| Abstract: | 具有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. |
| Reference: | [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)
39
[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. |
| Description: | 碩士
國立政治大學
應用數學系
104751006 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0104751006 |
| Data Type: | thesis |
| Appears in Collections: | [應用數學系] 學位論文
|
Files in This Item:
| File |
Description |
Size | Format | |
|---|
| 100601.pdf | | 445Kb | Adobe PDF2 | 73 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
