Premium
A generalization of line graphs: ( X, Y )‐intersection graphs
Author(s) -
Cai Leizhen,
Corneil Derek,
Proskurowski Andrzej
Publication year - 1996
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/(sici)1097-0118(199603)21:3<267::aid-jgt2>3.0.co;2-o
Subject(s) - combinatorics , mathematics , intersection graph , split graph , discrete mathematics , induced subgraph , chordal graph , line graph , cograph , graph , pathwidth , vertex (graph theory)
Given a pair ( X, Y ) of fixed graphs X and Y, the ( X, Y )‐intersection graph of a graph G is a graph whose vertices correspond to distinct induced subgraphs of G that are isomorphic to Y, and where two vertices are adjacent iff the intersection of their corresponding subgraphs contains an induced subgraph isomorphic to X . This generalizes the notion of line graphs, since the line graph of G is precisely the ( K 1 , K 2 )‐intersection graph of G . In this paper, we consider the forbidden induced subgraph characterization of ( X, Y )‐intersection graphs for various ( X, Y ) pairs; such consideration is motivated by the characterization of line graphs through forbidden induced subgraphs. For this purpose, we restrict our attention to hereditary pairs (a pair ( X, Y ) is hereditary if every induced subgraph of any ( X, Y )‐intersection graph is also an ( X, Y )‐intersection graph), since only for such pairs do ( X, Y )‐intersection graphs have forbidden induced subgraph characterizations. We show that for hereditary 2‐pairs (a pair ( X, Y ) is a 2‐pair if Y contains exactly two induced subgraphs isomorphic to X ), the family of line graphs of multigraphs and the family of line graphs of bipartite graphs are the maximum and minimum elements, respectively, of the poset on all families of ( X, Y )‐intersection graphs ordered by set inclusion. We characterize 2‐pairs for which the family of ( X, Y )‐intersection graphs are exactly the family of line graphs or the family of line graphs of multigraphs. © 1996 John Wiley & Sons, Inc.