TOPICS

# Superregular Graph

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).

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

Superregular Graph

## Cite this as:

Weisstein, Eric W. "Superregular Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SuperregularGraph.html