On vertex-disjoint paths in regular graphs

MaRDI QIDQ1753085zbMATH OpenFDO

Authors Jie Han

Publication date 25 May 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.06945, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p12

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

pathsregular graphs

Mathematics Subject Classification ID

Paths and cycles (05C38)

Abstract: Let $cin(0,1]$ be a real number and let $n$ be a sufficiently large integer. We prove that every $n$-vertex $cn$-regular graph $G$ contains a collection of $lfloor1/cfloor$ paths whose union covers all but at most $o(n)$ vertices of $G$. The constant $lfloor1/cfloor$ is best possible when $1/cotinmathbbN$ and off by $1$ otherwise. Moreover, if in addition $G$ is bipartite, then the number of paths can be reduced to $lfloor1/(2c)floor$, which is best possible.

Recommendations

• Cycle partitions of regular graphs
• scientific article; zbMATH DE number 2188351
• Covering 2-connected 3-regular graphs with disjoint paths
• A note on the path cover number of regular graphs
• Packings in Dense Regular Graphs

Cites work

• scientific article; zbMATH DE number 6116733 (Why is no real title available?)
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A note on the path cover number of regular graphs
• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• Arc coverings of graphs
• Blow-up lemma
• Paths, Stars and the Number Three
• Some Theorems on Abstract Graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Variations on the Gallai-Milgram theorem

Cited in

(10)

• LATIN 2004: Theoretical Informatics
• Cycle partitions of regular graphs
• A note on the path cover number of regular graphs
• A Hall-type condition for path covers in bipartite graphs
• Vertex-disjoint paths and edge-disjoint branchings in directed graphs
• Short paths in \(\varepsilon \)-regular pairs and small diameter decompositions of dense graphs
• On the fastest moving off from a vertex in directed regular graphs
• Covering 2-connected 3-regular graphs with disjoint paths
• On the path partition of graphs
• Ramsey-type results for path covers and path partitions

This page was built for publication: On vertex-disjoint paths in regular graphs

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