Bound on shortest cycle covers
Deping Song, Xuding Zhu · 2024
Read Bound on shortest cycle covers by Deping Song, Xuding Zhu (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-20874.txt.
Description
Abstract . Assume G G is a bridgeless graph. A cycle cover of G G is a collection of cycles of G G such that each edge of G G is contained in at least one of the cycles. The length of a cycle cover of G G is the sum of the lengths of the cycles in the cover.
Catalog record
| CREATOR | Deping Song, Xuding Zhu |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-20874
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bound on shortest cycle covers Deping Song, Xuding Zhu Abstract . Assume G G is a bridgeless graph. A cycle cover of G G is a collection of cycles of G G such that each edge of G G is contained in at least one of the cycles. The length of a cycle cover of G G is the sum of the lengths of the cycles in the cover. The minimum length of a cycle cover of G G is denoted by c c ( G ) cc(G) . It was proved independently by Alon and Tarsi and by Bermond, Jackson, and Jaeger that c c ( G ) ≤ 5 3 m cc(G)\leq\frac{5}{3}m for every bridgeless graph G G with m m edges. This remained the best-known upper bound for c c ( G ) cc(G) for 40 years. In this paper, we prove that if G G is a bridgeless graph with m m edges and n 2 n_{2} vertices of degree 2 2 , then c c ( G ) < 29 18 m + 1 18 n 2 cc(G)<\frac{29}{18}m+\frac{1}{18}n_{2} . As a consequence, we show that c c ( G ) ≤ 5 3 m − 1 42 log m cc(G)\leq\frac{5}{3}m-\frac{1}{42}\log m . The upper bound c c ( G ) < 29 18 m ≈ 1.6111 m cc(G)<\frac{29}{18}m\approx 1.6111m for bridgeless graphs G G of minimum degree at least 3 improves the previous known upper bound 1.6258 m 1.6258m . A key lemma used in the proof confirms Fan’s conjecture that if C C is a circuit of G G and G / C G/C admits a nowhere zero 4-flow, then G G admits a 4-flow f f such that E ( G ) − E ( C ) ⊆ supp ( f ) E(G)-E(C)\subseteq\text{supp}(f) and | supp ( f ) ∩ E ( C ) | > 3 4 | E ( C ) | |\textrm{supp}(f)\cap E(C)|>\frac{3}{4}|E(C)| . 1. Introduction Graphs considered in this paper may have loops and multiple edges. For terminology and notations not defined here, we follow [ 3 , 19 ] . Contracting an edge means deleting the edge and then identifying its ends. For a subgraph H of a graph G , let G/H be the graph obtained from G by contracting all edges of H . A circuit is a 2 -regular connected graph, and a cycle is a graph such that the degree of each vertex is even. The length of a cycle or a circuit is the number of its edges. A collection \mathcal{C} of cycles of a graph G covers G if each edge of G is contained in at least one cycle in \mathcal{C} . The length of a cycle cover \mathcal{C} , denoted by \ell(\mathcal{C}) , is the sum of the lengths of its cycles. The length of the shortest cycle cover of G is denoted by cc(G) . Alon and Tarsi [ 1 ] conjectured that cc(G)\leq\frac{7}{5}m for every bridgeless graph G with m edges. Jamshy and Tarsi [ 10 ] proved that Alon and Tarsi’s conjecture implies the well-known cycle double cover conjecture of Seymour [ 14 ] and Szekeres [ 16 ] , that every bridgeless graph has a collection of cycles that covers each edge exactly twice. Alon and Tarsi [ 1 ] and Bermond, Jackson, and Jaeger [ 2 ] independently proved that cc(G)\leq\frac{5}{3}m for every bridgeless graph G with m edges. This upper bound on cc(G) remained the best known upper bound for 40 years. For special families of graphs, there are some better upper bounds proved in the literature. Jamshy, Raspaud, and Tarsi [ 9 ] proved that if G admits a nowhere-zero 5-flow, then cc(G)\leq\frac{8}{5}m . Fan and Raspaud [ 6 ] proved that if the Fulkerson Conjecture is true, then cc(G)\leq\frac{22}{15}m . Kaiser, Král, Lidický, Nejedlý and Šámal [ 11 ] proved that if G has minimum degree at least 3 and is loopless, then cc(G)\leq\frac{44}{27}m . Fan [ 5 ] proved that if G has minimum degree at least 3, then cc(G)<\frac{218}{135}m in the loopless case and cc(G)<\frac{278}{171}m if loops are allowed. Kompišová and Lukot’ka [ 13 ] proved that cc(G)<\frac{278}{171}m+\frac{2}{27}n_{2} for an arbitrary bridgeless graph G , where n_{2} is the number of degree 2 vertices in G . This paper proves that cc(G)<\frac{29}{18}m+\frac{1}{18}n_{2} . As a consequence, we show that cc(G)\leq\frac{5}{3}m-\frac{1}{42}\log m , which improves the general upper bound for cc(G) by a fraction of \log m . Let G be a graph and \Gamma be an (additive) abelian group. For an orientation D of E(G) , denote E^{+}(v) (resp., E^{-}(v) ) by the set of all oriented edges of D(G) with their tails (resp., heads) at vertex v\in V(G) . For a function f:E(G)\to\Gamma and v\in V(G) , let f^{+}(v)=\sum_{e\in E^{+}(v)}f(e) and f^{-}(v)=\sum_{e\in E^{-}(v)}f(e) . A \Gamma -flow in G is an ordered pair (D,f) such that f^{+}(v)-f^{-}(v)=0 for every vertex v\in V(G) . For a subgraph H of G and a\in\Gamma , define E_{f=a}(H)=\left\{e\in E(H):f(e)=a\right\} . The support of f is the set of all edges of G with f(e)\neq 0 and is denoted by supp(f) . A flow (D,f) is called nowhere-zero if supp(f)=E(G) . We shall consider \mathbb{Z}_{2}\times\mathbb{Z}_{2} -flows in this paper. As -\alpha=\alpha for all \alpha\in\mathbb{Z}_{2}\times\mathbb{Z}_{2} , the orientation of G is irrelevant and can be omitted. To be precise, a Z_{2}\times Z_{2} -flow on G is a function f:E(G)\to Z_{2}\times Z_{2} such that for each vertex v , \sum_{e\in E(v)}f(e)=0 , where E(v) is the set of edges of G incident to v . 2. A key Lemma A maximal path P in a graph H with all interior vertices of degree 2 (in H ) is called a thread in H . This section proves the following lemma. Lemma 2.1 . Assume G is a graph and C is a circuit in G . Assume each edge in C is contained in a thread of G of length at least q . If G admits a \mathbb{Z}_{2}\times\mathbb{Z}_{2} -flow f , then G admits a \mathbb{Z}_{2}\times\mathbb{Z}_{2} -flow g such that {\rm supp}(f)-C={\rm supp}(g)-C and |E_{g=(0,0)}(C)|\leq\frac{1}{4}(|E(C)|-q) . Proof. Assume f is a \mathbb{Z}_{2}\times\mathbb{Z}_{2} -flow on G and C is a circuit. A subpath S of C is an f_{(0,0),(1,1)} - segment in C if f(e)\in\{(0,0),(1,1)\} for each edge e\in S . We choose f and S in such a way that for any \mathbb{Z}_{2}\times\mathbb{Z}_{2} -flow g with {\rm supp}(f)-C={\rm supp}(g)-C , and any g_{(0,0),(1,1)} -segment S^{\prime} in C , |S^{\prime}|\leq|S| . For a\in\mathbb{Z}_{2}\times\mathbb{Z}_{2} and cycle C^{\prime} , let f_{C^{\prime},a} be the function defined as f_{C^{\prime},a}(e)=a if e\in E(C^{\prime}) , and f_{C^{\prime},a}(e)=0 for other edges e . Then f_{C^{\prime},a} is a \mathbb{Z}_{2}\times\mathbb{Z}_{2} -flow with {\rm supp}(f_{C^{\prime},a})=E(C^{\prime}) . If S=C , then let g=f+f_{C,(0,1)} . Then g is a Z_{2}\times\mathbb{Z}_{2} -flow on G with {\rm supp}(f)-C={\rm supp}(g)-C , and E_{g=(0,0)}(C)=\emptyset . Thus, we may assume that S\neq C . Assume S=v_{1}v_{2}\cdots v_{s+1} , and C=(v_{1}v_{2}\ldots v_{p}) (so the other neighbor of v_{1} in C is v_{p} ). Considering f or