圖形之分割與反魔標號

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：20

、訪客IP：3.145.52.86

姓名

陳抮君(Zhen-Chun Chen) 查詢紙本館藏

畢業系所

數學系

論文名稱

圖形之分割與反魔標號
(Decompositions and Antimagic Labelings of Graphs)

相關論文

★ 圖之均勻分解與有向圖之因子分解	★ 加權圖之和、中位點及位移
★ 迴圈之冪圖的星林分解數	★ 圖形的線性蔭度及星形蔭度
★ On n-good graphs	★ A Note On Degree-Continuous Graphs
★ Status Sequences and Branch-Weight Sequences of Trees	★ n-realizable Quadruple
★ 圖形的路徑分解,迴路分解和星形分解	★ 星林圖的二分解與三分解
★ 2-decomposable, 3-decomposable multipaths and t-decomposable spiders	★ 圖形分解與反魔圖
★ The antimagic graph with a generalization	★ 圖的程度序列和狀態
★ The 3-split of multipaths and multicycles with multiplicity 2

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本篇論文研究圖形之分解(decompositions of graphs)與圖形之反魔標號(antimagic labelings of graphs)。
在第一章，我們介紹一些術語跟需要的符號。第二~四章我們探討圖形之分解，第五章我們探討反魔圖。
在第二章，我們將完全圖(the complete graphs)分解成兩種特別的圖形，兩種圖邊的個數在考慮之內。
在第三章，我們討論λ重邊完全圖的最大的(Pk,Sk)-填充與最小的(Pk,Sk)-覆蓋及最大的(Pk,Ck)-填充與最小的(Pk,Ck)-覆蓋。
在第四章，我們證得蜘蛛圖(spiders)分解成t個同構的圖形的充份必要條件。
在第五章，我們得到星林圖(star forest)是反魔圖的一個必要條件和一個充份條件，且得到mS2∪Sn是反魔圖的充份必要條件。

摘要(英)

In this thesis, we investigate decompositions and antimagic labelings of graphs.
In Chapter 1, we give some terminology and notation needed in the thesis. Chapter
2∼4 concern decompositions of graphs. Chapter 5 concerns antimagic labelings of
graphs.
In Chapter 2, we consider the problems about decompositions of the complete graphs
Kn into two kinds of graphs, each with specific numbers of edges.
In Chapter 3, the problems of the maximum (Pk; Sk)-packing, the minimum (Pk; Sk)-
covering, the maximum (Ck; Sk)-packing and the minimum (Ck; Sk)-covering of Kn
are investigated.
In Chapter 4, we give necessary and sufficient conditions for the spiders to be t-
decomposable.
In Chapter 5, we obtain a necessary condition for the star forest to be antimagic and
a sufficient condition for the star forest to be antimagic, and necessary and sufficient
conditions for mS2 ∪ Sn to be antimagic.

關鍵字(中)

★ 圖形之分割
★ 反魔標號

關鍵字(英)

★ decompositions
★ antimagic

論文目次

1 Introduction 1
1.1 Introduction and preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Overview of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Decompositions of complete graphs into two kinds of graphs 5
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Decomposition of Kn into paths and stars . . . . . . . . . . . . . . . . . . . . 7
2.3 Decomposition of Kn into cycles and stars . . . . . . . . . . . . . . . . . . . . 14
3 Maximum packings and minimum coverings of multiple complete graphs 23
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 (Pk, Sk)-Packing and (Pk, Sk)-covering of λKn . . . . . . . . . . . . . . . . . . 23
3.3 (Ck, Sk)-Packing and (Ck, Sk)-covering of λKn . . . . . . . . . . . . . . . . . . 28
4 t-decomposable spiders 50
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2 t-decomposable spiders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5 Antimagic Labelings of star forests 57
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2 Antimagicness of Star Forests . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

參考文獻

