V of
pairs of sets.
The connection graph has V as vertex set,
and an edge between x to y whenever
Sx 
Ty
Sy
Tx is nonempty
[M95].
Connection graphs extend intersection graphs---every intersection graph of a family of P-sets is a connection graph of a family of pairs of P-sets after adding all loops. Therefore recognition for a class of connection graphs may be more difficult than for the corresponding intersection class. For instance, if the property P is to have just one element, then intersection bigraphs, digraphs and graphs are fairly easy to recognize, but recognizing the corresponding connection graphs is NP-complete [CE90]. However, under some minimum degree condition, recognition is again possible essentially by the (bi)clique multigraph method [P97].
Why bicliques?
Star graphs
for connection graphs still
have a slightly more general shape. If we
consider any point
a
xV
(Sx
Tx), then we have the
set V1 of all x
V
where aSx,
and the set V2 of all
yV
where aTy.
Every x
V1 is adjacent to every
y
V2. Note also
that V1 and
V2 are not necessarily disjoint.
Certainly, all xV1
V2 have
loops. Finally these subgraphs are not necessarily
induced in G, nor are they necessarily maximal.
Back to the start page for intersection graphs.