Another extremal problem on edge-regular graphs.
by
K.J. Roblee
Troy University
Coauthors: P.D. Johnson, Jr. and T. Smotzer

A regular graph is said to be edge-regular provided there is a nonnegative l such that every pair of adjacent vertices has l common neigbors. It follows that for an edge-regular graph, there is a nonnegative p such that every adjacent vertex-pair has p common non-neighbors. It has been proven that for such values of l > 0 and p ≥ 0, for an edge-regular graph, we have that the order n ≤ 3l+ 3p. This inequality is sharp, and, for the most part, the extremal graphs for this inquality have been characterized. In this case, it happens that the common neighbor set of every pair of adjacent vertices is an independent set. Here, we consider the problem of characterizing the edge-regular graphs where n = 3l+3p -2, where l > 0 and p ≥ 0, and where the common neighbor set of any adjacent vertex pair is independent.

Date received: April 24, 2009