Let $G$ be a $k$-regular directed graph, that is, a directed graph such that each vertex has $k$ edges going in and $k$ edges going out of it, and suppose further that $G$ has no loops. We can associate a non-directed graph $G'$ to it by ignoring the directions and eliminating double edges. Then $G'$ is a graph with degrees between $k$ (if all the in and out edges collapse to the same) and $2k$ (the other extreme case).

Question: Is there a way to add edges to $G'$ to make it $k'$-regular, for some $k'(k)$ independent of the number of vertices? Clearly $k' \geq 2k$, but even something larger would work.

  • $\begingroup$ Can you clarify $k'$? What exactly do you mean "independent of the number of vertices"? $\endgroup$ – Joey Kilpatrick Nov 5 '18 at 23:18
  • $\begingroup$ I mean a function that only depends on the degree of the regular graph but not on the number of vertices. Otherwise, if $n$ is the number of vertices, you can clearly always add vertices to make it $(n-1)$-regular, i.e., complete. I would like something that only depends on $k$, like $3k, 10k$, even something like $k!$ or $e^k$ if it works... $\endgroup$ – frafour Nov 6 '18 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.