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):

  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.

Share:
1,232

Related videos on Youtube

davitenio
Author by

davitenio

Updated on August 01, 2022

Comments

  • davitenio
    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
      Qiaochu Yuan over 11 years
      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)).
    • Angela Pretorius
      Angela Pretorius over 11 years
      If $U$ is the empty set, or is any set containing one point, then the condition is trivially fulfilled.
    • 042
      042 over 11 years
      Thus, as Angela Richardson says, each graph fulfills this property.
    • MJD
      MJD over 11 years
      @Angela: I think you should post this as an answer.
    • davitenio
      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
      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
      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
    davitenio over 11 years
    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$.
  • davitenio
    davitenio over 11 years
    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).
  • 042
    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
    davitenio over 11 years
    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.
  • 042
    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
    davitenio over 11 years
    Ok. 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
    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.