Covering 2-connected 3-regular graphs with disjoint paths

DOI10.1002/JGT.22219MaRDI QIDQ4581271zbMATH OpenOpenAlexFDO

Authors Gexin Yu

Publication date 16 August 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.07014

zbMATH Keywords

dischargingpath coverregular graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A path cover of a graph is a set of disjoint paths so that every vertex in the graph is contained in one of the paths. The path cover number $p(G)$ of graph $G$ is the cardinality of a path cover with the minimum number of paths. Reed in 1996 conjectured that a $2$-connected $3$-regular graph has path cover number at most $lceiln/10ceil$. In this paper, we confirm this conjecture.

Recommendations

• A note on the path cover number of regular graphs
• On vertex-disjoint paths in regular graphs
• Perfect path double covers of graphs
• Subgraph coverings and edge switchings
• Covering the edges of a connected graph by paths

Cited in

(14)

• On vertex-disjoint paths in regular graphs
• Embedding coverings of 2-paths with 3-paths
• Covering the edges of a connected graph by paths
• Ramsey-type results for path covers and path partitions
• Nontrivial path covers of graphs: existence, minimization and maximization
• On the minimum leaf number of cubic graphs
• A note on the path cover number of regular graphs
• Induced path factors of regular graphs
• On the path partition number of 6‐regular graphs
• On the path partition of graphs
• An upper bound on path cover number of regular graphs and its application to Hamiltonian cycle in tough graphs
• Cycle partitions in dense regular digraphs and oriented graphs
• Degree conditions for disjoint path covers in digraphs
• Minimum path cover in quasi-claw-free graphs

This page was built for publication: Covering 2-connected 3-regular graphs with disjoint paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4581271)