4
$\begingroup$

We say that a property $\Pi$ is hereditary if whenever $G=(V,E)$ satisfies $\Pi$ then any induced subgraph G[V'] (with $V' \subseteq V $) satisfies $\Pi$.

I was wondering whether there is a proper name for the same concept when restricted to bipartite graphs. For example:

Given a bipartite graph G=(V,W,E), where V and W are the two independent sets of vertices, we call a property $\Pi$ "V-hereditary" (resp. "W-hereditary") if whenever $G$ satisfies $\Pi$ then any induced subgraph G[V' \cup W] (resp. $G[V \cup W']$) satisfies $\Pi$ (with V' \subseteq V and $W' \subseteq W'$).

Thank you very much!

EDIT I corrected the question after Oliver observation. The idea is that I allow removal only from one of the two sets.

2 Answers 2

1

Your restriction is the same as the usual definition. Indeed, clearly a (vertex-)hereditary property is also "bipartite hereditary". Now suppose $\Pi$ is "bipartite hereditary". Suppose $\Pi$ holds for a bipartite graph $G$ on $V = V_1 \cup V_2$ ($V_1,V_2$ are the two parts). Suppose we're given some V' \subset V. Since $\Pi$ is bipartite hereditary, then $\Pi$ holds for G[V_1 \cup (V_2 \cap V')]. Using the property again, $\Pi$ also holds for G[(V_1 \cap V') \cup (V_2 \cap V')] = G[V'].


As far as I know, a hereditary property is usually defined to be closed under taking arbitrary subgraphs, not only induced.

0

I think there is unlikely to be a name for this concept. The graph G[V'] has no edges, and hence is not a terribly interesting object of study.

  • 0
    Yes, you are right, the way I wrote it would return an edge-less set. I should write $G[V' \cup W]$.2011-07-18