The characterization of large order \((3, r)\)-regular graphs (Q2831589)

A simple graph \(G=(V(G),E(G))\) is \((t,r)\)-regular, if the cardinality of the neighbourhood set of every \(t\) independent vertices is \(r\). Thus, an \(r\)-regular graph is \((1,r)\)-regular, and a graph is \((t,0)\)-regular, if and only if it is a set of \(n\) isolated vertices. The \(t\)-kernel of \(G\), denoted \(\mathrm{Ker}_{t}(G)\), is the set of vertices that do not belong to any set of \(t\) independent vertices. The \(t\)-shell of \(G\), denoted \(\mathrm{Shell}_{t}(G)\), is the set \(V(G) \setminus\mathrm{Ker}_{t}(G)\), i.e., the set of vertices that are in some set of \(t\) independent vertices. The objective of this paper is to study \((3,r)\)-regular graphs and to characterize these for \(r=1,2,3\), similar to the results presented in [\textit{P. D. Johnson jun.} and \textit{E. J. Morgan}, Bull. Inst. Comb. Appl. 39, 21--26 (2003; Zbl 1049.05071)]. The main result can be formulated as follows. For \(r \geq 1\), let \(G\) be a \((3,r)\)-regular graph of order \(n\). Moreover, let \(N(3,1)=5\), \(N(3,2)=7\), \(N(3,3)=9\), \(N(3,4)=16\) and \(N(3,r)=(r-1)^{2}+r+2\) for \(r \geq 5\). Then \(\mathrm{Shell}_{3}(G)\) is a disjoint union of cliques \(mK_{p}\) for some integers \(m \geq 3\) and \(p \geq 1\) such that \(r=3(p-1)+|\mathrm{Ker}_{3}(G)|\).