Name for a graph with two types of vertices $U, V$, where the end points of edges are either both in $U$, or one is in $U$ and the other in $V$? 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$?
 A: 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):


*

*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.

*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.

*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.
