General information
Latest issue
Forthcoming papers
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Izv. RAN. Ser. Mat.:

Personal entry:
Save password
Forgotten password?

Izv. RAN. Ser. Mat., 2004, Volume 68, Issue 1, Pages 159–182 (Mi izv469)  

This article is cited in 13 scientific papers (total in 14 papers)

On the strong regularity of some edge-regular graphs

A. A. Makhnev

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

Abstract: An undirected graph is said to be edge-regular with parameters $(v,k,\lambda)$ if it has $v$ vertices, each vertex has degree $k$, and each edge belongs to $\lambda$ triangles. We put $b_1=v-k-\lambda$. Brouwer, Cohen, and Neumaier proved that every connected edge-regular graph with $\lambda\geqslant k+1/2-\sqrt{2k+2}$ (equivalently, with $k\geqslant b_1(b_1+3)/2+1$) is strongly regular. In this paper we construct an example of an edge-regular, not strongly regular graph on 36 vertices with $k=27=b_1(b_1+3)/2$. This shows that the estimate above is sharp. We prove that every connected edge-regular graph with $\lambda\geqslant k+1/2-\sqrt{2k+8}$ (equivalently, $k\geqslant b_1(b_1+3)/2-2$ either satisfies $b_1\leqslant 3$, or has parameters $(36,27,20)$ or $(64,52,42)$, or is strongly regular.


Full text: PDF file (2371 kB)
References: PDF file   HTML file

English version:
Izvestiya: Mathematics, 2004, 68:1, 159–180

Bibliographic databases:

UDC: 519.14
MSC: 05C12, 05C75, 05E30
Received: 09.01.2001

Citation: A. A. Makhnev, “On the strong regularity of some edge-regular graphs”, Izv. RAN. Ser. Mat., 68:1 (2004), 159–182; Izv. Math., 68:1 (2004), 159–180

Citation in format AMSBIB
\by A.~A.~Makhnev
\paper On the strong regularity of some edge-regular graphs
\jour Izv. RAN. Ser. Mat.
\yr 2004
\vol 68
\issue 1
\pages 159--182
\jour Izv. Math.
\yr 2004
\vol 68
\issue 1
\pages 159--180

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. A. Makhnev, D. V. Paduchikh, “On a class of coedge regular graphs”, Izv. Math., 69:6 (2005), 1169–1187  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    2. I. N. Belousov, A. A. Makhnev, “On edge-regular graphs with $k\ge 3b_1-3$”, St. Petersburg Math. J., 18:4 (2007), 517–538  mathnet  crossref  mathscinet  zmath  elib
    3. A. A. Makhnev, D. V. Paduchikh, “A new estimate for the vertex number of an edge-regular graph”, Siberian Math. J., 48:4 (2007), 653–665  mathnet  crossref  mathscinet  zmath  isi  elib  elib
    4. M. S. Nirova, “O vpolne regulyarnykh grafakh s $b_1\le5$”, Sib. elektron. matem. izv., 4 (2007), 1–11  mathnet  mathscinet  zmath
    5. A. A. Makhnev, N. V. Chuksina, “O khoroshikh parakh vershin v reberno regulyarnykh grafakh s $k=3b_1-1$”, Tr. IMM UrO RAN, 14, no. 4, 2008, 119–134  mathnet  elib
    6. A. A. Makhnev, N. V. Chuksina, “O reberno regulyarnykh grafakh, v kotorykh kazhdaya vershina lezhit ne bolee chem v odnoi khoroshei pare”, Vladikavk. matem. zhurn., 10:1 (2008), 53–67  mathnet  mathscinet  elib
    7. K. S. Efimov, A. A. Makhnev, “Vpolne regulyarnye grafy s $\mu\le k-2b_1+3$”, Tr. In-ta matem., 16:1 (2008), 28–39  mathnet
    8. Konstantin S. Efimov, Aleksandr A. Makhnev, “Vpolne regulyarnye grafy s $b_1=6$”, Zhurn. SFU. Ser. Matem. i fiz., 2:1 (2009), 63–77  mathnet  elib
    9. K. S. Efimov, A. A. Makhnev, M. S. Nirova, “O vpolne regulyarnykh grafakh s $k=10$, $\lambda=3$”, Tr. IMM UrO RAN, 16, no. 2, 2010, 75–90  mathnet  elib
    10. K. S. Efimov, A. A. Makhnev, “O vpolne regulyarnykh grafakh s $k=11$, $\lambda=4$”, Uchen. zap. Kazan. un-ta. Ser. Fiz.-matem. nauki, 154, no. 2, Izd-vo Kazanskogo un-ta, Kazan, 2012, 83–92  mathnet
    11. K. S. Efimov, “Classification of amply regular graphs with $b_1=6$”, Proc. Steklov Inst. Math. (Suppl.), 283, suppl. 1 (2013), 46–55  mathnet  crossref  isi  elib
    12. M. S. Nirova, “On strongly regular graphs with $b_1<24$”, Proc. Steklov Inst. Math. (Suppl.), 283, suppl. 1 (2013), 111–118  mathnet  crossref  isi  elib
    13. “Makhnev Aleksandr Alekseevich (on his 60th birthday)”, Proc. Steklov Inst. Math. (Suppl.), 285, suppl. 1 (2014), 1–11  mathnet  crossref  mathscinet
    14. A. A. Makhnev, M. S. Nirova, “On strongly regular graphs with $b_1<26$”, Discrete Math. Appl., 24:1 (2014), 13–20  mathnet  crossref  crossref  mathscinet  elib  elib
  • Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Number of views:
    This page:397
    Full text:116
    First page:1

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019