More extremal problems for edge-regular graphs
Abstract
An edge-regular graph is a simple graph which is d-regular, for some d, and for which there exists an integer λ such that any two adjacent vertices in the graph have exactly λ common neighbors. In previous work it was discovered that if λ > 0 then there is a natural upper bound on the number of vertices in the graph, and progress was made on the problem of characterizing the graphs achieving that upper bound. Here the opposite problem, of finding the edge-regular graphs of small order, is undertaken. In particular, edge-regular graphs with d = λ + k, k = 1, 2, 3, are characterized. In the case k = 3 the class of connected solutions is surprisingly rich, comprising three infinite families and two "sporadic" solutions, the complement of the Petersen graph and the icosahedron.
