• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
10.11606/D.45.2014.tde-03022015-115100
Documento
Autor
Nome completo
Renzo Gonzalo Gómez Diaz
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2014
Orientador
Banca examinadora
Wakabayashi, Yoshiko (Presidente)
Lee, Orlando
Vélez, César Israel Hernández
Título em português
Empacotamento de árvores em grafos completos
Palavras-chave em português
biestrelas
decomposição em árvores
empacotamento de árvores
estrelas
grafo completo
grafo k-cromático
Resumo em português
Nesta dissertacao estudamos problemas de empacotamento de arvores em grafos, com enfase no caso de grafos completos. Denotamos por Ti uma arvore de ordem i. Dizemos que existe um empacotamento de arvores T1, . . . , Tn num grafo G se e possivel encontrar em G subgrafos H1, . . . , Hn, dois a dois disjuntos nas arestas, tais que Hi e isomorfo a Ti. Em 1976, A. Gyarfas e J. Lehel levantaram a seguinte questao, que conjecturaram ter uma resposta positiva: e possivel empaco- tar qualquer sequencia de arvores T1, . . . , Tn no Kn? Esta dissertacao tem como tema principal os estudos realizados por diversos pesquisadores na busca de uma resposta para esta pergunta, que permanece ainda em aberto. Tendo em vista a dificuldade para tratar esta questao, surge natural- mente a pergunta sobre a existencia de classes de arvores para as quais a resposta e afirmativa. Nessa linha, existem diversos resultados positivos, como por exemplo quando queremos empacotar estrelas e caminhos, ou estrelas e biestrelas. Por outro lado, em vez de restringir a classe das arvores, faz sentido restringir o tamanho da sequencia e reformular a pergunta. Por exemplo, dado s < n, e possivel empacotar qualquer sequencia de arvores T1, . . . , Ts no Kn? Em 1983, Bollobas mostrou ? que a resposta e afirmativa se s <= n / sqrt(2). Na primeira parte deste trabalho focamos nosso estudo em questoes desse tipo. Na segunda parte desta dissertacao investigamos algumas conjecturas que foram motivadas pela pergunta levantada por Gyarfas & Lehel. Por exemplo, Hobbs, Bourgeois e Kasiraj formularam a seguinte questao: para n par, e possivel empacotar qualquer sequencia de arvores T1, . . . , Tn no grafo bipartido Kn/2,n-1? Para essa pergunta apresentamos alguns resultados conhecidos analogos aos obtidos para a conjectura de Gyarfas & Lehel. Mais recentemente, Gerbner, Keszegh e Palmer estudaram a seguinte generalizacao da conjectura original: e possivel empacotar qualquer sequencia de arvores T1, . . . , Tk num grafo k-cromatico? Neste trabalho estudamos essas e outras questoes relacionadas e apresentamos os principais resultados que encontramos na literatura.
Título em inglês
Packing trees into complete graphs
Palavras-chave em inglês
bistars
complete graph
decomposition into trees
k-chromatic graph
packing of trees
stars
Resumo em inglês
In this dissertation we address the problem of packing trees into graphs, with focus on complete graphs. We denote by Ti a tree of order i. We say that there exists a packing of trees T1,...,Tn in a graph G if its possible to find in G pairwise edge-disjoint subgraphs H1, . . . , Hn such that Hi is isomorphic to Ti. In 1976, A. Gyárfás and J. Lehel raised the following question, that they conjectured to have an affirmative answer: is it possible to pack any sequence of trees T1, . . . , Tn into the complete graph Kn? In this dissertation, we study a number of contributions made by various researchers in the search for an answer to this question, that is still open. In view of the difficulty of this question, it is natural to look for the existence of classes of trees for which the answer is affirmative. In this direction, some positive results have been found, as for example, when the sequences of trees are restricted to stars and paths, or stars and bistars. On the other hand, instead of restricting the classes of trees, it makes sense to restrict the length of the sequence and reformulate the question. For example, given s < n, is it possible to pack any sequence of trees T1, . . . , Ts into Kn? In 1983, Bollobás showed that the answer is affirmative if s <= n/sqrt(2). In the first part of this work, we focus on such kind of questions. In the second part of this dissertation we investigate some other conjectures that were motivated by the conjecture of Gyárfás & Lehel. For example, Hobbs, Bourgeois and Kasiraj formulated the following question: For n even, is it possible to pack any sequence of trees T1, . . . , Tn into the complete bipartite graph Kn/2,n-1? For this question, we present some known results analogous to those obtained for the conjecture of Gyárfás & Lehel. More recently, Gerbner, Keszegh and Palmer studied the following generalization of the of former conjecture: is it possible to pack any sequence of trees T1,...,Tk in a k-chromatic graph? In this dissertation, we study this and other related questions and present the main results we found in the literature.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
dissertacao_Renzo.pdf (808.06 Kbytes)
Data de Publicação
2015-02-04
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2018. Todos os direitos reservados.