Some Minimal $(r,2,k)$-Regular Graphs Containing a Given Graph

Abstract

A graph $G$ is said to be a $(2,k)$-regular graph if each vertex of $G$ is at a distance two away from $k$ vertices of $G$. A graph $G$ is called an $(r,2,k)$-regular graph if each vertex of $G$ is at a distance $1$ away from $r$ vertices of $G$ and each vertex of $G$ is at a distance $2$ away from $k$ vertices of $G$ \cite{9}. This paper suggests a method to construct a $((m+n–2),2,(m–1)(n–1))$-regular graph of smallest order $mn$ containing a given graph $G$ of order $n\ge 2$ as an induced subgraph for any $m>1$.