Busca avançada
Ano de início
Entree

Decomposições de grafos

Processo: 14/01460-8
Linha de fomento:Bolsas no Exterior - Estágio de Pesquisa - Doutorado
Vigência (Início): 04 de abril de 2014
Vigência (Término): 03 de abril de 2015
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Yoshiko Wakabayashi
Beneficiário:Fábio Happ Botler
Supervisor no Exterior: Cun-Quan Zhang
Instituição-sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
Local de pesquisa : West Virginia University (WVU), Estados Unidos  
Vinculado à bolsa:11/08033-0 - Decomposição de um grafo em caminhos: aspectos estruturais e algorítmicos, BP.DR
Assunto(s):Teoria dos grafos

Resumo

Um grafo G é um par (V,E), onde V é um conjunto finito e E é um conjunto de pares de elementos distintos de V. Os elementos de V são chamados vértices, e os elementos de E são chamados arestas. Dado um grafo G = (V,E), uma decomposição de G é um conjunto de subgrafos aresta-disjuntos de G que cobrem E. Se D = {H_1,...,H_k} é uma decomposição de G tal que H_i é um caminho para todo i em {1,...,k}, dizemos que D é uma decomposição por caminhos.Dizemos que uma decomposição por caminhos de um grafo G é mínima se para toda decomposição por caminhos D' de G, temos que |D'|>=|D|. O path number de um grafo G é o tamanho de uma decomposição por caminhos mínima. Denotamos o path number de G por pn(G). De acordo com Lovász (1968), em 1966, Erdös perguntou sobre este parâmetro, e Gallai estabeleceu a seguinte conjectura. Conjectura (Gallai, 1966). Se G = (V,E) é um grafo conexo com n vértices, então pn(G) <= (n+1)/2.Esse parâmetro não é conhecido para a maioria das classes de grafos. Lovász (1968) encontrou um limitante superior para um parâmetro similar, o tamanho de uma decomposição mínima em caminhos e circuitos.Teorema (Lovász, 1968). Todo grafo conexo com n vértices pode ser decomposto em no máximo n/2 caminhos e circuitos.Nosso plano é investigar a conjectura de Gallai, o path number de classes especiais de grafos, e tópicos relacionados. Sabemos que essa conjectura é verdadeira para várias classes de grafos, mas isso ainda não foi determinado para classes de grafos como grafos com grau máximo 4, grafos 2k-regulares, grafos cordais, ou grafos planares.Nós também estamos interessados no aspecto algorítmico do problema de encontrar uma decomposição por caminhos mínima de um grafo. Não foram encontrados resultados relacionados a este tópico, diferentemente do caso em que se busca caminhos disjuntos nos vértices. Deste ponto de vista estamos interessados em algoritmos de aproximação.O estudo desse tema justifica-se pela sua releância: um problema clássico, de grande interesse na área de grafos. Em se tratando de uma conjectura que está aberta há quase meio século, seria muita pretensão ter como objetivo estabelecer de vez a sua validade ou não. Temos porém a certeza de que um estudo dessa natureza irá dar ao aluno a oportunidade de aprender técnicas de provas e entender onde reside a dificuldade do problema. (AU)

Publicações científicas (6)
(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)
BOTLER, F.; MOTA, G. O.; OSHIRO, M. T. I.; WAKABAYASHI, Y. Decomposing highly connected graphs into paths of length five. DISCRETE APPLIED MATHEMATICS, v. 245, n. SI, p. 128-138, AUG 20 2018. Citações Web of Science: 1.
BOTLER, F.; MOTA, G. O.; OSHIRO, M. T. I.; WAKABAYASHI, Y. Decomposing regular graphs with prescribed girth into paths of given length. EUROPEAN JOURNAL OF COMBINATORICS, v. 66, p. 28-36, DEC 2017. Citações Web of Science: 0.
BOTLER, F.; TALON, A. Decomposing 8-regular graphs into paths of length 4. DISCRETE MATHEMATICS, v. 340, n. 9, p. 2275-2285, SEP 2017. Citações Web of Science: 1.
BOTLER, FABIO; JIMENEZ, ANDREA. On path decompositions of 2k-regular graphs. DISCRETE MATHEMATICS, v. 340, n. 6, p. 1405-1411, JUN 2017. Citações Web of Science: 5.
BOTLER, F.; MOTA, G. O.; OSHIRO, M. T. I.; WAKABAYASHI, Y. Decomposing highly edge-connected graphs into paths of any given length. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 122, p. 508-542, JAN 2017. Citações Web of Science: 7.
BOTLER, F.; MOTA, G. O.; WAKABAYASHI, Y. Decompositions of triangle-free 5-regular graphs into paths of length five. DISCRETE MATHEMATICS, v. 338, n. 11, p. 1845-1855, NOV 6 2015. Citações Web of Science: 4.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.