![]() ![]() ![]() ![]() |
![]() ![]() ![]() ![]() |
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).
See also Complete Graph, Cyclic Graph, Regular Graph
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.