Five‐cycle double cover and shortest cycle cover

The 5‐even subgraph cycle double cover conjecture (5‐CDC conjecture) asserts that every bridgeless graph has a 5‐even subgraph double cover. A shortest even subgraph cover of a graph G is a family of even subgraphs which cover all the edges of G and the sum of their lengths is minimum. It is conject...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2025-01, Vol.108 (1), p.39-49
Main Authors: Liu, Siyan, Hao, Rong‐Xia, Luo, Rong, Zhang, Cun‐Quan
Format: Article
Language:English
Subjects:
4‐even subgraph cover
4‐flow
Apexes
Graph theory
Graphs
oddness
shortest even subgraph cover
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The 5‐even subgraph cycle double cover conjecture (5‐CDC conjecture) asserts that every bridgeless graph has a 5‐even subgraph double cover. A shortest even subgraph cover of a graph G is a family of even subgraphs which cover all the edges of G and the sum of their lengths is minimum. It is conjectured that every bridgeless graph G has an even subgraph cover with total length at most 21 15 ∣ E ( G ) ∣. In this paper, we study those two conjectures for weak oddness 2 cubic graphs and present a sufficient condition for such graphs to have a 5‐CDC containing a member with many vertices. As a corollary, we show that for every oddness 2 cubic graph  G satisfying the sufficient condition has a 4‐even subgraph ( 1 , 2 )‐cover with total length at most 20 15 ∣ E ( G ) ∣ + 2. We also show that every oddness 2 cubic graph  G with girth at least 30 has a 5‐CDC containing a member of length at least 9 10 ∣ V ( G ) ∣ and thus it has a 4‐even subgraph ( 1 , 2 )‐cover with total length at most 21 15 ∣ E ( G ) ∣.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.23164