Is it possible and how to construct k+1-regular graph from k-regular graph?

There is simple answer when the number of vertices n is divisible by k+1 - then one should add one vertex with edges to every group of k+1 vertices and the result is k+1-regular graph.

But what algorithms can be used for more general k+1 graphs. I guess, that every k-regular graph is subgraph of k+1-regular graph.

  • $\begingroup$ Simple answer: let n be number of vertices, i - index of vertex. Then one can add additional vertex vi and edge (vi,i) to each of the vertices i=1,...,n. Then one can take additional n copies of the initial graph and draw edges from vi to the corresponding vertices i of the copied graphs. The degress of vertices of the resulting graph will be k+1, that was required. Apparently it works but one should add too much new vertices. Maybe less involved construction exists? $\endgroup$ – TomR Oct 4 '15 at 12:33
  • 2
    $\begingroup$ A trivial sufficient condition: if the complement graph has a perfect matching, then you can add these edges to the original graph. But obviously this is not necessary (e.g. if you have an odd number of vertices). $\endgroup$ – Casteels Oct 4 '15 at 14:34

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.