Propriedades Estruturais dos Grafos Cordais Comparabilidade
Autores
|
7505 |
3248,410
|
|
|
7506 |
3248,410
|
Informações:
Publicações do PESC
Um grafo G é cordal se todo ciclo de tamanho pelo menos 4 em G possui uma corda; é de comparabilidade se admite orientação transitiva de suas arestas; e é cordal comparabilidade se é simultaneamente cordal e de comparabilidade. Neste texto, revisamos alguns resultados estruturais sobre os grafos cordais comparabilidade e apresentamos alguns novos resultados. A saber, mostramos que a classe dos grafos cordais comparabilidade é uma classe de interseção, definindo uma classe de famílias de subárvores T tal que os grafos cordais comparabilidade são os grafos de interseção de T. Provamos a inexistência de um limite superior para o grau máximo de árvores características dos grafos cordais comparabilidade. Mais especificamente, provamos que, para todo n maior ou igual a 3, existe um grafo cordal comparabilidade RSn tal que sua árvore característica é única e isomorfa a estrela com n folhas. Finalmente, provamos que a dimensão linear dos grafos split comparabilidade, uma subclasse dos grafos cordais comparabilidade, é menor ou igual a 3.
A graph G is chordal if every cycle of size at least 4 in G has a chord; it is comparability graph if its admits a transitive orientation of its edges; and it is a chordal comparability graph if it is both a chordal graph and a comparability graph. In this text, we review some structural results about chordal comparability graphs and present some new results. Namely, we show that the class of chordal comparability graphs is an intersection class, by defining a class of families of subtrees T such that the chordal comparability graphs are the intersection graphs of T. We prove the non-existence of an upper bound for the maximum degree of clique trees of chordal comparability graphs. More specifically, we prove that for all n greater than or equal to 3 there exists a chordal comparability graph RSn such that its clique tree is unique and isomorphic to the star with n leaves. Finally, we prove that the linear dimension of the split comparability graphs is less than or equal to 3.