On vertex-disjoint paths in regular graphs

Autor(es)

Han, Jie

• Tipo de documento: Artigo Científico
• Fonte: ELECTRONIC JOURNAL OF COMBINATORICS; v. 25, n. 2 APR 27 2018.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 14/18641-5 - Circuitos hamiltonianos e problemas de ladrilhamento em hipergrafos
• Beneficiário: Jie Han
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado