History


Please fill in your query. A complete syntax description you will find on the General Help page.
A polynomial algorithm for constructing the clique graph of a line graph. (English)
Discrete Appl. Math. 15, 61-66 (1986).
Summary: We will consider only finite, undirected, connected graphs without loops or multiple edges. A clique of graph G is a maximal complete subgraph of G. The clique graph K(G) of graph G is the intersection graph of the cliques of G. The line graph L(G) of graph G is the intersection graph of the edges of G. Thus, K(L(G)) is the clique graph of the line graph of G. This paper presents a five-step algorithm for constructing K(L(G)). As applications of the algorithm the results of two previous papers on K(L(G)) are subsumed as easy corollaries. Finally, additional corollaries are presented, including a description of $K(L(K\sb n))$. This algorithm is on the order $O(n\sp 3)$, whereas constructing the clique graph of a general graph is NP-complete.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!