A COMMON GENERALIZATION OF LINE GRAPHS AND CLIQUE GRAPHS

Both the line graph and the clique graph are defined as intersection g raphs of certain families of complete subgraphs of a graph. We general ize this concept. By a k-edge of a graph we mean a complete subgraph w ith k vertices or a clique with fewer than k vertices. The k-edge grap h DELTA(k)(G) of a graph G is defined as the intersection graph of the set of all k-edges of G. The following three problems are investigate d for k-edge graphs. The first is the characterization problem. Second , sets of graphs closed under the k-edge graph operator are found. The third problem is the question of convergence: What happens to a graph if we take iterated k-edge graphs? (C) 1994 John Wiley & Sons, Inc.