|
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.
Received: 19.06.2008
Citation:
A. L. Gavrilyuk, “Classification of Ryser Graphs”, Mat. Zametki, 86:1 (2009), 14–21; Math. Notes, 86:1 (2009), 19–25
Linking options:
https://www.mathnet.ru/eng/mzm8362https://doi.org/10.4213/mzm8362 https://www.mathnet.ru/eng/mzm/v86/i1/p14
|
|