Premium
A common generalization of line graphs and clique graphs
Author(s) -
Prisner Erich
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180308
Subject(s) - combinatorics , block graph , mathematics , line graph , split graph , clique graph , discrete mathematics , cograph , symmetric graph , chordal graph , clique sum , neighbourhood (mathematics) , vertex transitive graph , pathwidth , 1 planar graph , graph , graph power , voltage graph , mathematical analysis
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?