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

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)

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

(11)

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

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)