# 臺灣博碩士論文加值系統

(44.192.254.59) 您好！臺灣時間：2023/01/27 19:58

:::

### 詳目顯示

:

• 被引用:0
• 點閱:70
• 評分:
• 下載:1
• 書目收藏:0
 一個圖由頂點集與邊集構成。若存在頂點集間的映射保持相鄰關係，則我們稱兩個圖同構。一個平移環面網格可以看作是環面的四邊形分割。一個循環圖的點集是Ｚｎ，且若兩個頂點的差在某個給定差集裡則相鄰。亞當猜想宣稱兩個循環圖同構，若且唯若他們的給定差集相差一個與ｎ互質的倍數。一個圖的均勻著色是一個圖著色使得每種顏色的用量至多差１。一個圖的辨識數是最少能使用多少種標記，使得唯一能保持標記的自圖同構映射只有恆等映射。在這篇論文中，我們找尋關於平移環面網格之間圖同構的充分必要條件，並刻畫他們之間所有的圖同構映射。在應用上我們給另一個亞當猜想在度數小於等於４的證明，並給出二分圖平移環面網格能否均勻著色，以及平移環面網格的辨識數。
 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 thetorus and a circulant graph is the graph with vertex set Zn and two vertices u and vare 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 multipliedby an integer coprime to n. An equitable coloring is a graph coloring which thenumbers 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 thatthe identity map is the unique graph automorphism of preserving the labeling. Inthis thesis we find the necessary and sufficient condition for the graph isomorphismof shifted toroidal grids and characterize all graph isomorphisms. As applicationwe 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 shiftedtoroidal grids, and we provide the exact values of the distinguishing numbers forshifted toroidal grids.
 Abstract iContent iiiList of Tables ivList of Figures iv1 Introduction 11.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Shifted toroidal grid . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3 Circulant graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.4 Equitable coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5 Distinguishing number . . . . . . . . . . . . . . . . . . . . . . . . . 71.6 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.7 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Preliminaries 123 Graph isomorphism between shifted toroidal grids 153.1 Straight cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15ii3.2 Shifted toroidal grids with straight cycles . . . . . . . . . . . . . . . 183.3 Shifted toroidal grids with no straight cycles . . . . . . . . . . . . . 213.4 Main result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254 Shifted toroidal grids which are graph isomorphic to circulantgraphs and it’s application on Ad´am’s Conjecture. 37 ´4.1 Shifted toroidal grids which are graph isomorphic to circulant graphs 374.2 Applications on Ad´am’s conjecture for circulant graphs ´ Cn(a, b) . . 404.3 Ad´am’s conjecture on ´ Cn(a, b, a + b) . . . . . . . . . . . . . . . . . . 425 Equitable coloring of shifted toroidal grids 476 Distinguish number of shifted toroidal grids 627 Discussion 667.1 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 667.2 Future works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67References 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 combinatorialtheory 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 ofCombinatorial 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 maximumdegree, 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 multigraphsof 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 maximumdegree 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 ControlSciences, vol. 26, no. 3, 281–295, 2016.[15] K. L. Collins and J. P. Hutchinson, Four-coloring six-regular graphs on thetorus, 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 graphsCn(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 Cartesianproducts of complete graphs, European Journal of Combinatorics, vol. 29, 922–929, 2008.[21] W. Imrich and S. Klavˇzar, Distinguishing Cartesian powers of graphs, Journalof Graph Theory, vol. 53, no. 3, 250–260, 2006.[22] W. Meyer, Equitable coloring, The American mathematical monthly, vol. 80,920–922, 1973.
 電子全文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 p類型Banach空間中逐行獨立的隨機元素陣列的完全收斂性質之研究 2 利用深度學習中的轉移學習來處理錯誤標記的數據 3 以集合為索引的隨機集合部分和的強大數法則 4 吳青峰歌詞中關於愛情的認知隱喻探究 5 模型式空間的維度與斯特姆界限 6 類別層級之關節式形變類神經輻射場 7 適用於快速圖像處理之具記憶體效率分組排序膨脹卷積引擎 8 記憶體內運算之內建自測試與內建自修正策略 9 應用於密集物件偵測之具距離周長比值函數低複雜度非極大值抑制引擎 10 應用於光學雷達之電磁驅動壓阻感測CMOS掃描鏡 11 適用於太赫茲單像素成像系統之兩階段適應式壓縮感測與訊號重建演算法 12 一個低位寬高面積效率深度學習加速器及其軟體硬體聯合設計和模型量化方法 13 混合積分梯度法視覺化解釋輕量級深度卷積神經網路針對秀麗隱桿線蟲顯微影像日齡估測 14 半導體高分子奈米粒子於光催化水分解產氫之發展 15 運用CRISPR活化系統用於調控脂肪幹細胞內長鏈非編碼核糖核酸及改促進骨再生

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室