After talking about the basics of regular graphs, let me now introduce something more interesting. When we make changes to a regular graph topology, like addition or removal of edges or nodes, the resulting topology might not remain regular. An interesting question then is the following: are there ways to modify a given regular graph topology, while maintaining its regularity?

Here I introduce a simple operation called “clique insertion” that “extends” a graph (or makes a graph bigger by adding more nodes) while preserving the regularity of the graph. The basic idea of this is due to sri. Later on I developed it a bit more and now it looks like it is a useful result.

**Given an ***r-regular* graph of *n* nodes, the graph can be extended to an *r-regular* graph of *n + (r – 1)* nodes by a process of “node insertions” (or “clique insertion”).

**Explanation:** Let us start with the minimally connected non-trivial regular graph: a circle with *n* nodes. We can see that by “inserting” a node between any two nodes, we can extend the graph into a bigger graph while preserving the regularity. In other words, cut an arbitrary edge into two, and make their loose ends incident on a newly added node. We can go on inserting any number of nodes in this fashion. We just get bigger circles, all of which have a regularity of 2.

It is pretty simple to see in a circle. Now, let’s go to a slightly more complicated topology. Consider a 3-regular graph. We can get a bigger 3-regular graph by inserting 2 nodes (as explained above), and *adding another edge between the 2 nodes*.

It is equivalent to inserting a clique of exactly *r – 1* (where *r* is the regularity) nodes in the existing graph (refer the figure below). For an arbitrary *n* and arbitrary *r*, we can construct an *n + (r – 1)* node graph by inserting exactly *r – 1* nodes, and adding edges among them to form a *r – 1* node clique.

In the figure, we have a 4-regular graph (incidentally, it is the complete graph K5). We now do a “clique insertion” operation on the graph to get a new 4-regular graph of 8 nodes. The nodes marked in brown form the clique.

The above result can be extended thus: given an *r-regular* graph of *n* nodes, we can construct a graph of *n + m * (r – 1)*, where *m* is a positive integer. So, we can easily construct arbitrarily large regular graphs of a given regularity *r* by inserting any number of cliques of size exactly *r – 1*.

**Usefulness:** This has an important connotation in distributed systems, where nodes joining and failures are frequent. Several distributed hash tables (DHTs) require a symmetric degree distribution. They also need to accommodate for node joining and leaving.

- For one, this result can be developed to be a measure the amount of disruption in symmetry that can be expected when changes in topology occur.
- Also, it can be used to design topology changes so as to preserve symmetry. Perhaps, by using dummy nodes.

** Question:** Is there a similar way to make a graph smaller while preserving the regularity?

—

That was one example of preserving a structural property of a graph. It is an interesting to find out if we can have a whole set of such operators. We can look at several other properties as well: diameter, average path length, centrality distributions, connectivity etc.. I shall define this problem more formally in another post later on.