Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Yes, you are right, the way I wrote it would return an edge-less set. I should write $G[V' \cup W]$. –  Marco Gario Jul 18 '11 at 23:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.