Some Extremal Problems for Edge-Regular Graphs

摘要

We consider the class ER.(n, d, λ) of edge-regular graphs for some n> d > λ. i.e., graphs regular of degree d on n vertices, with each pair of adjacent vertices having λ common neighbors. It has previously been shown that for such graphs with λ > 0 we have n ≥ 3(d — λ) and much has been done to characterize such graphs when equality holds. Here we show that n ≥ 3(d — λ) + 1 if λ > 0 and d is odd and contribute to the characterization of the graphs in ER(n, d, λ), λ > 0, n=3(d — λ) +1 by proving some lemmas about the structure of such graphs, and by classifying such graphs that satisfy a strong additional requirement. that the number t=t(u,υ) of edges in the subgraph induced by the λ common neighbors of any two adjacent vertices u and υ is positive, and independent of u and υ. The result is that there are exactly 4 such graphs: K_4 and 3 strongly regular graphs.