RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2007 Volume 48, Number 4, Pages 817–832 (Mi smj1747)

This article is cited in 4 papers

A new estimate for the vertex number of an edge-regular graph

A. A. Makhnev, D. V. Paduchikh

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

Abstract: Given a connected edge-regular graph $\Gamma$ with parameters $(v,k,\lambda)$ and $b_1=k-\lambda-1$, we prove that in the case $k\geqslant3b_1-2$ either $|\Gamma_2(u)|(k-2b_1+2)<kb_1$ for every vertex $u$ or $\Gamma$ is a polygon, the edge graph of a trivalent graph without triangles that has diameter greater than 2, the icosahedral graph, the complete multipartite graph $K_{r\times2}$, the $3\times3$-grid, the triangular graph $T(m)$ with $m\leqslant7$, the Clebsch graph, or the Schläfli graph.

Keywords: edge-regular graph, characterization by parameters.

Received: 22.11.2005


 English version:
Siberian Mathematical Journal, 2007, 48:4, 653–665

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025