Please use this identifier to cite or link to this item:
|Type:||Artigo de periódico|
|Title:||The K-behaviour of p-trees|
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.|
|Editor:||Charles Babbage Res Ctr|
|Citation:||Ars Combinatoria. Charles Babbage Res Ctr, v. 83, n. 33, n. 45, 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.