0
$\begingroup$

I'm looking to try and get a bound on the maximum outdegree of an internal vertex in a DAG w/ multiple-source vertexes and a single sink vertex given the following constraints:

  1. $\text{deg}^-(\text{sink}) = 2$
  2. For any internal vertex, $1 \le \text{deg}^-(v) \le 2$
  3. Source vertexes can have any outdegree.

Using the degree sum formula, my gut instinct says that the maximum outdegree of an internal vertex is 2 but I'm having difficulty formally proving it. However, I'm new to graph theory so I'm not sure if I'm even on the right track or if my intuition is leading me astray. Any help would is much appreciated!

$\endgroup$
2
  • $\begingroup$ what is an interval vertex? $\endgroup$
    – Exodd
    Jun 15, 2017 at 18:23
  • $\begingroup$ Sorry typo, edited now $\endgroup$
    – jaip
    Jun 15, 2017 at 19:37

1 Answer 1

0
$\begingroup$

Consider the following graph

            -> v_1 ->
            -> v_2 -> v_5 ->
            -> v_3 ->
Source -> v -> v_4 -> v_6 -> sink

i.e. the graph $G=(V,E)$, with $V=\{source,v,v_1,v_2,...,v_6,sink\}$ and $E=\{(source,v),(v,v_1),(v,v_2),(v,v_3),(v,v_4),(v_1,v_5),(v_2,v_5),(v_3,v_6),(v_4,v_6),(v_5,sink),(v_6,sink)\}$. Source and sink here are two vertices and thus sink has in-degree exactly 2.

You can easily add more "layers" in the graph and thus increase $\deg^+(v)$. If you do not bound the total number of vertices in your graph, vertex $v$ can have arbitrarily high out-degree (something around $\deg^+(v)=\frac{n-1}{2}$, where $n=|V|$). So the answer would be that there can only be an upper bound that is depending on the number of vertices. Note however, that this upper bound might even be higher than the one in my example.

(Excuse me for that ugly scetch but I only have my phone with me and I am not allowed to upload pictures.)

$\endgroup$
5
  • $\begingroup$ Sorry, I think I'm not entirely clear on the notation you're using because the way I'm understanding your graph, it violates one of the constraints. The sink must have an indegree of 2 and only one sink can exist (therefore all paths from any input must terminate at that sink). The way I'm reading your diagram, there are either >1 sinks or the sink has an in degree >2. $\endgroup$
    – jaip
    Jun 16, 2017 at 20:51
  • $\begingroup$ Sorry, if my Diagramm is misleading. I meant a graph $G=(V,E)$, with $V=\{source,v,v_1,v_2,...,v_6,sink\}$ and $E=\{(source,v),(v,v_1),(v,v_2),(v,v_3),(v,v_4),(v_1,v_5),(v_2,v_5),(v_3,v_6),(v_4,v_6),(v_5,sink),(v_6,sink)\}$. Source and sink here are two vertices and thus sink has in-degree exactly 2. Does that help? $\endgroup$
    – Jon Isr
    Jun 16, 2017 at 23:42
  • $\begingroup$ Ok yes, now I see what you're saying. Definitely helps, thanks for the clarification! $\endgroup$
    – jaip
    Jun 18, 2017 at 0:47
  • $\begingroup$ I edited my answer so that it includes the clarification. If it answers your question please mark it as the correct answer. $\endgroup$
    – Jon Isr
    Jun 18, 2017 at 13:53
  • $\begingroup$ Sorry that took a bit, thanks for the help! $\endgroup$
    – jaip
    Jun 21, 2017 at 17:44

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.