Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/73584
Type: Artigo de periódico
Title: The K-behaviour of p-trees
Author: Liverani, M
Morgana, A
de Mello, CP
Abstract: Let, G = (V, E) be a graph with n vertices. The clique graph of G is the intersection graph K(G) of the set of all (maximal) cliques of G and K is called the clique operator. The iterated clique graphs K-i(G) are recursively delined by K-0(G) = G and K-i(G) = K(Ki-1(G)), i > 0. A graph is K-divergent if the sequence vertical bar V(K-i(G))vertical bar of all vertex numbers of its iterated clique graphs is unbounded, otherwise it is K-convergent. The long-run behaviour of G, when we repeatedly apply the clique operator, is called the K-behaviour of G. In this paper we characterize the K-behaviour of the class of graphs called p-trees, that has been extensively studied by Babel. Among many other properties, a p-tree contains exactly n - 3 induced P(4)s. In this way we extend some previous result about the K-behaviour of cographs, i.e. graphs with no induced P4S. This characterization leads to a polynomial time algorithm for deciding the K-convergence or K-divergence of any graph in the class.
Country: Canadá
Editor: Charles Babbage Res Ctr
Citation: Ars Combinatoria. Charles Babbage Res Ctr, v. 83, n. 33, n. 45, 2007.
Rights: fechado
Date Issue: 2007
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
There are no files associated with this item.


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