Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

On vertex-disjoint paths in regular graphs

Autor(es):
Han, Jie
Número total de Autores: 1
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
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 14/18641-5 - Circuitos Hamiltonianos e problemas de ladrilhamento em hipergrafos
Beneficiário:Jie Han
Linha de fomento: Bolsas no Brasil - Pós-Doutorado