0
$\begingroup$

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$?

  • 0
    @042 Thanks for clarifying. Maybe I phrased my question incorrectly, or I am still using wrong terminology, but I don't see that every graph fulfills the property. If $U = \{u_1, u_2\}$ and $V = \{v\}$ and I interconnect these 3 vertices such that they form a triangle with a vertex in each corner, I have an edge from $v$ to $u_1$, from $v$ to $u_2$, and from $u_1$ to $u_2$. The latter is precisely what I don't want to allow.2012-06-29

1 Answers 1

3

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.

  • 0
    @davitenio The graphs are of course not the same. But this is not a problem. A problem is how _exactly_ do you define your property. Try to write down the _exact_ definition with quantifiers and all other things and you shall see the problem as well... You have definitely a problem with quantifiers.2012-07-01