Grafos ORTH [h,s,t]
Autores
|
6618 |
6,2974
|
|
|
6619 |
6,2974
|
Informações:
Publicações do PESC
Grafos de interseção é um assunto que desperta grande interesse de pesquisadores da área de teoria dos grafos desde a década de 60. Nesta tese estudamos os grafos de interseção de subárvores de uma árvore.
Mais precisamente vamos apresentar resultados sobre a classe de grafos ORTH [h,s,t]. Os grafos que pertencem a esta classe são aqueles que admitem uma representação por interseção de subárvores de uma árvore hospedeira, na qual o grau máximo da árvore hospedeira é h, o grau máximo de qualquer subárvore é s, todas as folhas das subárvores também são folhas da árvore hospedeira e dois vértices são adjacentes no grafo se e somente se suas subárvores correspondentes possuem no mínimo t nós em comum e ao menos um destes nós é uma folha.
Resultados de representabilidade, não-representabilidade e complexidade para classes ORTH [h,s,t] com a variação do valores dos parâmetros h, s ou t estão presentes neste trabalho.
Intersection graphs are a topic that has attracted great interest from researchers in the area of graph theory since the 1960s. In this thesis we study the intersection graphs of subtrees of a tree.
More precisely we will present results on the class of graphs ORTH [h,s, t]. The graphs that belong to this class are those that admit a representation by intersection of subtrees of a host tree, in which the maximum degree of the host tree is h, the maximum degree of any subtree is s, all leaves of the subtree are also leaves of the host tree and two vertices are adjacent in the graph if and only if their corresponding subtrees have at least t nodes in common and at least one of these nodes is a leaf.
Results of representability, non-representability and complexity for classes ORTH [h,s,t] with the di erent values of the parameters h, s or t are present in this work.