For a graph vertex of a graph, let and denote the subgraphs of induced by the graph vertices adjacent to and nonadjacent to , respectively. The empty graph is defined to be superregular, and is said to be superregular if is a regular graph and both and are superregular for all .
The superregular graphs are precisely , (), (), and the complements of these graphs, where is a cyclic graph, is a complete graph and is disjoint copies of , and is the Cartesian product of with itself (the graph whose graph vertex set consists of graph vertices arranged in an 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
More things to try:
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.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Superregular Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SuperregularGraph.html