跳到主要內容

臺灣博碩士論文加值系統

(44.192.254.59) 您好!臺灣時間:2023/01/27 19:58
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林浩誼
研究生(外文):Lin, Hau-Yi
論文名稱:平移環面網格的圖同構問題及其應用
論文名稱(外文):On the Graph Isomorphism Problem of Shifted Toroidal Grids and It's Applications
指導教授:林武雄林武雄引用關係高淑蓉高淑蓉引用關係
指導教授(外文):Lin, Wu-HsiungKao, Shu-Jung
口試委員:傅恆霖黃國卿
口試委員(外文):Fu, Hung-LinHuang, Kuo-Ching
口試日期:2021-12-29
學位類別:碩士
校院名稱:國立清華大學
系所名稱:數學系
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2021
畢業學年度:110
語文別:英文
論文頁數:74
中文關鍵詞:環面網格圖同構循環圖亞當猜想均勻著色辨識數
外文關鍵詞:Toroidal gridGraph isomorphismCirculant graphAd´am’s conjectureEquitable coloringDistinguishing number
相關次數:
  • 被引用被引用:0
  • 點閱點閱:70
  • 評分評分:
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
一個圖由頂點集與邊集構成。若存在頂點集間的映射保持相鄰關係,
則我們稱兩個圖同構。一個平移環面網格可以看作是環面的四邊形分割。
一個循環圖的點集是Zn,且若兩個頂點的差在某個給定差集裡則相鄰。
亞當猜想宣稱兩個循環圖同構,
若且唯若他們的給定差集相差一個與n互質的倍數。
一個圖的均勻著色是一個圖著色使得每種顏色的用量至多差1。
一個圖的辨識數是最少能使用多少種標記,
使得唯一能保持標記的自圖同構映射只有恆等映射。
在這篇論文中,我們找尋關於平移環面網格之間圖同構的充分必要條件,
並刻畫他們之間所有的圖同構映射。
在應用上我們給另一個亞當猜想在度數小於等於4的證明,
並給出二分圖平移環面網格能否均勻著色,
以及平移環面網格的辨識數。
A graph consists of a vertex set and an edge set, and two graphs are graph isomorphic if there is a bijection between their vertex sets preserving the adjacency.
A shifted toroidal grid is the graph modeling of a 4-regular quadrangulation of the
torus and a circulant graph is the graph with vertex set Zn and two vertices u and v
are adjacent if u − v is in a given difference set. Ad´am’s conjecture claims that two ´
circulant graphs are graph isomorphic if and only if their difference set is multiplied
by an integer coprime to n. An equitable coloring is a graph coloring which the
numbers of vertices in any two color classes differ by at most one. The distinguishing number is the least number of labels requiring for a labeling of vertices such that
the identity map is the unique graph automorphism of preserving the labeling. In
this thesis we find the necessary and sufficient condition for the graph isomorphism
of shifted toroidal grids and characterize all graph isomorphisms. As application
we provide another proof of Ad´am’s conjecture for circulant graphs with degree ´
less than or equal to four, we verify the equitable colorability of bipartite shifted
toroidal grids, and we provide the exact values of the distinguishing numbers for
shifted toroidal grids.
Abstract i
Content iii
List of Tables iv
List of Figures iv
1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Shifted toroidal grid . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Circulant graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Equitable coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Distinguishing number . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.7 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Preliminaries 12
3 Graph isomorphism between shifted toroidal grids 15
3.1 Straight cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
ii
3.2 Shifted toroidal grids with straight cycles . . . . . . . . . . . . . . . 18
3.3 Shifted toroidal grids with no straight cycles . . . . . . . . . . . . . 21
3.4 Main result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4 Shifted toroidal grids which are graph isomorphic to circulant
graphs and it’s application on Ad´am’s Conjecture. 37 ´
4.1 Shifted toroidal grids which are graph isomorphic to circulant graphs 37
4.2 Applications on Ad´am’s conjecture for circulant graphs ´ Cn(a, b) . . 40
4.3 Ad´am’s conjecture on ´ Cn(a, b, a + b) . . . . . . . . . . . . . . . . . . 42
5 Equitable coloring of shifted toroidal grids 47
6 Distinguish number of shifted toroidal grids 62
7 Discussion 66
7.1 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
7.2 Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
References 68
[1] A. Ad´am, Research problem 2-10, Journal of Combinatorial Theory, vol. 2, ´
393, 1967.
[2] A. Altshuler, Construction and enumeration of regular maps on the torus,
Discrete Mathematics, vol. 4, 201–217, 1973.
[3] A. Hajnal and E. Szemer´edi, Proof of a conjecture of P. Erd˝os, In combinatorial
theory and its applications, North Holland, vol. 2, pp. 601–623, 1970.
[4] A. Cayley, Desiderata and suggestions, American Journal of Mathematics, vol.
1, no. 2, 174–176, 1878.
[5] A. Nakamoto, Irreducible quandrangulations of the torus, Journal of Combinatorial Theory, vol. 67, 183–201, 1996.
[6] B. Elspas and J. Turner, Graphs with circulant adjacency matrices, Journal of
Combinatorial Theory, vol. 9, 297–307, 1970.
68
[7] E. B´ezout, Th´eorie g´en´erale des ´equations alg´ebriques, University of Lausanne, ´
Ph. D. Pierres, 1779.
[8] B. Bogstad and L. J. Cowen, The distinguishing number of the hypercube,
Discrete Mathematics, vol. 283, 29–35, 2004.
[9] B. L. Chen, K. W. Lih and P. L. Wu, Equitable Coloring and the maximum
degree, European Journal of Combinatorics, vol. 15, 443–447, 1994.
[10] C. H. Li, On isomorphisms of finite Cayley graphs a survey, Discrete Mathematics, vol. 256, 301–334, 2002.
[11] C. Delorme, O. Favaron and M. Mah´eo, Isomorphisms of Cayley multigraphs
of degree 4 on finite abelian groups, European Journal of Combinatorics, vol.
13, 59–61, 1992.
[12] C. Heuberger, On planarity and colorablity of circulant graphs, Discrete Mathematics, vol. 268, 153–169, 2003.
[13] H. Kierstead and A. V. Kostochka, Every 4-colorable graph with maximum
degree 4 has an equitable 4-coloring, Journal of Graph Theory, vol. 71, no. 1,
31–48, 2012.
[14] H. Furmanczyk, A. Jastrzebski and M. Kubale, Equitable coloring of graphs,
recent theoretical results and new practical algorithms, Archives of Control
Sciences, vol. 26, no. 3, 281–295, 2016.
[15] K. L. Collins and J. P. Hutchinson, Four-coloring six-regular graphs on the
torus, In Graph Coluring and Applications, vol. 23, 21–34,1999.
[16] K. W. Lih, Equitable coloring of graphs, Handbook of combinatorial optimization, Second edition, Panos M. Pardalos, Ding Zhu Du and Ronald L. Graham,
pp. 1199–1248, 2013.
[17] M. Muzychuk, On Ad´am’s conjecture for circulant graphs, Discrete Mathemat- ´
ics, vol. 176, 285–298, 1997.
69
[18] S. Nicoloso and U. Pietropaoli, Isomorphism testing for circulant graphs
Cn(a, b), Utilitas Mathematica, vol. 87, 165–182, 2010.
[19] T. Fukuda and S. Negami, The distinguish numbers of 4-regular quadrangulations on the torus, Yokohama Mathematical Journal, vol. 55, 47–70, 2009.
[20] W. Imrich, J. Jerebic and S. Klavˇzar, The distinguishing number of Cartesian
products of complete graphs, European Journal of Combinatorics, vol. 29, 922–
929, 2008.
[21] W. Imrich and S. Klavˇzar, Distinguishing Cartesian powers of graphs, Journal
of Graph Theory, vol. 53, no. 3, 250–260, 2006.
[22] W. Meyer, Equitable coloring, The American mathematical monthly, vol. 80,
920–922, 1973.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top