RUS  ENG
Full version
JOURNALS // Algebra i Analiz // Archive

Algebra i Analiz, 2006 Volume 18, Issue 4, Pages 10–38 (Mi aa77)

Research Papers

On edge-regular graphs with $k\ge 3b_1-3$

I. N. Belousov, A. A. Makhnev

Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences

Abstract: An undirected graph on $v$ vertices in which the degrees of all vertices are equal to $k$ and each edge belongs to exactly $\lambda$ triangles is said to be edge-regular with parameters $(v,k,\lambda)$. It is proved that an edge-regular graph with parameters $(v,k,\lambda)$ such that $k\ge 3b_1-3$ either has diameter 2 and coincides with the graph $P(2)$ on 20 vertices or with the graph $M(19)$ on 19 vertices; or has at most $2k+4$ vertices; or has diameter at least 3 and is a trivalent graph without triangles, or the line graph of a quadrivalent graph without triangles, or a locally hexagonal graph; or has diameter 3 and satisfies $|\Gamma_3(u)|\le 1$ for each vertex $u$.

MSC: 05C60

Received: 27.06.2005


 English version:
St. Petersburg Mathematical Journal, 2007, 18:4, 517–538

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025