Covering 2-connected 3-regular graphs with disjoint paths

DOI10.1002/JGT.22219zbMATH Open1393.05218arXiv1806.07014OpenAlexW2963952043MaRDI QIDQ4581271FDOQ4581271

Authors: Gexin Yu 

Publication date: 16 August 2018

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

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.

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

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

zbMATH Keywords

path coverregular graphsdischarging

Mathematics Subject Classification ID

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

Cited In (11)

• On vertex-disjoint paths in regular graphs
• On the minimum leaf number of cubic graphs
• Embedding coverings of 2-paths with 3-paths
• Induced path factors of regular graphs
• A note on the path cover number of regular graphs
• On the path partition number of 6‐regular graphs
• Nontrivial path covers of graphs: existence, minimization and maximization
• Minimum path cover in quasi-claw-free graphs
• Covering the edges of a connected graph by paths
• On the path partition of graphs
• Ramsey-type results for path covers and path partitions

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)