|
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$.
Received: 27.06.2005
Citation:
I. N. Belousov, A. A. Makhnev, “On edge-regular graphs with $k\ge 3b_1-3$”, Algebra i Analiz, 18:4 (2006), 10–38; St. Petersburg Math. J., 18:4 (2007), 517–538
Linking options:
https://www.mathnet.ru/eng/aa77 https://www.mathnet.ru/eng/aa/v18/i4/p10
|
|