[1] A. Abueida, S. Clark, and D. Leach, Multidecomposition of the complete graph into graph
pairs of order 4 with various leaves, Ars Combin. 93 (2009), 403–407.
[2] A. Abueida and M. Daven, Multidecompositons of the complete graph, Ars Combin. 72
(2004), 17–22 .
[3] A. Abueida and M. Daven,Multidecompositions of several graph products, Graphs Combin.
29 (2013), 315–326.
[4] A. Abueida and M. Daven, Multidesigns for graph-pairs of order 4 and 5, Graphs Combin.
19 (2003), 433–447.
[5] B. Alspach, D. Dyes and D. L. Kreher, On isomorphic factorization of circulant graphs,
J. Combin. Des. 14 (2006), 406–414.
[6] A. Abueida, M. Daven, and K. J. Roblee, Multidesigns of the λ-fold complete graph for
graph-pairs of order 4 and 5, Australas J. Combin. 32 (2005), 125–136.
[7] A. Abueida and C. Hampson, Multidecomposition of Kn −F into graph-pairs of order 5
where F is a Hamilton cycle or an (almost) 1-factor, Ars Combin. 97 (2010), 399–416
[8] N. Alon, G. Kaplan, A. Lev, Y. Roditty and R. Yuster, Dense grapchs are anti-magic,
J. Graph Theory 47(4) (2004), 297–309.
[9] A. Abueida and T. O’Neil, Multidecomposition of λKm into small cycles and claws, Bull.
Inst. Combin. Appl. 49 (2007), 32–40.
[10] J. Bos´ak, Decompositions of Graphs, Kluwer, Dordrecht, Netherlands, 1990.
65
[11] Darryn Bryant, Packing paths in complete graphs, J. Combin. Theory Ser. B 100 (2010),
206–215.
[12] Y. Cheng, A new class of antimagic Cartesian product graphs, Discrete Math. 308
(2008), 6441–6448.
[13] D. W. Cranston, Regular bipartite graphs are antimagic, J. Graph Theory 60 (2009),
no. 3, 173-182.
[14] D. W. Cranston, Y.-C. Liang, and X. Zhu, Regular graphs of odd degree are antimagic,
to appear, J. Graph Theory.
[15] C. R. J. Clapham, Graphs self-complementary in Kn − e, Discrete Math. 81 (1990),
229–235.
[16] G. Chartrand, A.D. Polimeni and M.J. Stewart, The existence of 1-factors in line graphs,
squares, and total graphs, Indag. Math. 35 (1973), 228–232.
[17] Y. Caro, J. Sch¨onheim, Decomposition of trees into isomorphic trees, Ars Combin. 9
(1980), 119–130.
[18] R. A. Gibbs Self-complementary graphs, J. Combinatorial Theory, Ser. B 16 (1974),
106–123.
[19] T. Gangopadhyay and S. P. Rao Hebbare, Multipartite self-complementary graphs, Ars
Combin. 13 (1982), 87–114.
[20] T. Gangopadhyay and S. P. Rao Hebbare, r-partite self-complementary graph-diameters,
Discrete Math. 32 (1980), 245–255.
[21] K. Heinrich and P. Horak, Isomorphic factorizations of trees, J. Graph Theory 19 (1995)
187–199.
66
[22] N. Hartsfield and G. Ringel, Pearls in Graph Theory, Academic Press, Boston, 1990.
[23] P. Hell and A. Rosa, Graph decompositions, handcuffed prisoners and balanced P-designs,
Discrete Math. 2 (1972), 229–252.
[24] F. Harary, R. W. Robinson and N. C. Wormald, Isomorphic factorization III : complete
multipartite graphs, Combinatorial Math., Lecture Notes in Math. 686 (1978), 47–54.
[25] F. Harary, R. W. Robinson and N. C. Wormald, The Divisibility theorem for isomorphic
factorization of complete graphs, J. Graph Theory 1 (1977), 187–188.
[26] R.E. Jamison and G. E. Stevens, Isomorphic factorizations of caterpillars, Congr. Numer.
158 (2002) 143–151.
[27] G. Kaplan, A. Lev, and Y. Roditty, On zero-sum partitions and anti-magic trees, Discrete
Math. 309 (2009), no. 8, 2010-2014.
[28] J. Knisely, C. Wallis and G. Domke, The partitioned graph isomorphism problem, Congr.
Numer. 89 (1992), 39–44.
[29] H.-C. Lee,Multidecompositions of complete bipartite graphs into cycles and stars, Ars
Combin. 108 (2013), 355–364.
[30] J.-J. Lin, Decompositions of multicrowns into cycles and stars, Taiwanese J. Mathematics,
accepted.
[31] H.-C. Lee and C. Lin, Balanced star decompositions of regular multigraphs and λ-fold
complete bipartite graphs, Discrete Math. 301 (2005), 195–206.
[32] H.-C. Lee and J.-J. Lin, Decomposition of the complete bipartite graph with a 1-factor
removed into cycles and stars, Discrete Math. 313 (2013), 2354–2358.
67
[33] Chiang Lin, Jenq-Jong Lin, Tay-Woei Shyu, Isomorphic star decomposition of multicrowns
and the power of cycles, Ars Combin. 53 (1999), 249–256.
[34] Ming-Ju Lee, Chiang Lin, and Wei-Han Tsai, On antimagic labeling for power of cycles,
Ars Combin. 98 (2011), 161165.
[35] Y.-C. Liang, T.-L. Wong, and X. Zhu, Anti-magic labeling of trees, Discrete Math. 331
(2014), 9-14.
[36] Y.-C. Liang and X. Zhu, Anti-magic labelling of Cartesian product of graphs, Theoret.
Comput. Sci. 477 (2013), 1-5.
[37] Y.-C. Liang and X. Zhu, Antimagic labeling of cubic graphs, J. Graph Theory 75 (2014),
no. 1, 31-36.
[38] H. M. Priyadharsini and A. Muthusamy, (Gm,Hm)-multidecomposition of Km;m(λ), Bull.
Inst. Combin. Appl. 66 (2012), 42–48.
[39] H. M. Priyadharsini and A. Muthusamy, (Gm,Hm)-multifactorization of λKm, J. Combin.
Math. Combin. Comput. 69 (2009), 145–150.
[40] S. J. Quinn, Factorization of complete bipartite graphs into two isomorphic sub-graphs,
Combinatorial Math. VI, Lecture Notes in Math. 748 (1979), 98–111.
[41] S. J. Quinn, Isomorphic factorization of complete equipartite graphs, J. Graph Theory 7
(1983), 285–310.
[42] J.-L. Shang, Spiders are antimagic, Ars Combin. 118 (2015), 367-372.
[43] T.-W. Shyu, Decomposition of complete graphs into cycles and stars, Graphs Combin.
29 (2013), 301–313.
68
[44] T.-W. Shyu, Decompositions of complete graphs into paths and cycles, Ars Combin. 97
(2010), 257–270.
[45] T.-W. Shyu, Decomposition of complete graphs into paths of length three and triangles,
Ars Combin. 107 (2012), 209–224.
[46] T.-W. Shyu, Decomposition of complete graphs into paths and stars, Discrete Math. 310
(2010), 2164–2169.
[47] T.-W. Shyu, Decomposition of complete bipartite graphs into paths and stars with same
number of edges, Discrete Math. 313 (2013), 865–871.
[48] G. E. Stevens, Properties of Lucas trees, Ars Combin. 92 (2009), 171–192.
[49] G. E. Stevens and R.E. Jamison, Isomorphic factorization of some linearly recursive
trees, Congr. Numer. 16 (2003), 149–160.
[50] Jen-Ling Shang, Chiang Lin, and Sheng-Chyang Liaw, On the Antimagic Labeling of
Star Forests, to appear, Utilitas Mathematica.
[51] M. Tarsi, Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed
designs, J. Combin. Theory, Ser. A 34 (1983), 60–70.
[52] M. Tarsi, Decomposition of complete multigraphs into stars, Discrete Math. 26 (1979)
273–278.
[53] Tao-Ming Wang, Toroidal grids are anti-magic, Computing and combinatorics, 671679,
Lecture Notes in Comput. Sci., 3595, Springer, Berlin, 2005.
[54] Tao-Ming Wang and Cheng-Chih Hsiao, On anti-magic labeling for graph products, Discrete
Math. 308 (2008), no. 16, 36243633.
69
[55] S. Yamamoto, H. Ikeda, S. Shige-ede, K. Ushio, and N. Hamada, On claw decomposition
of complete graphs and complete bipartie graphs, Hiroshima Math. J. 5 (1975), 33–42.

指導教授

林強(Chiang Lin)

審核日期

2015-7-24

推文