Superregular Graph

For a Vertex $x$ of a Graph, let $\Gamma_x$ and $\Delta_x$ denote the Subgraphs of $\Gamma-x$ induced by the Vertices adjacent to and nonadjacent to $x$, respectively. The empty graph is defined to be superregular, and $\Gamma$ is said to be superregular if $\Gamma$ is a Regular Graph and both $\Gamma_x$ and $\Delta_x$ are superregular for all $x$.

The superregular graphs are precisely $C_5$, $mK_n$ ($m,n\geq 1$), $G_n$ ($n\geq 1$), and the complements of these graphs, where $C_n$ is a Cyclic Graph, $K_n$ is a Complete Graph and $mK_n$ is $m$ disjoint copies of $K_n$, and $G_n$ is the Cartesian product of $K_n$ with itself (the graph whose Vertex set consists of $n^2$ Vertices arranged in an $n\times n$ square with two Vertices adjacent Iff they are in the same row or column).

See also Complete Graph, Cyclic Graph, Regular Graph

References

Vince, A. ``The Superregular Graph.'' Problem 6617. Amer. Math. Monthly 103, 600-603, 1996.

West, D. B. ``The Superregular Graphs.'' J. Graph Th. 23, 289-295, 1996.