By Peter D. Johnson Jr.
Auburn University
Abstract:
A graph is strongly
(t,r)-regular if and only if it is of order at least t, and the open
neighborhood of any set of t of its vertices has cardinality r. There are some easy--some would say
"trivial"--ways to find strongly (t,r)-regular
graphs. For instances: every matching
(graph consisting of a number of independent edges) is strongly (t,t)-regular
for t = 1,...,n, where n is the number of vertices of the
graph; every graph without isolated vertices, on n vertices, is strongly
(t,n)-regular if t = n+1 - (minimum degree of the
graph); and every r-regular graph is strongly (1,r)-regular.
The big question
is whether or not there exist "non-trivial" strongly (t,r)-regular
graphs, and this question is wide open for t > 2. For t = 2 something is known: the
regular strongly (2,r)-regular graphs form a variety of strongly regular
graphs, about which a good deal is known.
The big open problem in this case is:
do there exist non-regular strongly (2,r)-regular graphs? Some results and more problems will be
presented.
March 29, 2005
At 3:30 in Wallace 430