RUS  ENG
Full version
JOURNALS // Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya // Archive

Izv. RAN. Ser. Mat., 2005 Volume 69, Issue 6, Pages 95–114 (Mi im667)

This article is cited in 4 papers

On a class of coedge regular graphs

A. A. Makhnev, D. V. Paduchikh

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

Abstract: We study graphs in which $\lambda(a,b)=\lambda_1,\lambda_2$ for every edge $\{a,b\}$ and all $\mu$-subgraphs are 2-cocliques. We give a description of connected edge-regular graphs for $k\geqslant(b_1^2+3b_1-4)/2$. In particular, the following examples confirm that the inequality $k>b_1(b_1+3)/2$ is a sharp bound for strong regularity: the $n$-gon, the icosahedron graph, the graph in $\operatorname{MP}(6)$ and the distance-regular graph of diameter 4 with intersection massive $\{x,x-1,4,1;1,2,x-1,x\}$, which is an antipodal 3-covering of the strongly regular graph with parameters $((x+2)(x+3)/6,x,0,6)$.

UDC: 519.14

MSC: 05C75, 05E30

Received: 25.05.2004

DOI: 10.4213/im667


 English version:
Izvestiya: Mathematics, 2005, 69:6, 1169–1187

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025