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

Abstract

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\ge 2$, and let $G$ be a $(2,r)$-regular graph. If $n$ is sufficiently large, then $G$ is isomorphic to $K_s+m{K}_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^{\prime })$-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.