Premium
Neighborhood hypergraphs of bipartite graphs
Author(s) -
Boros Endre,
Gurvich Vladimir,
Zverovich Igor
Publication year - 2008
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.20293
Subject(s) - mathematics , hypergraph , combinatorics , bipartite graph , graph isomorphism , uniqueness , discrete mathematics , symmetrization , adjacency matrix , isomorphism (crystallography) , graph , line graph , mathematical analysis , chemistry , crystal structure , crystallography
Matrix symmetrization and several related problems have an extensive literature, with a recurring ambiguity regarding their complexity and relation to graph isomorphism. We present a short survey of these problems to clarify their status. In particular, we recall results from the literature showing that matrix symmetrization is in fact NP‐hard; furthermore, it is equivalent with the problem of recognizing whether a hypergraph can be realized as the neighborhood hypergraph of a graph. There are several variants of the latter problem corresponding to the concepts of open, closed, or mixed neighborhoods. While all these variants are NP‐hard in general, one of them restricted to the bipartite graphs is known to be equivalent with graph isomorphism. Extending this result, we consider several other variants of the bipartite neighborhood recognition problem and show that they all are either polynomial‐time solvable, or equivalent with graph isomorphism. Also, we study uniqueness of neighborhood realizations of hypergraphs and show that, in general, for all variants of the problem, a realization may be not unique. However, we prove uniqueness in two special cases: for the open and closed neighborhood hypergraphs of the bipartite graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 69–95, 2008