Superregular Graph

For a graph vertex x of a graph, let Gamma_x and Delta_x denote the subgraphs of Gamma-x induced by the graph 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>=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 mK_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).

See also

Complete Graph, Cyclic Graph, Regular Graph

Explore with Wolfram|Alpha


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.

Referenced on Wolfram|Alpha

Superregular Graph

Cite this as:

Weisstein, Eric W. "Superregular Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications