淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0503201408093800
中文論文名稱 史納克圖形的有向圈雙重覆蓋及圓流數
英文論文名稱 Oriented circuit double cover and circular flow number of flower snark
校院名稱 淡江大學
系所名稱(中) 數學學系碩士班
系所名稱(英) Department of Mathematics
學年度 102
學期 1
出版年 103
研究生中文姓名 王志維
研究生英文姓名 Zhi-Wei Wang
學號 698190138
學位類別 碩士
語文別 中文
口試日期 2014-01-10
論文頁數 43頁
口試委員 指導教授-潘志實
委員-高金美
委員-張飛黃
中文關鍵字   史納克  圈雙重覆蓋  色數 
英文關鍵字 circuit  snark  circuit double cover  colouring 
學科別分類 學科別自然科學數學
中文摘要 C是G中的有向圈所形成的集合,其中C是G的有向圈雙重覆蓋,我們將
C當成頂點集合,記為I_C,如果|C∩C'|=k則我們稱C和C'這兩個有向圈為k-連通。
令ϕ^*_c(G)=min{χ_c(I_C)},其中ϕ_c^*(G)是所有有向圈雙重覆蓋著色數中最小的那個,非常容易證明對於所有的圖G,ϕ_c(G)<ϕ_c^*(G)。
同時我們也在此說明存在圖G使得ϕ_c(G)<ϕ_c^*(G)。
令J_(2k+1)是一個史納克圖形,頂點集合V(J_(2k+1) )={a_i,b_i,c_i,d_i:i=0,1,…,2k}
邊集合E(J_(2k+1) )={b_i a_i,b_i c_i,b_i d_i,a_i a_(i+1),c_i d_(i+1),d_i c_(i+1):i=0,1,…,2k},其中每一個索引要模2k+1。
在本篇論文中,我們證明了:
(1)If k≥1,then χ_c(I_C )≥5.
英文摘要 For a set C of directed crcuits of a graph G that form an oriented circuit double cover,we denote by I_C the graph with vertex set C,in which two circuits C and C' are connected by k edges if |C∩C'|=k.
Let ϕ^*_c (G)=min{χ_c(I_C)},where the minimum is taken over all the oriented circuit double covers of G,it is easy to show that for any graph G,ϕ_c(G)<ϕ^*_c (G).
We also show that there are graphs G for which ϕ_c (G)<ϕ^*_c (G).
Let J_(2k+1) be the flower snark which has vertex set V(J_(2k+1) )={a_i,b_i,c_i,d_i:i=0,1,…,2k}
and dege set E(J_(2k+1) )={b_i a_i,b_i c_i,b_i d_i,a_i a_(i+1),c_i d_(i+1),d_i c_(i+1):i=0,1,…,2k},where the summationin indices are modulo 2k+1.
In this thesis,we proved that
(1)If k≥1,then 〖 χ〗_c (I_C )≥5.
論文目次 目 錄

第一章:簡介..........................................1

第二章:主定理證明.....................................6

2.1:基本定義介紹及圈的性質...........................6

2.2:各類大圈的證明.................................14

參考文獻.............................................40

圖目錄

圖1 圖..................................................1
圖2 圖1的有向圖........................................1
圖3 P_4..................................................1
圖4 C_5(右:有向圈).......................................1
圖5 雙重圈覆蓋C={C_1,C_2,C_3,C_4 }..........................2
圖6 G_1:平面圖;G_2:非平面圖..............................2
圖7 左:χ_C(G)=5/2 右:Φ_C(G^* )=5/2..................2
圖8 J_9...................................................5
圖9 Flower snark(J_9)....................................6
圖10 Flower snark圖中的Y處..............................6
圖11 Flower snark圖中的H處..............................7
圖12 虛線:左、右(S型)皆為大圈 實線:小圈..................7
圖13 e無法被通過.........................................9
圖14 小圈不能同時在Y處回頭..............................10
圖15 C_1相交每個H_i兩次...................................16
圖16 C_1走S形,長度為1...................................16
圖17 S形內部小圈長度為六.................................16
圖18 S形兩側Y處.........................................17
圖19 小圈相交情況.......................................19
圖20 小圈相交大圈的情況.................................19
圖21 Y處有相異大圈相交..................................20
圖22 史納克圖形的轉換...................................22
圖23 圖22的圈相交圖....................................22
圖24 四個大圈相交情形...................................23
圖25 圈的交集圖.........................................23
圖26 兩個Y處有大圈相交..................................25
圖27 四個大圈中存在S形.................................26
圖28 圖27的圈相交圖....................................26
圖29 圖27的轉換........................................27
圖30 大圈一定要走Y處....................................28
圖31 兩個大圈和Y不相交..................................29
圖32 兩個大圈在Y處不對稱...............................30
圖33 兩大圈連續不相交...................................31
圖34 H處的奇、偶性質....................................31
圖35 S形內部............................................32
圖36 大圈相交的交集圖長相...............................33
圖37 S形的圈交集圖......................................33
圖38 圈交集圖間的相連...................................34
圖39 圈交集圖對應關係...................................34
圖40 圈交集圖對應關係...................................34
圖41 圈交集圖對應關係...................................34
圖42 與S形的對應關係...................................35
圖43 與S形的對應關係...................................35
圖44 S形與S形之間的對應關係............................35
圖45 S形之間對應關係....................................35
圖46 S形之間對應關係....................................35
圖47 兩個大圈...........................................37
圖49 圈的交集圖.........................................38

