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$?
1,232
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.
Related videos on Youtube
Author by
davitenio
Updated on August 01, 2022Comments
-
davitenio over 1 year
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$?
-
Qiaochu Yuan over 11 yearsI 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)).
-
Angela Pretorius over 11 yearsIf $U$ is the empty set, or is any set containing one point, then the condition is trivially fulfilled.
-
042 over 11 yearsThus, as Angela Richardson says, each graph fulfills this property.
-
MJD over 11 years@Angela: I think you should post this as an answer.
-
davitenio over 11 years@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$.
-
042 over 11 years@davitenio That depends on a definition of graph. Usually, if it is not stated otherwise, by the term graph one means an undirected simple graph, i.e., multiple edges and loops are not allowed. However, it does not matter what definition do you use, since $U = \emptyset$ works for all graphs.
-
davitenio over 11 years@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.
-
-
davitenio over 11 yearsThank 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$.
-
davitenio over 11 yearsIf 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).
-
042 over 11 years@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.
-
davitenio over 11 yearsYes. 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.
-
042 over 11 years@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...
-
davitenio over 11 yearsOk. Maybe I am even missusing the word graph. If $U = \{u_1, u_2\}$ and $V = \{v_1, v_2\}$, then I could create one graph $G_1$ with edges $u_1v_1, v_1u_2, u_2v_2$ and $v_2u_1$; and I could create another graph $G_2$ with edges $u_1u_2, u_2v_2, v_2v_1$ and $v_1u_1$. To me $G_1$ satisfies the property because $u_1$ and $u_2$ are not adjacent; whereas $G_2$ violates the property. So I have a graph that does not satisfy the property, or should they both considered the same graph?
-
042 over 11 years@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.