Regular Graphs: “Clique Insertion”

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.

Advertisements

4 Responses to Regular Graphs: “Clique Insertion”

  1. sri says:

    I came across this blog by sheer chance and was about to forward the URL for this blog to.. you!! Hmm, so silent folks are always up to something.. 😉

    Nice set of posts.

    Coming to this post: You can extend an r-regular graph simply by inserting an r-2 regular graph by plopping nodes inside edges. They need not be cliques.

    -sri

  2. sri says:

    Some more associated questions:

    Suppose we have an edge X — Y. We can insert any number of nodes inside a single edge and make the edge into a long chain. However, suppose we have inserted k edges and the original edge looks like this: X — n1 — n2 — … — nk — Y. Suppose the original graph was 3 regular, and we want to connect the inserted nodes to make it 3-regular. We see that we can connect some — but not all — of the inserted nodes. Specifically, we cannot connect consecutive nodes n_i and n_{i+1}, unless we are willing to accept multi-graphs.

    So the question is, what is the maximum number of nodes by which I can extend a regular graph by insertion? The minimum is r-1, because to keep regularity r, we need to insert a r-2 regular graph and the smallest r-2 (connected) regular graph has r-1 nodes (a clique). But can insert *any* r-2 regular graph into an r-regular graph? While there seems to be no limit on the size of the inserted graph, it appears that some insertions will not be possible (because no matter how you try to insert, it can’t escape from creating a multi-graph of the resultant graph).

    I don’t know whether there is a simple way to prove which r-2 regular graph can be inserted into a given r regular graph, and which cannot be.

    -sri

  3. sanket says:

    You are right about inserting any r-2 regular graph. Inserting a r-1 clique is the minimal case. It is also the easiest to visualize. The other questions you asked need more consideration.

  4. […] theory — sanket @ 12:08 am Tags: bounds, regular graphs As sri rightly pointed out in the comments section of the previous post, clique insertion is just one way to extend an r-regular graph into a bigger r-regular graph. We […]

%d bloggers like this: