Another Extremal Family of Edge-Regular Graphs

摘要

A d-regular graph is edge-regular if there exists an integer λ such that any two adjacent vertices of the graph have exactly λ common neighbors. Here we show that if G is edge-regular with λ > 0, and if the set of common neighbors of each pair of adjacent vertices is independent, then d ≥ 2λ, with equality only if G = mK_(λ,λ,λ), for some positive integer m.