zbMATH — the first resource for mathematics

A polynomial algorithm for constructing the clique graph of a line graph. (English) Zbl 0592.05034
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_ n))\). This algorithm is on the order \(O(n^ 3)\), whereas constructing the clique graph of a general graph is NP-complete.
05C35 Extremal problems in graph theory
05C99 Graph theory
Full Text: DOI
[1] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[2] Hedetniemi, S.T.; Slater, P.J., Line graphs of triangleless and iterated clique graphs, (), 139-147 · Zbl 0255.05121
[3] Johnson, H.D., Cliques of a graph, Internat. J. comput. information sci., 5, 3, 209-238, (1976) · Zbl 0401.68042
[4] Sato, I., On a few clique graph equations, TRU mathematics, 14, 2, 31-36, (1978) · Zbl 0418.05043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.