On vertex-disjoint paths in regular graphs

zbMATH Open1391.05146arXiv1706.06945MaRDI QIDQ1753085FDOQ1753085

Authors: Jie Han 

Publication date: 25 May 2018

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

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.

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

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

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

zbMATH Keywords

pathsregular graphs

Mathematics Subject Classification ID

Paths and cycles (05C38)

Cites Work

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

Cited In (9)

• 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
• On the path partition of graphs
• Ramsey-type results for path covers and path partitions
• LATIN 2004: Theoretical Informatics

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)