學術產出-Theses
Article View/Open
Publication Export
-
題名 實數反魔圖與k平移反魔圖之比較
A comparison between R-antimagic graphs and k-shifted antimagic graphs作者 蔡侑穎
Tsai, Yu-Ying貢獻者 張宜武<br>李渭天
Chang, Yi-Wu<br>Li, Wei-Tian
蔡侑穎
Tsai, Yu-Ying關鍵詞 k平移反魔圖
實數反魔方
雙星圖 S2,2
R-antimagic graphs
K-shifted antimagic graphs
S2,2日期 2023 上傳時間 9-Mar-2023 18:12:34 (UTC+8) 摘要 具有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 tov. 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 notationsof 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 founda counterexample: The double star S2,2 is k-shifted-antimagic, but it is not R-antimagic.參考文獻 [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. 描述 碩士
國立政治大學
應用數學系
104751006資料來源 http://thesis.lib.nccu.edu.tw/record/#G0104751006 資料類型 thesis dc.contributor.advisor 張宜武<br>李渭天 zh_TW dc.contributor.advisor Chang, Yi-Wu<br>Li, Wei-Tian en_US dc.contributor.author (Authors) 蔡侑穎 zh_TW dc.contributor.author (Authors) Tsai, Yu-Ying en_US dc.creator (作者) 蔡侑穎 zh_TW dc.creator (作者) Tsai, Yu-Ying en_US dc.date (日期) 2023 en_US dc.date.accessioned 9-Mar-2023 18:12:34 (UTC+8) - dc.date.available 9-Mar-2023 18:12:34 (UTC+8) - dc.date.issued (上傳時間) 9-Mar-2023 18:12:34 (UTC+8) - dc.identifier (Other Identifiers) G0104751006 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/143718 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 應用數學系 zh_TW dc.description (描述) 104751006 zh_TW dc.description.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 平移反魔圖，但它不是實數反魔圖。 zh_TW dc.description.abstract (摘要) 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 tov. 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 notationsof 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 founda counterexample: The double star S2,2 is k-shifted-antimagic, but it is not R-antimagic. en_US dc.description.tableofcontents 致謝 i中文摘要 iiAbstract iiiContents ivList of Figures vi1 Graph terminologies 12 Background 32.1 Antimagic graphs 32.2 k-shifted antimagic graphs 42.3 R-antimagic graphs 53 Main Results 73.1 Graphs on at most four edges 73.2 Graphs on five edges 94 Conclusions and future work 374.1 Summary of the results 374.2 Future work 38Bibliograph 40 zh_TW dc.format.extent 455720 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0104751006 en_US dc.subject (關鍵詞) k平移反魔圖 zh_TW dc.subject (關鍵詞) 實數反魔方 zh_TW dc.subject (關鍵詞) 雙星圖 S2,2 zh_TW dc.subject (關鍵詞) R-antimagic graphs en_US dc.subject (關鍵詞) K-shifted antimagic graphs en_US dc.subject (關鍵詞) S2,2 en_US dc.title (題名) 實數反魔圖與k平移反魔圖之比較 zh_TW dc.title (題名) A comparison between R-antimagic graphs and k-shifted antimagic graphs en_US dc.type (資料類型) thesis en_US dc.relation.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. zh_TW
