Grafos Clique de Arestas
Autores
|
1845 |
410,6
|
|
|
1846 |
410,6
|
Informações:
Publicações do PESC
Título
Grafos Clique de Arestas
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
10/12/1999
Resumo
Dado um grafo G = (V,E), o grafo clique de arestas de G, denotado Ke(G), é o grafo com conjunto de vértices igual a E e tal que existe uma aresta entre dois vértices de Ke(G) se e somente se os extremos das arestas correspondentes em G estão em uma mesma clique. Um grafo G é grafo clique de arestas se existe um grafo H tal que G=Ke(H).
Examinamos, neste trabalho, tanto o operador clique de arestas quanto a classe de grafos por ele definida. Estudamos as propriedades básicas do operador e sua dinâmica. Apresentamos uma caracterização da classe dos grafos clique de arestas e investigamos sua relação com a classe dos grafos clique. Também estudamos problemas de caracterização associados à aplicação do operador clique de arestas a algumas classes de grafos. Finalmente, definimos e reconhecemos em tempo polinomial a classe dos grafos aresta-Helly.
Abstract
The edge clique graph Ke(G) is the one whose vertices correspond to the edges of G and where two vertces of Ke(G) are adjacent whenever the ends of the corresponding edges of G are in a common clique. A graph G is an edge clique graph if there is a graph H such that G = Ke(G).
We examine both the edge clique operator and the class of edge clique graphs. We consider some basic properties of the edge clique operator and its dynamics. We present a characterization of edge clique graphs and investigate the relationship between edge clique graphs and clique graphs. We also study the application of the operator to some special classes of graphs. Finally, we consider the edge-Helly graphs and give a polynomial algorithm to recognize them.
Arquivo