1. NCCU Academic Hub
  2. 學術產出
  3. College of Science
  4. Theses
  5. Item

學術產出-Theses

Article View/Open

Publication Export

Google ScholarTM

政大圖書館

Citation Infomation

題名 實數標號的反魔幻圖形
Graphs with R-Antimagic Labeling
作者 劉繕榜
Liu, Shan-Pang
貢獻者 張宜武
Chang, Yi-Wu
劉繕榜
Liu, Shan-Pang
關鍵詞 R-反魔幻圖
正則圖
笛卡爾乘積圖
均勻R-反魔幻
Uniformly R-antimagic graphs
R-antimagic graphs
Regular graphs
Cartesian product of graphs
日期 2022
上傳時間 1-Mar-2022 17:19:30 (UTC+8)
摘要 設G是一個圖，且A是複數的子集，其中|A|=|E(G)|，且E(G)為圖G的邊所成集合。標號在集合A裡頭的邊標記，是從E(G)映射到A的函數。設B是複數的子集，且|B|≥|E(G)|。若對於集合B 的每個子集A，滿足|A| = |E(G)|，而且標號在A 裡頭的邊標記，使得不同頂點它們連接的邊標記之總和是不同的，則圖G被稱為B-反魔幻。一般文獻中，若G是{1, 2, ..., |E(G)|}-反魔幻，則稱圖G是反魔幻的。反魔幻圖的概念是由Hartsfield and Ringel [11]在1990 年提出的。他們猜測至少有兩條邊的連通圖都是反魔幻的。這個猜想還沒有完全解決。許多研究人員在反魔圖領域做出了一些努力。
設R表所有實數所成集合，且C表所有複數所成集合。我們將反魔圖的定義延伸推廣至R-反魔幻圖。在第二章，我們證明了每個R-反魔幻圖都是C-反魔幻。我們也證明了若圖G為正則圖，則R+-反魔幻圖就是R-反魔幻。另外，我們也發現了有一類正則圖是R-反魔幻。
在第三章中，我們證明了環及點數大於等於3的完全圖是R-反魔幻。假設圖G 是環或點數大於3的完全圖，我們可以依照每個頂點邊標記總和的大小，將點以u1, u2, ..., un排序，無關乎標號的選取，這樣的性質我們就稱為均勻R-反魔幻。明顯地，每個均勻R-反魔幻, 都是R-反魔幻。我們也證明了G1□G2□...□Gn (n ≥ 2)是均勻R-反魔幻，其中每個Gi是環或點數大於等於3 的完全圖。
在第四章，我們證明了輪子，爪子及點數大於等於6的路徑是R-反魔幻。最後，我們在第五章作研究結果總結及討論，並提出未來研究方向。
Let G be a finite graph, and A ⊆ C. An edge labeling of graph G with labels in A is an injection from E(G) to A, where E(G) is the edge set of G, and A is a subset of C. Suppose that B is a set of complex numbers with |B| ≥ |E(G)|. If for every A ⊆ B with |A| = |E(G)|, there is an edge labeling of G with labels in A such that the sums of the labels assigned to edges incident to distinct vertices are different, then G is said to be B-antimagic. A graph G is an antimagic graph in the literature, if G is {1, 2, ..., |E(G)|}-antimagic.
The concept of antimagic graphs was introduced by Hartsfield and Ringel [11] in 1990. They conjectured that every connected graph with at least two edges was antimagic. The conjecture has not been completely solved yet.
We propose the concept of R-antimagic graphs in this thesis. In Chapter 2, we prove that every R-antimagic graph is C-antimagic. We also show that every R+-antimagic graph is also R-antimagic if the graph is regular. Additionally, we discover a special class of regular graphs that are R-antimagic (see Theorem 2.3.5). One of the graphs in this class is the Peterson graph.
In Chapter 3, we show that cycles and complete graphs of order ≥ 3 are R-antimagic. Assume that G is a complete graph or a cycle with V (G)={u1, u2, ..., un} (n ≥ 3). We have found that all the vertices of G can be listed as u1, u2, ..., un such that for every A ⊆ R with |A|=|E(G)|, there is an edge labeling f of G with labels in A such that f +(u1) < f +(u2) < ... < f +(un). The property we call uniformly R-antimagic property which is independent of the choice of the subset A of R. Clearly, every uniformly R-antimagic is R-antimagic. We prove that Cartesian products G1□G2□...□Gn (n ≥ 2) are uniformly R-antimagic, where each Gi is a complete graph of order ≥ 2 or a cycle.
In Chapter 4, we prove that wheels, paws, and paths of order ≥ 6 are R-antimagic. Finally, we summarize the findings and recommend future research in Chapter 5.
參考文獻 [1] Noga Alon, Gil Kaplan, Arieh Lev, Yehuda Roditty, and Raphael Yuster. Dense graphs are antimagic. Journal of Graph Theory, 47(4):297–309, 2004.
[2] Martin Bača, Oudone Phanalasy, Joe Ryan, and Andrea Semaničová-Feňovčíková. Antimagic labelings of join graphs. Mathematics in Computer Science, 9(2):139–143, 2015.
[3] Fei-Huang Chang, Hong-Bin Chen, Wei-Tian Li, and Zhishi Pan. Shifted-antimagic labelings for graphs. Graphs and Combinatorics, 37(3):1065–1082, 2021.
[4] Fei-Huang Chang, Pinhui Chin, Wei-Tian Li, and Zhishi Pan. The strongly antimagic labelings of double spiders. arXiv preprint arXiv:1712.09477, 2017.
[5] Feihuang Chang, Yu-Chang Liang, Zhishi Pan, and Xuding Zhu. Antimagic labeling of regular graphs. Journal of Graph Theory, 82(4):339–349, 2016.
[6] Yi Wu Chang and Shan Pang Liu. Cartesian products of some regular graphs admitting antimagic labeling for arbitrary sets of real numbers. Journal of Mathematics, 2021:1–8,
2021.
[7] Yongxi Cheng. Lattice grids and prisms are antimagic. Theoretical Computer Science, 374(1-3):66–73, 2007.
[8] Yongxi Cheng. A new class of antimagic cartesian product graphs. Discrete Mathematics, 308(24):6441–6448, 2008.
[9] Daniel W Cranston. Regular bipartite graphs are antimagic. Journal of Graph Theory, 60(3):173–182, 2009.
[10] Daniel W Cranston, Yu-Chang Liang, and Xuding Zhu. Regular graphs of odd degree are antimagic. Journal of Graph Theory, 80(1):28–33, 2015.
[11] Nora Hartsfield and Gerhard Ringel. Pearls in Graph Theory. Boston: Academic Press, Inc., 1990.
[12] Dan Hefetz. Anti-magic graphs via the combinatorial nullstellensatz. Journal of Graph Theory, 50(4):263–272, 2005.
[13] Yu-Chang Liang and Xuding Zhu. Antimagic labeling of cubic graphs. Journal of Graph Theory, 75(1):31–36, 2014.
[14] Martín Matamala and José Zamora. Graphs admitting antimagic labeling for arbitrary sets of positive numbers. Discrete Applied Mathematics, 281:246–251, 2020.
[15] Jen-Ling Shang. Spiders are antimagic. Ars Combin, 97:367–372, 2015.
[16] Jen-Ling Shang, Chiang Lin, and Sheng-Chyang Liaw. On the antimagic labeling of star forests. Util. Math, 97:373–385, 2015.
[17] Tao Wang, Ming Ju Liu, and De Ming Li. A class of antimagic join graphs. Acta Mathematica Sinica, English Series, 29(5):1019–1026, 2013.
[18] Tao-Ming Wang. Toroidal grids are anti-magic. In International Computing and Combinatorics Conference, pages 671–679. Springer, 2005.
[19] Tao-Ming Wang and Cheng-Chih Hsiao. On anti-magic labeling for graph products. Discrete Mathematics, 308(16):3624–3633, 2008.
[20] Mark E. Watkins. A theorem on tait colorings with an application to the generalized petersen graphs. Journal of Combinatorial Theory, 6(2):152–164, 1969.
[21] Douglas Brent West. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, 2001.
[22] Yuchen Zhang and Xiaoming Sun. The antimagicness of the cartesian product of graphs. Theoretical Computer Science, 410(8-10):727–735, 2009.
描述 博士
國立政治大學
應用數學系
100751502
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0100751502
資料類型 thesis
dc.contributor.advisor 張宜武zh_TW
dc.contributor.advisor Chang, Yi-Wuen_US
dc.contributor.author (Authors) 劉繕榜zh_TW
dc.contributor.author (Authors) Liu, Shan-Pangen_US
dc.creator (作者) 劉繕榜zh_TW
dc.creator (作者) Liu, Shan-Pangen_US
dc.date (日期) 2022en_US
dc.date.accessioned 1-Mar-2022 17:19:30 (UTC+8)-
dc.date.available 1-Mar-2022 17:19:30 (UTC+8)-
dc.date.issued (上傳時間) 1-Mar-2022 17:19:30 (UTC+8)-
dc.identifier (Other Identifiers) G0100751502en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/139216-
dc.description (描述) 博士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 應用數學系zh_TW
dc.description (描述) 100751502zh_TW
dc.description.abstract (摘要) 設G是一個圖，且A是複數的子集，其中|A|=|E(G)|，且E(G)為圖G的邊所成集合。標號在集合A裡頭的邊標記，是從E(G)映射到A的函數。設B是複數的子集，且|B|≥|E(G)|。若對於集合B 的每個子集A，滿足|A| = |E(G)|，而且標號在A 裡頭的邊標記，使得不同頂點它們連接的邊標記之總和是不同的，則圖G被稱為B-反魔幻。一般文獻中，若G是{1, 2, ..., |E(G)|}-反魔幻，則稱圖G是反魔幻的。反魔幻圖的概念是由Hartsfield and Ringel [11]在1990 年提出的。他們猜測至少有兩條邊的連通圖都是反魔幻的。這個猜想還沒有完全解決。許多研究人員在反魔圖領域做出了一些努力。
設R表所有實數所成集合，且C表所有複數所成集合。我們將反魔圖的定義延伸推廣至R-反魔幻圖。在第二章，我們證明了每個R-反魔幻圖都是C-反魔幻。我們也證明了若圖G為正則圖，則R+-反魔幻圖就是R-反魔幻。另外，我們也發現了有一類正則圖是R-反魔幻。
在第三章中，我們證明了環及點數大於等於3的完全圖是R-反魔幻。假設圖G 是環或點數大於3的完全圖，我們可以依照每個頂點邊標記總和的大小，將點以u1, u2, ..., un排序，無關乎標號的選取，這樣的性質我們就稱為均勻R-反魔幻。明顯地，每個均勻R-反魔幻, 都是R-反魔幻。我們也證明了G1□G2□...□Gn (n ≥ 2)是均勻R-反魔幻，其中每個Gi是環或點數大於等於3 的完全圖。
在第四章，我們證明了輪子，爪子及點數大於等於6的路徑是R-反魔幻。最後，我們在第五章作研究結果總結及討論，並提出未來研究方向。		zh_TW
dc.description.abstract (摘要) Let G be a finite graph, and A ⊆ C. An edge labeling of graph G with labels in A is an injection from E(G) to A, where E(G) is the edge set of G, and A is a subset of C. Suppose that B is a set of complex numbers with |B| ≥ |E(G)|. If for every A ⊆ B with |A| = |E(G)|, there is an edge labeling of G with labels in A such that the sums of the labels assigned to edges incident to distinct vertices are different, then G is said to be B-antimagic. A graph G is an antimagic graph in the literature, if G is {1, 2, ..., |E(G)|}-antimagic.
The concept of antimagic graphs was introduced by Hartsfield and Ringel [11] in 1990. They conjectured that every connected graph with at least two edges was antimagic. The conjecture has not been completely solved yet.
We propose the concept of R-antimagic graphs in this thesis. In Chapter 2, we prove that every R-antimagic graph is C-antimagic. We also show that every R+-antimagic graph is also R-antimagic if the graph is regular. Additionally, we discover a special class of regular graphs that are R-antimagic (see Theorem 2.3.5). One of the graphs in this class is the Peterson graph.
In Chapter 3, we show that cycles and complete graphs of order ≥ 3 are R-antimagic. Assume that G is a complete graph or a cycle with V (G)={u1, u2, ..., un} (n ≥ 3). We have found that all the vertices of G can be listed as u1, u2, ..., un such that for every A ⊆ R with |A|=|E(G)|, there is an edge labeling f of G with labels in A such that f +(u1) < f +(u2) < ... < f +(un). The property we call uniformly R-antimagic property which is independent of the choice of the subset A of R. Clearly, every uniformly R-antimagic is R-antimagic. We prove that Cartesian products G1□G2□...□Gn (n ≥ 2) are uniformly R-antimagic, where each Gi is a complete graph of order ≥ 2 or a cycle.
In Chapter 4, we prove that wheels, paws, and paths of order ≥ 6 are R-antimagic. Finally, we summarize the findings and recommend future research in Chapter 5.		en_US
dc.description.tableofcontents 致謝 i
中文摘要 ii
Abstract iii
Contents v
List of Figures vii
1 Introduction 1
1.1 Fundamental definitions and notations . . . . . . . . . 1
1.2 Antimagicness of graphs . . . . . . . . . . . . . . . . 3
1.3 Overview of the thesis . . . . . . . . . . . . . . . . 4
2 R-antimagic regular graphs 6
2.1 R+ ∪ {0}-antimagic graphs . . . . . . . . . . . . . . . 6
2.2 R-antimagic graphs and C-antimagic graphs . . . . . . . 7
2.3 A class of R-antimagic regular graphs . . . . . . . . . 9
3 Uniformly R-antimagic graphs 19
3.1 Cycles and complete graphs . . . . . . . . . . . . . . 19
3.2 Cartesian products of uniformly R-antimagic graphs and complete graphs . . . . . . . . . . . . . . . . . . . . . .21
3.3 Cartesian products of uniformly R-antimagic graphs and cycles . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4 Some irregular graphs 33
4.1 Wheels . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Paws . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.3 Paths . . . . . . . . . . . . . . . . . . . . . . . . .40
5 Conclusions and further studies 44
5.1 Results . . . . . . . . . . . . . . . . . . . . . . . .44
5.2 Discussions . . . . . . . . . . . . . . . . . . . . . .45
5.3 Further studies . . . . . . . . . . . . . . . . . . . .45
Bibliography 47		zh_TW
dc.format.extent 610280 bytes-
dc.format.mimetype application/pdf-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0100751502en_US
dc.subject (關鍵詞) R-反魔幻圖zh_TW
dc.subject (關鍵詞) 正則圖zh_TW
dc.subject (關鍵詞) 笛卡爾乘積圖zh_TW
dc.subject (關鍵詞) 均勻R-反魔幻zh_TW
dc.subject (關鍵詞) Uniformly R-antimagic graphsen_US
dc.subject (關鍵詞) R-antimagic graphsen_US
dc.subject (關鍵詞) Regular graphsen_US
dc.subject (關鍵詞) Cartesian product of graphsen_US
dc.title (題名) 實數標號的反魔幻圖形zh_TW
dc.title (題名) Graphs with R-Antimagic Labelingen_US
dc.type (資料類型) thesisen_US
dc.relation.reference (參考文獻) [1] Noga Alon, Gil Kaplan, Arieh Lev, Yehuda Roditty, and Raphael Yuster. Dense graphs are antimagic. Journal of Graph Theory, 47(4):297–309, 2004.
[2] Martin Bača, Oudone Phanalasy, Joe Ryan, and Andrea Semaničová-Feňovčíková. Antimagic labelings of join graphs. Mathematics in Computer Science, 9(2):139–143, 2015.
[3] Fei-Huang Chang, Hong-Bin Chen, Wei-Tian Li, and Zhishi Pan. Shifted-antimagic labelings for graphs. Graphs and Combinatorics, 37(3):1065–1082, 2021.
[4] Fei-Huang Chang, Pinhui Chin, Wei-Tian Li, and Zhishi Pan. The strongly antimagic labelings of double spiders. arXiv preprint arXiv:1712.09477, 2017.
[5] Feihuang Chang, Yu-Chang Liang, Zhishi Pan, and Xuding Zhu. Antimagic labeling of regular graphs. Journal of Graph Theory, 82(4):339–349, 2016.
[6] Yi Wu Chang and Shan Pang Liu. Cartesian products of some regular graphs admitting antimagic labeling for arbitrary sets of real numbers. Journal of Mathematics, 2021:1–8,
2021.
[7] Yongxi Cheng. Lattice grids and prisms are antimagic. Theoretical Computer Science, 374(1-3):66–73, 2007.
[8] Yongxi Cheng. A new class of antimagic cartesian product graphs. Discrete Mathematics, 308(24):6441–6448, 2008.
[9] Daniel W Cranston. Regular bipartite graphs are antimagic. Journal of Graph Theory, 60(3):173–182, 2009.
[10] Daniel W Cranston, Yu-Chang Liang, and Xuding Zhu. Regular graphs of odd degree are antimagic. Journal of Graph Theory, 80(1):28–33, 2015.
[11] Nora Hartsfield and Gerhard Ringel. Pearls in Graph Theory. Boston: Academic Press, Inc., 1990.
[12] Dan Hefetz. Anti-magic graphs via the combinatorial nullstellensatz. Journal of Graph Theory, 50(4):263–272, 2005.
[13] Yu-Chang Liang and Xuding Zhu. Antimagic labeling of cubic graphs. Journal of Graph Theory, 75(1):31–36, 2014.
[14] Martín Matamala and José Zamora. Graphs admitting antimagic labeling for arbitrary sets of positive numbers. Discrete Applied Mathematics, 281:246–251, 2020.
[15] Jen-Ling Shang. Spiders are antimagic. Ars Combin, 97:367–372, 2015.
[16] Jen-Ling Shang, Chiang Lin, and Sheng-Chyang Liaw. On the antimagic labeling of star forests. Util. Math, 97:373–385, 2015.
[17] Tao Wang, Ming Ju Liu, and De Ming Li. A class of antimagic join graphs. Acta Mathematica Sinica, English Series, 29(5):1019–1026, 2013.
[18] Tao-Ming Wang. Toroidal grids are anti-magic. In International Computing and Combinatorics Conference, pages 671–679. Springer, 2005.
[19] Tao-Ming Wang and Cheng-Chih Hsiao. On anti-magic labeling for graph products. Discrete Mathematics, 308(16):3624–3633, 2008.
[20] Mark E. Watkins. A theorem on tait colorings with an application to the generalized petersen graphs. Journal of Combinatorial Theory, 6(2):152–164, 1969.
[21] Douglas Brent West. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, 2001.
[22] Yuchen Zhang and Xiaoming Sun. The antimagicness of the cartesian product of graphs. Theoretical Computer Science, 410(8-10):727–735, 2009.		zh_TW
dc.identifier.doi (DOI) 10.6814/NCCU202200274en_US