Graphs with Dense Constant Neigbourhoods

Abstract

Let $G$ be a finite graph and $x$ be its vertex. The $neighbourhood$ of $x$ in $G$, denoted $N_G(x)$, is a subgraph of $G$ induced by all vertices adjacent to $x$. $G$ is a $graphwithaconstantneighbourhood$ if there exists a graph $H$ such that $N_G(x)$ is isomorphic to $H$ for every vertex $x$ of $G$.

We completely characterize graphs with constant neighbourhoods isomorphic to complements of regular disconnected graphs.