✦ LIBER ✦

Neighborhood hypergraphs of bipartite graphs

✍ Scribed by Endre Boros; Vladimir Gurvich; Igor Zverovich

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 252 KB
Volume: 58
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20293

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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

📜 SIMILAR VOLUMES

Transversal hypergraphs to perfect match

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

✍ Endre Boros; Khaled Elbassioni; Vladimir Gurvich 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 285 KB

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers

Embeddings of bipartite graphs

✍ Mohammed Abu-Sbeih; T. D. Parsons 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 458 KB

Bichromaticity of bipartite graphs

✍ Dan Pritikin 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 312 KB

Let 8 be a bipartite graph with edge set €and vertex bipartition M, N. The bichromaticity p ( 6) is defined as the maximum number p such that a complete bipartite graph on p vertices is obtainable from 5 by a sequence of identifications of vertices of M or vertices of N. Let p = max{lMI, IN\}. Hara

Balanced coloring of bipartite graphs

✍ Uriel Feige; Shimon Kogan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

## Abstract Given a bipartite graph __G__(__U__∪__V, E__) with __n__ vertices on each side, an independent set __I__∈__G__ such that |__U__∩__I__|=|__V__∩__I__| is called a balanced bipartite independent set. A balanced coloring of __G__ is a coloring of the vertices of __G__ such that each color c

Path factors of bipartite graphs

✍ Hong Wang 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 375 KB

## Abstract A path on __n__ vertices is denoted by __P__~__n__~. For any graph __H__, the number of isolated vertices of __H__ is denoted by __i(H)__. Let __G__ be a graph. A spanning subgraph __F__ of __G__ is called a {__P__~3~, __P__~4~, __P__~5~}‐factor of __G__ if every component of __F__ is o

Quadrilateral embeddings of bipartite gr

Quadrilateral embeddings of bipartite graphs

✍ Ian Anderson 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 304 KB

## Abstract Current graphs and a theorem of White are used to show the existence of almost complete regular bipartite graphs with quadrilateral embeddings conjectured by Pisanski. Decompositions of __K~n~__ and __K~n, n~__ into graphs with quadrilateral embeddings are discussed, and some thickness