The clique operator on cographs and serial graphs
Por:
Larrión F., De Mello C.P., Morgana A., Neumann-Lara V., Pizaña M.A.
Publicada:
1 ene 2004
Resumen:
The clique graph of a graph G is the intersection graph K(G) of the (maximal) cliques of G. The iterated clique graphs Kn(G) are defined by K0(G) = G and Ki(G) = K(Ki-1(G)), i > 0 and K is the clique operator. A cograph is a graph with no induced subgraph isomorphic to P4. 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. © 2003 Elsevier B.V. All rights reserved.
Filiaciones:
Larrión F.:
Instituto de Matemáticas, U.N.A.M., Mexico, Mexico
De Mello C.P.:
Inst. de Computação, UNICAMP, Brazil
Morgana A.:
Dipartimento di Matematica, Univ. di Roma La Sapienza, Italy
Neumann-Lara V.:
Instituto de Matemáticas, U.N.A.M., Mexico, Mexico
Pizaña M.A.:
Depto. de Ing. Eléctrica, UAM-I, Mexico, Mexico
|