Ways to "regularize" a graph

Question

Are there any canonical methods, in graph theory, to produce a regular graph from a non-regular one? What I'm after is a construction which is as "categorically nice" as possible; for instance, to make a graph bipartite, you can take the tensor product of $G$ and $K_2$. Even more precisely, let's call the regularized graph $f(G)$; then I'd like there to be as nice a relationship as possible between $Hom(G, -)$ and $Hom(f(G), -)$.

I'm not really expecting there to be something particularly nice that satisfies even my loose criteria, but I'd be happy to upvote/accept any useful pointers to the literature. Alternatively, if anyone has an argument explaining why such a construction shouldn't exist, that'd be helpful too.

Answer 1

You may find the following article useful: The Minimal Regular Graph Containing a Given Graph, by Erdős and Kelly, available at http://www.math-inst.hu/~p_erdos/1967-26.pdf

Answer 2

I haven't thought at all about the relationship between Hom(G,-) and Hom(f(G),-), but the following very simple method will give you a regular graph (though the article in the first answer will probably give a smaller one):

If the graph is not regular, consider two disjoint copies of G, $G_1$ and $G_2$. Now, for all vertices v with degree less than the maximum degree in G, add an edge between the copy of v in $G_1$ and the copy of v in $G_2$. Repeat untill all vertices have degree equal to the maximum degree.

Answer 3

While not dealing with regularization in general perhaps these observations may be of interest. Graphs with special properties often lend themselves to operations on the graph which lead to "nice" properties on the transformed graph.

If one starts with a planar 3-connected graph (which by Steinitz's Theorem is a 3-polytopal graph, the vertex-edge graph of some 3-dimensional convex polyhedron) then one can construct the dual of this graph and obtain another planar 3-connected graph. If one starts with a planar 3-connected graph, first construct from it the medial graph. This is done by having a vertex for each edge of the graph, and joining two of these vertices in the medial graph with an edge if the edges they represent share a vertex and lie in the same face of the original graph. The resulting graph has the nice property that it is planar, 3-connected and every vertex has valence 4. Thus, if one dualizes this graph one gets a graph which which is bipartite, planar, and 3-connected, which is "related" to the original graph. In fact, all of its faces will have 4 sides. There are similar transformations which start with a plane 3-connected graph and transform it via a chain of operations into a graph all of whose faces have 5 sides.

Answer 4

Given a finite simple graph $\Gamma$ with vertices $V$, one can consider the Cayley graph of the group generated by transpositions of vertices corresponding to edges. This group is the symmetric group of the vertex set $V$ if $\Gamma$ is connected and it is the product associated to symmetric groups of the connected components otherwise.

Answer 5

One method that's useful in theoretical CS is the following. First, choose a particular family of $d$-regular graphs (i.e., for fixed $d$, one $d$-regular graph $H_r$ of each size $r$). Then, in the original graph $G$, for every vertex $v$, if the degree of $v$ is $r$, replace $v$ with the $d$-regular graph $H_r$ of size $r$ from the chosen family and connect each vertex in the copy of $H_r$ to one of the neighbors of $v$ in the original graph $G$. The resulting graph is obviously $(d+1)$-regular.

The chosen family of regular graphs is often a family of constant-degree expander graphs. This technique, introduced by Papadimitrou and Yannakakis, is particularly useful in manipulation of constraint graphs where the goal is to bound the arity of each constraint without affecting too much the maximum fraction of constraints that can be satisfied. The construction is useful, for example, in Dinur's proof of the PCP theorem.

Answer 6

If you define "graph" to allow multiple adjacencies and self-loops, then the simplest way to regularize a graph is just to add the right number of self-loops to each vertex. Algebraically this amounts to adding a diagonal matrix to the adjacency matrix of the graph. I'm not exactly sure what categorical consequences this would have, though.

Answer 7

Here is a simple and "natural" (whatever it means) way to get a regular graph from a given graph $G$. Take two disjoint copies of $G$, and insert edges between all pairs of vertices $(v_1,v_2)$ (with $v_1$ from the first copy and $v_2$ from the second copy) whenever there is no edge between the two corresponding vertices of $G$. Denoting by $n$ the order of the original graph $G$, this way you get an $n$-regular graph of order $2n$.

Yet another possible construction. Take four copies of the vertex set of $G$, and insert an edge between the vertex $v_i$ from the $i$th copy and the vertex $v_{i+1}$ from the $(i+1)$-th copy if either $i$ is even and there is an edge between the two corresponding vertices of the original graph $G$, or $i$ is odd and there is no edge between the two vertices of $G$. This yields an $n$-regular $4$-partite graph of order $4n$ which keeps the structure of $G$. More generally, for any even integer $k\ge 4$ you can produce this way a $k$-partite, $n$-regular graph of order $kn$, encoding in a very transparent way the structure of the original graph.

Answer 8

2 ways, both probably too boring for what you want:

(1) The inclusion of a graph into the complete graph on its vertex set.

(2) The homotopy $G \to \vee_n S^1$ (the latter being regular on just 1 vertex).