Title: A common generalization of line graphs and clique graphs
Abstract: Abstract Both the line graph and the clique graph are defined as intersection graphs of certain families of complete subgraphs of a graph. We generalize this concept. By a k ‐edge of a graph we mean a complete subgraph with k vertices or a clique with fewer than k vertices. The k ‐edge graph Δ 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 investigated 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?
Publication Year: 1994
Publication Date: 1994-05-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 15
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot