Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/2650
Type: Relatório
Title: On clique graphs with linear size
Author(s)/Inventor(s): Protti, Fábio
Szwarcfiter, Jayme Luiz
Abstract: The clique graph H = K (G) of is the intersection graph of the collection of maximal cliques of G. In this case, G is a clique-inverse graph of H. By examining K (G), we describe some sufficient conditions for the number of maximal cliques of G to be bounded by O(|VG|). These conditions are then applied to analyze the complexity of recognizing clique-inverse graphs of various families of graphs.
Keywords: Grafos clique-inverse
Interseção de grafos
Clique-inverse graphs
Intersection graphs
Clique graphs
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Department : Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Issue: 0799
Issue Date: 31-Dec-1999
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Citation: PROTTI, F.; SZWARCFITER, J. L. On clique graphs with linear size . Rio de Janeiro: NCE, UFRJ, 1999. 10 p. (Relatório Técnico, 07/99)
URI: http://hdl.handle.net/11422/2650
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
07_99_000611268.pdf210,62 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.