Cheap and Secure Web Hosting Provider : See Now

[Solved]: Maximum edges in degree-restricted digraph

, , No Comments
Problem Detail: 

How many edges can there be in a loop-free, asymmetric $n$-vertex digraph, if each node can have maximum total degree $k$ and minimum total degree $m$?

That is,

  1. There are no edges $(v,v)$ (self-loops),
  2. if there is an edge $(u,v)$, there is no edge $(v,u)$,
  3. $d_{\mathrm{in}}(v) + d_{\mathrm{out}}(v)\leq k$ for every vertex $v$, and
  4. $d_{\mathrm{in}}(v) + d_{\mathrm{out}} \geq m$ for every vertex $v$.

Thanks in advance.

Asked By : rajshri

Answered By : Yuval Filmus

The question has changed and will probably change again in the future. It wasn't clear to start with, so the question I was trying to answer is:

How many edges can a directed graph on 22 vertices have, if the out-degree is at most 4, and the in-degree is at least 3?

Connect each node $x$ to nodes $x+1,x+2,x+3,x+4$, all indices taken modulo $22$. This satisfies all your conditions and has 88 edges, which is also trivially the maximum.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41536

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback