For a graph vertex x of a graph, let Γ_x and Δ_x denote the subgraphs of Γ - x induced by the graph vertices adjacent to and nonadjacent to x, respectively. The empty graph is defined to be superregular, and Γ is said to be superregular if Γ is a regular graph and both Γ_x and Δ_x are superregular for all x. The superregular graphs are precisely C_5, m K_n (m, n>=1), G_n (n>=1), and the complements of these graphs, where C_n is a cyclic graph, K_n is a complete graph and m K_n is m disjoint copies of K_n, and G_n is the Cartesian product of K_n with itself (the graph whose graph vertex set consists of n^2 graph vertices arranged in an n×n square with two graph vertices adjacent iff they are in the same row or column).

complete graph | cyclic graph | regular graph