Grafos Equiestáveis e de Partição Geral
Autores
|
5608 |
2580,410
|
|
|
5615 |
2580,410
|
Informações:
Publicações do PESC
Um grafo é equiestável quando existe uma atribuição de números reais positivos aos seus vértices de forma que para todo conjunto independente maximal, e somente para esses conjuntos de vértices, a soma dos valores atribuídos aos vértices do conjunto somem 1. Por outro lado, um grafo é de partição geral se todas as suas arestas podem ser cobertas por cliques fortes.
Neste trabalho reunimos os principais resultados sobre grafos equiestáveis e de partição geral e desenvolvemos resultados envolvendo as classes dos grafos de partição geral, equiestáveis e triangulares. Em particular, mostramos que tanto a classe dos grafos de partição geral quanto a classe dos grafos triangulares são fechadas pelas operações de substituição e indução e contração de módulo, obtendo diversos resultados da literatura como corolários desses teoremas.
Além disso, ao caracterizar os grafos planares que são equiestáveis/de partição geral, generalizamos o resultado de Mahadev, Peled e Sun sobre os grafos outerplanares equiestáveis, respondendo também a uma questão em aberto proposta por Anbeek, DeTemple, McAvaney e Robertson em 1997.
A graph is equistable when there is a real positive attribution to the vertices of the graph such that among all the subsets of vertices, for all maximal independent sets, and only for them, the sum of the values assigned to each vertex is equal to 1. On the other hand, a general partition graph is a graph whose edges are covered by strong cliques.
In this work, we did a survey on equistable and general partition graphs and developed results concerning the equistable, general partition and triangle classes. In particular, we showed that the general partition and triangle classes are both closed under the operations of substitution and inducing and contraction of modules, which turned several results into corollaries of these theorems.
Moreover, by characterizing the planar graphs that are equistable/general partition graphs, we generalized Mahadev, Peled and Sun result on equistable outerplanar graphs and solved an open question proposed by Anbeek, DeTemple, McAvaney and Robertson in 1997.