7
$\begingroup$

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one directed edge), we want to check for how many of the following we have a corresponding graph. the vertex number start from 1 to n and the degree sequence are sort by vertex numbers.

a) $d_{in}=(0,1,2,3), d_{out}=(2,2,1,1)$

b) $d_{in}=(2,2,1), d_{out}=(2,2,1)$

c) $d_{in}=(1,1,2,3,3), d_{out}=(2,2,3, 1,2)$

I want to find a nice way instead of drawing graph.

for (C):

enter image description here

$\endgroup$
1
1
$\begingroup$

Hints:

How many total directed edges does (a) and (c) have. What does that imply about the digraph? What should the sum $d_{in}+d_{out}$ be for any vertex in these cases?

(b) has too many edges!

$\endgroup$
4
  • $\begingroup$ None of these digraphs are possible. (a) and (c) are complete graphs, so $d_{in}+d_{out}=n-1$, where $n$ is the number of vertices. (b) doesn't work because $\sum d_{in}=\sum d_{out}=$ # of undirected edges. A graph on 3 vertices can only have a maximum of 3 edges, but the degree sequence implies 5 edges. $\endgroup$ – Laars Helenius Oct 17 '14 at 13:34
  • $\begingroup$ Of course if you allow loops and multiple edges some of the graphs may be possible. My objections are based on the fact that loops and multi edges are not allowed. $\endgroup$ – Laars Helenius Oct 17 '14 at 13:37
  • 1
    $\begingroup$ Whatever. Then prove it. $\endgroup$ – Laars Helenius Oct 17 '14 at 13:49
  • 1
    $\begingroup$ Your graph has multi edges! You said they weren't allowed. $\endgroup$ – Laars Helenius Oct 17 '14 at 14:34
1
$\begingroup$

Consider the sequence dtotal formed by summing the two sequences together;

dtotal is (2, 3, 3, 4), (4, 4, 2), (3, 3, 5, 4, 5)

Then note that each of these sequences must not contain any number larger than or equal to the number of terms in the sequence.

For example, the 4 in the first sequence would be unconstructible because there are only 4 vertices in the graph, while that vertex with total degree 4 needs to be connected to 4 other distinct vertices (since loops and multiple edges not allowed)

Similar arguments apply for the next two cases. For more information, do a search on degree sequences.

$\endgroup$
3
  • $\begingroup$ To clarify: if there is a edge from u to v, can there be a edge from v to u? Because my answer assumes otherwise. $\endgroup$ – Sean Lo Oct 17 '14 at 7:04
  • $\begingroup$ Ok with this information, I guess having a edge from u to v and a edge from v to u together. Then (b) is not possible while (a) and (c) are. $\endgroup$ – Sean Lo Oct 17 '14 at 7:28
  • $\begingroup$ Havel-Hakimi algorithm does not apply to directed graphs in its conventional sense, it only applies to simple graphs. $\endgroup$ – Sean Lo Oct 17 '14 at 7:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.