Nested (2,r)-Regular Graphs and Their Network Properties

A graph G is a (t, r)-regular graph if every collection of t independent vertices is collectively adjacent to exactly r vertices. Let p, s, and m be positive integers, where m ≥ 2 and let G be a (2,r)-regular graph. If n is sufficiently large, then G is isomorphic to G = Ks + mKp, where 2(p- 1) + s = r. A nested (2, r)-regular graph is constructed by replacing selected cliques in a (2,r)-regular graph with a (2, r\u27)-regular graph and joining the vertices of the peripheral cliques. We examine the network properties such as the average path length, clustering coefficient, and the spectrum of these nested graphs