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 \geq 2 \), and let \( G \) be a \((2, r)\)-regular graph. If \( n \) is sufficiently large, then \( G \) is isomorphic to \( K_s + mK_p \), 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’)\)-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.