政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/139216
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  全文筆數/總筆數 : 113451/144438 (79%)
造訪人次 : 51281618      線上人數 : 853
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜尋範圍 查詢小技巧：
  • 您可在西文檢索詞彙前後加上"雙引號"，以獲取較精準的檢索結果
  • 若欲以作者姓名搜尋，建議至進階搜尋限定作者欄位，可獲得較完整資料
    •  進階搜尋
    政大機構典藏 > 理學院 > 應用數學系 > 學位論文 >  Item 140.119/139216


    請使用永久網址來引用或連結此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/139216


    題名: 實數標號的反魔幻圖形
    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
    上傳時間: 2022-03-01 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
    DOI: 10.6814/NCCU202200274
    顯示於類別:[應用數學系] 學位論文

    文件中的檔案:

    檔案 描述 大小格式瀏覽次數
    150201.pdf595KbAdobe PDF20檢視/開啟


    在政大典藏中所有的資料項目都受到原著作權保護.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 回饋