Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/74959
Type: Artigo de periódico
Title: The clique operator on cographs and serial graphs
Author: Larrion, F
de Mello, CP
Morgana, A
Neumann-Lara, V
Pizana, MA
Abstract: The clique graph of a graph G is the intersection graph K(G) of the (maximal) cliques of G. The iterated clique graphs K(n)(G) are defined by K(0)(G) = G and K(i)(G) = K(K(i-1)(G)), i > 0 and K is the clique operator. A cograph is a graph with no induced subgraph isomorphic to P(4). In this article we use the modular decomposition technique to characterize the K-behaviour of cographs and to give some partial results for the larger class of serial (i.e. complement-disconnected) graphs. We prove that a cograph is K-convergent if and only if it is clique-Helly. This characterization leads to a polynomial time algorithm for deciding the K-convergence or K-divergence of any cograph. (C) 2003 Elsevier B.V. All rights reserved.
Subject: iterated clique graphs
clique divergence
modular decompositions
cographs
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/j.disc.2003.10.023
Date Issue: 2004
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000221634100018.pdf247.93 kBAdobe PDFView/Open


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