圖的圈覆蓋

Abstract

ㄧ個圖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 }.