The following statements are equivalent for every graph G=(V,E):
|
A hypergraph is self-dual if it is isomorphic to its dual. Another way of expressing this is to say that the vertex-hyperedge incidence matrix can be made symmetric by permutating the columns. Thus these graphs in questions are just the row-intersection graphs of symmetric (0-1) matrices, and therefore special competition graphs.
In the second step of the duality-approach of recognizing intersection graphs of self-dual hypergraphs, one needs a method to recognize self-dual hypergraphs. ....
Now the Krausz-type characterization obviously reads as follows:
The following statements are equivalent for every graph G=(V,E):
|
Self-dual hypergraphs may have different representations as symmetric matrices, i.e. there may be different isomorphisms between the hypergraph and its dual.. But for such matrices, we have two extremes: Self-dual hypergraphs where every symmetrical vertex-hyperedge incidence matrix has no `1´ in the main diagonal, and those with no `0´. Self-dual hypergraphs of the first kind are just the neighborhood hypergraphs of graphs, those of the second kind are just the closed-neighborhood hypergraphs of graphs. But the intersection graph of the neighborhood hypergraph of a graph G is just the 2-step graph of G, whereas the intersection graph of the closed-neighborhood hypergraph of G equals the square of G. Therefore, the above theorem yields the following Krausz-type characterizations of squares and 2-step graphs:
[M67]:
A graph G=(V,E) is the square of some graph if and only if
there is some covering of the its edges by complete subgraphs
Sx, x V,
such that each Sx contains x,
and xSy
if and only if
ySx.
|
|
[AV73]:
A graph G=(V,E) is the 2-step graph of some graph
if and only if
there is some covering of the its edges by complete subgraphs
Sx, xV,
such that no Sx contains x,
and xSy
if and only if
ySx,
for distinct x,y .
|
These characterizations are not too useful---actually recognizing squares of graphs is NP-complete [MS94].