RUS  ENG
Full version
JOURNALS // Matematicheskie Zametki // Archive

Mat. Zametki, 2009 Volume 86, Issue 1, Pages 14–21 (Mi mzm8362)

Classification of Ryser Graphs

A. L. Gavrilyuk

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

Abstract: The object of study is $(2,r_1,r_2)$-regular graphs in which the union of the neighborhoods of two different vertices $u$ and $w$ contains $r_1$ or $r_2$ vertices, depending on whether $u$ and $w$ are adjacent. It is proved that such graphs either are strongly regular or decompose into the direct sum of a complete multipartite graph and a clique. Earlier, the case $r_1=r_2$ was studied by other authors.

Keywords: Ryser graph, strongly regular graph, distance-regular graph, multipartite graph.

UDC: 519.17

Received: 19.06.2008

DOI: 10.4213/mzm8362


 English version:
Mathematical Notes, 2009, 86:1, 19–25

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024