臺灣博碩士論文加值系統

ㄧ個圖G的圈覆蓋(cycle cover)是收集一些G裡面的圈(cycle)，使得G裡面的邊都被覆蓋住(cover)。ㄧ個整數流(integer
flow)是在圖上賦予方向，且給定一個整數函數phi對應到G上所有的邊，使得對所有G裡的點v都滿足由v流出的量等於流入的量。
當所有的phi(e)，都滿足-k<phi(e)<k，則phi稱為一個k-整數流(k-flow)，如果對所有G上的邊，給的值都不為零，
則phi稱為處處不為零的k-整數流(nowhere-zero k-flow)。在這篇論文中，我們證明：如果Tutte的3-整數流猜測(Tutte's
3-flow conjecture)是對的，則當k是奇數時，對所有的(k-1)-邊連通圖滿足最小度數為k，會有一個處處不為零的6-整數流(6-flow)
phi，使得那些給定奇數值的邊數會大於等於(k-1)/k的總邊數，這會推得圖G有一個圈覆蓋最多只需要(13k+5)/(9k)的總邊數。
當k是偶數時，對所有的(k-1)-邊連通圖滿足最小度數為k，會有一個處處不為零的6-整數流(6-flow)
phi，使得那些給定奇數值的邊數會大於等於(k-2)/(k-1)的總邊數，這會推得圖G有一個圈覆蓋最多只需要(13k-8)/(9(k-1))的總邊數。

A cycle cover of a graph G is a collection of cycles of G which covers all edges of G. The size of a cycle cover is the sum of the lengths of the cycles in the cover. A flow in
G under orientation D is an integer-valued function on E(G) such that the output value is equal to the input value for each v in V(G). The support of ph(i) is defined by S(ph(i)) = {e in E(G) : phi(e) not equalto 0}. For a positive integer k, if −k < (e) < k for every e in E(G), then is called a k-flow, and furthermore, if S(phi) = E(G), then is called a nowhere-zero k-flow. In this thesis we prove: (1) if Tutte’s 3-Flow Conjecture is true, then every (k − 1)-edge-connected graph G with minimum degree = k has a nowhere-zero 6-flow such that when k is odd |Eodd(phi)| not less than (k-1)\k |E(G)| and when k is even |Eodd(phi)| not less than (k-2)\(k-1) |E(G)| ; (2) If a (k−1)-edge-connected graph G with minimum degree = k has a nowhere-zero 6-flow such that when k is odd |Eodd(phi)| not less than (k-1)\k |E(G)|, then G has a cycle cover in which the size of the cycle cover is at most (13k+5)\9k |E(G)| and when k is even |Eodd(phi)| not less than (k-2)\(k-1) |E(G)|, then G has a cycle cover in which the size of the cycle cover is at most (13k−8)\9(k−1) |E(G)|, where Eodd(phi)={e in E(G) : phi(e) is odd }.

Abstract (in Chinese) . . . . . . . . . . . . . . . . i
Abstract (in English) . . . . . . . . . . . . . . . . ii
Acknowledgement........................................iii
Contents . . . . . . . . . . . . . . . . . . . . . . .iv
1 Introduction and Preliminaries
1.1 Basic Notations . . . . . . . . . . . . . . . . . . . . . 1
1.2 Preliminaries . . .. . . . . . . . . . . . . . . 3
2 Known Results and Conjectures
2.1 Conjectures . . . . . . . . . . . . . . . . . . 9
2.2 Known results . . . . . . . . . . . . . . . . . . . . . . 11
3 Main Results and Conclusion
3.1 The Main Results . . . . . . .. . . . . . . . . . . . . . . . 14
3.2 Conclusion . . . . . . . .. . . . .. . . . . . . 26

[1] N. Alon, and M. Tarsi, Covering multigraphs by simple circuits, SIAM J. Algebraic
Discrete Methods 6 (1985) 345-350.
[2] J. Bang-Jensen and B. Toft, Unsolved problems presented at the Julius Petersen
Graph Theory Conference. Discrete Math. 101 (1992) 351-360.
[3] J. C. Bermond, B. Jackon, and F. Jaeger, Shortest covering of graphs with cycles,
J. Combin. Theory, Ser. B 35 (1983) 297-308.
[4] U. A. Celmins, ”On Cubic Graphs That Do Not Have an edge-3-coloring,”Ph.D.
thesis, University of Waterloo, Waterloo, 1984.
[5] J. Edmonds, Maximum matching and a polyhedron with (0, 1)−vertices, J. Res.
Nat. Bur. Standards B, 69 (1965) 125-130.
[6] G. Fan, Covering weighted graphs by even subgraphs, J. Combin. Theory, Ser.
B 49 (1990) 137-141.
[7] G. Fan, Integer flows and cycle covers, J. Combin. Theory, Ser. B 54 (1992)
113-122.
[8] G. Fan, Tutte’s 3-flow conjecture and short cycle covers, J. Combin. Theory, Ser.
B 57 (1993) 36-43.
[9] G. Fan, Circuit coverings of graphs and conjecture of Pyber, J. Combin. Theory,
Ser. B 65 (1995) 1-6.
[10] D. R. Fulkerson, Blocking and antiblocking pairs of polyhedra, Math. Programming
1 (1971), 168-194.
[11] L. Goddyn, Talk, Workshop on cycles and rays, Montr´eal, 1987.
[12] A. Itai, R. J. Lipton, C. H. Papadimitriou and M. Rodeh, Covering graphs with
simple circuits, SIAM J. Comput. 10 (1981) 746-750.
[13] F. Jaeger, On nowhere-zero flows in multigraphs, Congr. Number 15 (1975) 373-
378.
[14] F. Jaeger, Flows and generalized coloring theorems in graphs, J combin. Theory
Ser. B 26 (1979) 205-216.
[15] F. Jaeger, Nowhere-zero flow problems, in ”Selected Topics in Graph Theory 3”
(L. W. Beineke and R. J. Wilson, Eds.), pp. 71-95, Academic Press, London.
1988.
[16] U. Jamshy, A. Raspaud and M. Tarsi, Short circuit covers for regular matroids
with a nowhere-zero 5-flow, J combin. Theory Ser. B 43 (1987) 354-357.
[17] C. H. C. Little, W. T. Tutte and D. H. Younger, A theorem on integer flows,
unpublished manuscript.
[18] P. D. Seymour, Sums of circuits, in ”Graph Theory and Related Topics” (J. A.
Bondy and U. S. R. Murty, Eds.), pp. 341-355, Academic Press, New York, 1979.
[19] P. D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory, Ser. B 30 (1981) 130-
135.
[20] G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Austral. Math.
Soc. 8 (1973) 367-387.
[21] M. Tarsi, Nowhere zero flow and circuit covering in regular matroids, J. Combin.
Theory, Ser. B 39 (1985) 346-352.
[22] W. T. Tutte, A class of abelian groups, Canad. J. Math. 8 (1956) 13-28.
[23] D. B. West, Introduction to Graph Theory, Second Edition, Prentice Hall, Upper
Saddle River, 2001.
[24] D. H. Younger, Integer flows, J. Graph Theory 7 (1983), 349-357.
[25] C. Q. Zhang, Integer Flows and Cycle Covers of Graphs, Marcel Dekker, 1996.