Oriented circuit double cover and circular flow and colouring

淡江大學機構典藏 > 理學院 > 應用數學與數據科學學系 > 期刊論文 > Item 987654321/56753

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

題名:	Oriented circuit double cover and circular flow and colouring
作者:	潘志實;Pan, Zhi-shi;朱緒鼎;Zhu, Xu-ding
貢獻者:	淡江大學數學學系
關鍵詞:	Circuit double cover;Circular flow number;Edge rooted graph;Flow;Graph;Parallel join;Series join
日期:	2010-12
上傳時間:	2011-09-07 11:57:42 (UTC+8)
出版者:	Taipei: Institute of Mathematics, Academia Sinica
摘要:	For a set C of directed circuits of a graph G that form an oriented circuit double cover, we denote by IC 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(IC), 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). On the other hand, it follows from well-known results that for any integer 2 ≤ k ≤ 4, Φ∗c (G) ≤ k if and only if Φc(G) ≤ k; for any integer k ≥ 1, Φ∗c (G) ≤ 2 + 1 k if and only if Φc(G) ≤ 2 + 1 k. This papers proves that for any rational number 2 ≤ r ≤ 5 there exists a graph G for which Φ∗c (G) = Φc(G) = r. We also show that there are graphs G for which Φc(G) < Φ∗c (G).
關聯:	Bulletin of the Institute of Mathematics Academia Sinica New Series 5(4), pp.349-368
顯示於類別:	[應用數學與數據科學學系] 期刊論文

文件中的檔案:

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

TAIR相關文章