Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/2658
Tipo: Relatório
Título: Edge clique graphs and some classes of chordal graphs
Autor(es)/Inventor(es): Cerioli, Márcia Rosana
Szwarcfiter, Jayme Luiz
Resumo : The edge clique graph of a graph G is one having as vertices the edges of G, two vertices being adjacent if the corresponding edges of G belong to a common clique. This class of graphs has been introduced by Albertson and Collins (1984). Although many interesting properties of it have been since studied, we do not know complete characterizations of edge clique graphs of any non trivial class of graphs. In this paper, we describe characterizations relative to edge clique graphs and some classes of chordal graphs, such as starlike, starlikethreshold, split and threshold graphs. In special, a known necessary condition for a graph to be an edge clique graph is that the sizes of all maximal cliques and intersections of ma.ximal cliques ought to be triangular numbers. We show that this condition is also suflicient for starlike-threshold graphs.
Palavras-chave: Grafos cordal
Margens de grafos clique
Chordal graphs
Edge clique graphs
split graphs
Assunto CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
Departamento: Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Número: 2199
Data de publicação: 31-Dez-1999
País de publicação: Brasil
Idioma da publicação: eng
Tipo de acesso: Acesso Aberto
Citação: CERIOLI, M. R; SZWARCFITER, J. L. Edge clique graphs and some classes of chordal graphs. Rio de Janeiro: NCE, UFRJ, 1999. 17 p. (Relatório Técnico, 21/99)
URI: http://hdl.handle.net/11422/2658
Aparece nas coleções:Relatórios Técnicos e de Pesquisa

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
21_99_000611340.pdf800,21 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.