How do you call a graph that the bipartite property is satisfied for the one set of nodes and not the other?

Say you have two set of nodes $A$ and $B$ where there can be edges between nodes of set $A$ but there can be no edges between nodes of set $B$.Of course there can be edges between nodes of different sets.Is there a name for this type of graph?

  • $\begingroup$ No, there is no special name, and indeed you can do this for any graph (just take any independent set of vertices to form $B$ and the rest of the vertices form $A$). $\endgroup$ Dec 7 '20 at 11:28
  • 1
    $\begingroup$ That could be any graph, right? Let $G$ be any graph, let $B$ be any independent set of nodes (no edges between them) in $G$, and let $A$ be the rest of the nodes in $G$. $\endgroup$
    – bof
    Dec 7 '20 at 11:29
  • $\begingroup$ You could say that this holds iff $A$ is a vertex cover of the entire graph if that helps. $\endgroup$ Dec 7 '20 at 19:20

This is more a characteristic of $B$. A subset $B$ of the nodes of a graph that have no edges between each other is called an independent set.

To further elaborate:

Every independent subset fulfills the criterion of the question, and every $B$ that fulfills the criterion of the question is inversely an independent subset.

Note that there are actually no criteria on $A$ other that it's the remaining graph, after removing $B$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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