史納克圖形的有向圈雙重覆蓋及圓流數

淡江大學機構典藏 > 理學院 > 數學學系暨研究所 > 學位論文 > Item 987654321/101591

請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/101591

題名:	史納克圖形的有向圈雙重覆蓋及圓流數
其他題名:	Oriented circuit double cover and circular flow number of flower snark
作者:	王志維;Wang, Zhi-Wei
貢獻者:	淡江大學數學學系碩士班潘志實;Pan, Zhi-Shi
關鍵詞:	圈;史納克;圈雙重覆蓋;色數;circuit;snark;circuit double cover;colouring
日期:	2014
上傳時間:	2015-05-01 16:11:14 (UTC+8)
摘要:	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.
顯示於類別:	[數學學系暨研究所] 學位論文

文件中的檔案:

檔案	大小	格式	瀏覽次數
index.html	0Kb	HTML	163	檢視/開啟

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

TAIR相關文章

資料載入中.....