DIMACS TR: 2001-40

Characterization of superbipartite graphs



Authors: I. E. Zverovich

ABSTRACT

Let $G$ and $H$ be graphs. A {\em substitution} of $H$ in $G$ instead of a vertex $v \in V(G)$ is the graph $G(v \to H)$, which consists of disjoint union of $H$ and $G - v$ with the additional edge-set $\{xy: x \in V(H), y \in N_G(v)\}$.

For a hereditary class of graphs ${\mathcal P}$, the {\em substitutional closure} of ${\mathcal P}$ is defined as the class ${\mathcal P}^*$ consisting of all graphs which can be obtained from graphs in $P$ by repeated substitutions.

Let ${\mathcal B}$ be the class of all graphs $G$ such that $G - N[v]$ is a bipartite graph for every vertex $v$ of $G$. Here $N[v]$ denotes the closed neighborhood of $v$. A graph is called a {\em superbipartite graph} if it is in the substitutional closure of ${\mathcal B}$.

We characterize superbipartite graphs in terms of forbidden induced subgraphs. Note that the weighted stability number in ${\mathcal B}^*$ can be found in polynomial time.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-40.ps.gz

DIMACS Home Page