參考文獻 參考文獻
[01] D.Archdeacon,Face coloring of embedded graphs J.Graph Theory,8(1984),387-398.
[02] C.Chien and X.Zhu,The circular chromatic numbers of series-parallel graphs of large firth,J. Graph Theory,33(2000),185-198.
[03] L.A.Goddyn, M. Tarsi,and C.Q.Zhang,On(k,d)-colorings and fractionalNowhere-zero flows,J. Graph Theory,28(1998), 155-161.
[04] P. Hell and X. Zhu,The circular chromatic numbers of series-parallelgraphs,J. Graph Theory, 33(2000), 14-24.
[05] F. Jager,Flows and generalized coloring theorems in graphs,J. Combin. Theory Ser. B., 26(1979), 205-216.
[06] F. Jaeger,Nowhere zero flow problems,in Selected Topics in Graph Theory3, (L. W. Beineke and R. J. Wilson eds.), Academic Press,London,(1988), 71-95.
[07] J. C. Lagrrias,Number theory and dynamical systems,Proceedings of Symposiuin App. Math. Vol. 46(1992).
[08] S. Liaw, Z. Pan and X. Zhu,Construstion of K_n minor free graphs with given circular chromatic number,Discrete Mathematics, 263(2003), 191-206.
[ 09] R. Lukot’ka and M.Skoviera,k Real flow number and the cycle rank of a graph,J. Graph Theory 59(2008), 11-16.
[10] D. Moser,The star-chromatic number of planar graphs,J. Graph Theory 24(1997), 33-43
[11] Z. Pan and X. Zhu,Density of the circular chromatic number of series-parallel graphs,Journal of Graph Theory, 46(2004),57-68.
[12] Z. Pan and X. Zhu,Circular chromatic number of series-parallel graphs of large odd girth,Discrete Mathematics, 245(2002), 235-246.
[13] Z. Pan and X. Zhu,Construction of graph with given circular folw numbers,Journal of Graph Theory, 43(2003), 304-318.
[14] P. D. Seymour,Nowhere-zero 6-flows,J. Combinatorial Theory (B), 31(1981), 82-94.
[15] E. Steffen,The circular flow number of multigraphs,J. Graph Theory,36(2001)24-34.
[16] W. T. Tutte,On the embedding of linear graphs in surfaces,Proc.London Math. Soc., Ser. 2, 51(1949), 474-483.
[17] W. T. Tutte,A contribution on the theory of chromatic polynomial,Canad. J.Math., 6(1954), 80-91
[18] A. Vince,Star chromatic number,J. Graph Theory 12(1998), 551-559.
[19] C. Q. Zhang, Integer flows and cycle covers of graphs, Marcel Dekker, Inc. 1997.
[20] C. Q. Zhang,Circular flows od nearly eulerian graphs and vertex -splitting,manuscript, 2000.
[21] X. Zhu,A simple proof of Mower's theorem,J. Graph Theory, 30(1999),19-26.
[22] X. Zhu,Planar graphs with circular chromatic numbers between 3 and 4,J. Combin. Th.(B), 76(1999), 170-200.
[23] X. Zhu,Circular colouring and graph minors,Taiwanese Journal of Mathematics, 4(2000), 643-660.
[24] X. Zhu,Circular chromatic number,a survey,Discrete Mathematics, 229(2001), 371-410.
[25] Bulletin of the Institute of Mathematics Academia Sinica (New Series)Vol. 5 (2010), No. 4, pp. 349-368.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2014-03-05公開。
  • 同意授權瀏覽/列印電子全文服務,於2014-03-05起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信