Diskretnaya Matematika
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskr. Mat.: Year: Volume: Issue: Page: Find

 Diskr. Mat., 2020, Volume 32, Issue 1, Pages 74–80 (Mi dm1595)

On distance-regular graphs with $c_2=2$

A. A. Makhnevab, M. S. Nirovaab

a Institute of Mathematics and Mechanics UB RAS
b Kabardino-Balkarskii State University

Abstract: Let $\Gamma$ be a distance-regular graph of diameter 3 with $c_2=2$ (any two vertices with distance 2 between them have exactly two common neighbors). Then the neighborhood $\Delta$ of the vertex $w$ in $\Gamma$ is a partial line space. In view of the Brouwer–Neumaier result either $\Delta$ is the union of isolated $(\lambda+1)$-cliques or the degrees of vertices $k\ge \lambda(\lambda+3)/2$, and in the case of equality $k=5, \lambda=2$ and $\Gamma$ is the icosahedron graph. A. A. Makhnev, M. P. Golubyatnikov and Wenbin Guo have investigated distance-regular graphs $\Gamma$ of diameter 3 such that $\bar \Gamma_3$ is the pseudo-geometrical network graph. They have found a new infinite set $\{2u^2-2m^2+4m-3,2u^2-2m^2,u^2-m^2+4m-2;1,2,u^2-m^2\}$ of feasible intersection arrays for such graphs with $c_2=2$. Here we prove that some distance-regular graphs from this set do not exist. It is proved also that distance-regular graph with intersection array $\{22,16,5;1,2,20\}$ does not exist.

Keywords: distance-regular graph, partial line space, graph with $c_2=2$

 Funding Agency Grant Number Ural Branch of the Russian Academy of Sciences 18-1-1-17 Ministry of Education and Science of the Russian Federation 02.A03.21.0006

DOI: https://doi.org/10.4213/dm1595

Full text: PDF file (435 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2021, 31:6, 397–401

Bibliographic databases:

UDC: 519.172

Citation: A. A. Makhnev, M. S. Nirova, “On distance-regular graphs with $c_2=2$”, Diskr. Mat., 32:1 (2020), 74–80; Discrete Math. Appl., 31:6 (2021), 397–401

Citation in format AMSBIB
\Bibitem{MakNir20} \by A.~A.~Makhnev, M.~S.~Nirova \paper On distance-regular graphs with $c_2=2$ \jour Diskr. Mat. \yr 2020 \vol 32 \issue 1 \pages 74--80 \mathnet{http://mi.mathnet.ru/dm1595} \crossref{https://doi.org/10.4213/dm1595} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=4075903} \elib{https://elibrary.ru/item.asp?id=47550529} \transl \jour Discrete Math. Appl. \yr 2021 \vol 31 \issue 6 \pages 397--401 \crossref{https://doi.org/10.1515/dma-2021-0035} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000730399800003} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85121800286}