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

  • 2
    $\begingroup$ Hi, what did you try and where did you get stuck? It doesn't sound too hard to just try one graph by another. $\endgroup$ – Pål GD Apr 20 '15 at 12:49
  • $\begingroup$ I need a mathematical expression for maximum possibility. but I could not figure out how to proceed. $\endgroup$ – rajshri Apr 20 '15 at 12:57
  • 1
    $\begingroup$ One problem which seems like you have overlooked, which might be what Richerby hints to, is that of isomorphism classes. You shouldn't count isomorphic graphs twice. And it will be hard to tell when you construct to isomorphic graphs. So you will probably have to settle for a cruder upper bound. $\endgroup$ – Pål GD Apr 20 '15 at 14:12
  • 1
    $\begingroup$ This is a problem statement, not a question. If you have a specific question regarding the wording of the problem or about specific steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Apr 20 '15 at 14:23
  • $\begingroup$ @PålGD I agree: It's unclear whether isomorphic graphs should be counted as the same, since the identity of the nodes may or may not be important. I had considered isomorphism but, even if you're counting graphs up to identity, rather than isomorphism, there probably still isn't a nice function that gives the answer. $\endgroup$ – David Richerby Apr 20 '15 at 17:12

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.

| cite | improve this answer | |

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.