Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/139216
|
| Title: | 實數標號的反魔幻圖形
Graphs with R-Antimagic Labeling |
| Authors: | 劉繕榜
Liu, Shan-Pang |
| Contributors: | 張宜武
Chang, Yi-Wu
劉繕榜
Liu, Shan-Pang |
| Keywords: | R-反魔幻圖
正則圖
笛卡爾乘積圖
均勻R-反魔幻
Uniformly R-antimagic graphs
R-antimagic graphs
Regular graphs
Cartesian product of graphs |
| Date: | 2022 |
| Issue Date: | 2022-03-01 17:19:30 (UTC+8) |
| 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-反魔幻。最後，我們在第五章作研究結果總結及討論，並提出未來研究方向。
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. |
| 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. |
| Description: | 博士
國立政治大學
應用數學系
100751502 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0100751502 |
| Data Type: | thesis |
| DOI: | 10.6814/NCCU202200274 |
| Appears in Collections: | [應用數學系] 學位論文
|
Files in This Item:
| File |
Description |
Size | Format | |
|---|
| 150201.pdf | | 595Kb | Adobe PDF2 | 0 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
