For a Vertex of a Graph, let and denote the Subgraphs of induced by the 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 Vertex set consists of Vertices arranged in an square with two Vertices adjacent Iff they are in the same row or column).

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

© 1996-9

1999-05-26