I know that a graph whose vertices can be divided into two sets $U$ and $V$ such that every edge can only connect a vertex in $U$ to one in $V$ is called a bipartite graph. Is there a name for a type of graph where edges are allowed from $U$ to $V$ and from $V$ to $V$, but not from $U$ to $U$?

  • 3
    $\begingroup$ I don't know if there's a name for this kind of graph, but $U$ is called an independent set (en.wikipedia.org/wiki/Independent_set_(graph_theory)). $\endgroup$ – Qiaochu Yuan Jun 28 '12 at 15:55
  • 2
    $\begingroup$ If $U$ is the empty set, or is any set containing one point, then the condition is trivially fulfilled. $\endgroup$ – Angela Richardson Jun 28 '12 at 15:59
  • $\begingroup$ Thus, as Angela Richardson says, each graph fulfills this property. $\endgroup$ – 042 Jun 28 '12 at 16:10
  • $\begingroup$ @Angela: I think you should post this as an answer. $\endgroup$ – MJD Jun 28 '12 at 16:20
  • $\begingroup$ @AngelaRichardson If my graph has no vertex from $U$, i.e., $U = \{\}$, I see that the condition is satisfied. But if $U$ has one vertex $u$, i.e, $U = \{u\}$, the condition does not need to be fulfilled. My graph could have a loop $(u, u)$ from $u$ to $u$. $\endgroup$ – davitenio Jun 28 '12 at 19:13

Well, according to your last comment, you have probably some chaos in quantifiers. Because there are three (in the case I have not overlooked some) possible interpretations of your question (no matter whether you allow or disallow loops and/or multiple edges):

  1. The most usual interpretation: graph is in your class if there exists a pair of sets $U$, $V$ of vertices of that graph, such that they satisfy your property. That is, you have an existential quantifier before $U$ and $V$. Note, that bipartite graphs are defined in a similar manner. In that case, as Angela Richardson pointed, you can take set $U = \emptyset$ and a property holds trivially. Thus, in this interpretation, all graphs satisfy this property.
  2. Your last comment suggest this (quite unusual) interpretation: graph is in your class if for all pairs of sets $U$, $V$ of vertices of that graph your property holds. But, if your graph has at least one edge interconnecting vertices $v_1, v_2$, the property does not hold for $U = \{v_1,v_2\}$, and $V = V(G) - U$. Thus, the only graphs satisfying this property are graphs without edges.
  3. The last possible interpretation that I am aware of is this one: you have specified $U$, $V$ uniquely for all graphs (for instance, you can specify $U$ as set of all vertices of degree greater than 3 and $V$ as a set of all other vertices). In this case, it is possible that for some definition of $U$ and $V$ you get some reasonable nontrivial classes, but you have not mentioned anything like this in your question, so I suppose that this is not a case.

If you have meant some other interpretation, please specify your question.

  • $\begingroup$ Thank you very much for having taken the time to make sense of my ambiguous question. I hope I have understood where the misunderstanding is coming from. It is not that I want to know if there exists a way to divide $V(G)$ into two sets $U$ and $V$ with edges having the form $uv$ or $vv$, but not $uu$, where $u \in U$ and $v \in V$. Instead, I am assuming fixed $U$ and $V$, with $U \cap V = \emptyset$. Using $U$ and $V$ I construct a graph $G$ such that it has a set of vertices $V(G) = U \cup V$ and a set of edges where $uv$ and $vv$ are allowed, but $uu$ is not, with $u \in U$ and $v \in V$. $\endgroup$ – davitenio Jul 1 '12 at 9:13
  • $\begingroup$ If I had not added the edges $vv$, but only edges $uv$, I would have created a bipartite graph. But I want to allow $vv$ in my constructed graph, but not $uu$. I want to know if there is a name for a graph constructed like that. Alternatively, I would be happy with a way to describe such a graph (maybe using the term independent set suggested by Qiaochu Yuan). $\endgroup$ – davitenio Jul 1 '12 at 9:19
  • $\begingroup$ @davitenio In what sense are the sets $U,V$ fixed? Because in the usual sense this means, that you use the same sets $U,V$ to construct all graphs, and this means, that you can construct only finitely many graphs and this is probably not what you mean. Sorry, but your question still does not make great sense to me. $\endgroup$ – 042 Jul 1 '12 at 9:30
  • $\begingroup$ Yes. For fixed $U, V$ I can create a finite number of graphs in the described manner. For a different set $U, V$, call them $U', V'$, I can create another finite number of graphs. The graphs created from $U$ and $V$, and those created from $U'$ and $V'$ share the same restriction: no edges $uu$, for $u \in U$, or $u \in U'$ in the latter case, are allowed. I want a way to name or concisely describe such graphs. $\endgroup$ – davitenio Jul 1 '12 at 9:57
  • 1
    $\begingroup$ @davitenio If the name of the class of graphs is supposed not to depend on $U$ and $V$, then it is exactly equivalent to the case 1.) of my answer. Since you say that a graph has a property $x$ (you want to determine the name of this property) if it can be created from some $U$, $V$ in the way you have specified. But "from some $U$,$V$" is exactly equivalent to "there exist a pair of sets $U$,$V$, such that..." That is, the problem with quantifiers is still there... $\endgroup$ – 042 Jul 1 '12 at 12:15

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.