On vertex-disjoint paths in regular graphs

Author(s)

Han, Jie

• Document type: Journal article
• Source: ELECTRONIC JOURNAL OF COMBINATORICS; v. 25, n. 2 APR 27 2018.
• Web of Science Citations: 0

Abstract

Let c is an element of (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 {[}1/c] paths whose union covers all but at most o(n) vertices of G. The constant {[}1/c] is best possible when 1/c is not an element of N and off by 1 otherwise. Moreover, if in addition G is bipartite, then the number of paths can be reduced to {[}1/(2c)] , which is best possible. (AU)

• FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
• Grantee: Carlos Eduardo Ferreira
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 14/18641-5 - Hamilton cycles and tiling problems in hypergraphs
• Grantee: Jie Han
• Support Opportunities: Scholarships in Brazil - Post-Doctoral