Edge-clique graphs

The edge-clique graphK(G) of a graphG is that graph whose vertices correspond to the edges ofG and where two vertices ofK(G) are adjacent whenever the corresponding edges ofG belong to a common clique. It is shown that every edge-clique graph is a clique graph, and that ifG is either an interval graph or a line graph, then so too isK(G). An algorithm is provided for determining whether a graph is an edge-clique graph. A new graph called the STP graph is introduced and a relationship involving this graph, the edge-clique graph, and the line graph is presented. The STP graphs are also characterized.Research supported in part by Office of Naval Research Contract N00014-88-K-0018.Research supported in part by Office of Naval Research Contract N00014-88-K-0163.