Cheap and Secure Web Hosting Provider : See Now

[Answers] How many ways are there to add a node to a digraph?

, , No Comments
Problem Detail: 

In a digraph with $n$ vertices, how many different ways a new vertex can be added to get the digraphs with $n$+1 vertices?

Input digraph with $n$ vertices have following degree criteria :

  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) \leq 2$ for every vertex $v$, and
  4. $d_{\mathrm{out}}(v) \leq 2$ for every vertex $v$.
  5. $d_{\mathrm{in}}(v) + d_{\mathrm{out}} \geq 3$ for every vertex $v$.

After adding one vertex, the digraphs with $n$+1 vertices should also follow same degree criteria.

Is there any way to mathematically express the number of possibilities?

My approach:

I come to know that, In a directed graph with n vertices has total degree k, can have at-most nk/2 edges. So for example (Specific Case) If the original digraph is having 20 vertices and total degree of each vertex is 3 (minimum case). That means maximum edge possible is 30. When I add one node to the digraph, total vertices will be 21 and if i take total degree to 4(maximum). Then maximum possible edges will be 42. Which means there is 12 (42 - 30) possible position where I can add new edge.

So finally I have 12 free positions(indegree and outdegree) and I can add maximum 4 and minimum 3 edges at once and then I will calculate possible combinations...Is this approach correct

Asked By : rajshri

Answered By : David Richerby

Since we are not treating isomorphic graphs as identical, my advice in the comments to try all the options was bad.

Let $G$ be the original graph. Let $A$ be the set of vertices in $G$ that can accept an extra incoming edge and let $B$ be the set of vertices that can accept an extra outgoing edge. Every vertex has total degree 3 or 4 and no vertex in the new graph can have degree more than 4. This means that no vertex of $G$ can have more than one edge added to it, so $A\cap B=\emptyset$.

Now, consider adding a new vertex $x$ to $G$. By the degree conditions, $x$ must be connected to $G$ in one of the following ways:

  • it sends one edge to $A$ and receives two from $B$;
  • it sends two edges to $A$ and receives one from $B$;
  • it sends two edges to $A$ and receives two from $B$.

Working out the total number of ways from here is simple combinatorics.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback