On edge-regular graphs with $k\ge 3 b_1-3$
HTML articles powered by AMS MathViewer
- by
I. N. Belousov and A. A. Makhnev
Translated by: B. M. Bekker - St. Petersburg Math. J. 18 (2007), 517-538
- DOI: https://doi.org/10.1090/S1061-0022-07-00959-4
- Published electronically: May 25, 2007
- PDF | Request permission
Abstract:
An undirected graph on $v$ vertices in which the degrees of all vertices are equal to $k$ and each edge belongs to exactly $\lambda$ triangles is said to be edge-regular with parameters $(v,k,\lambda )$. It is proved that an edge-regular graph with parameters $(v,k,\lambda )$ such that $k\ge 3b_1-3$ either has diameter 2 and coincides with the graph $P(2)$ on 20 vertices or with the graph $M(19)$ on 19 vertices; or has at most $2k+4$ vertices; or has diameter at least 3 and is a trivalent graph without triangles, or the line graph of a quadrivalent graph without triangles, or a locally hexagonal graph; or has diameter 3 and satisfies $|\Gamma _3(u)|\le 1$ for each vertex $u$.References
- A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-regular graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 18, Springer-Verlag, Berlin, 1989. MR 1002568, DOI 10.1007/978-3-642-74341-2
- A. A. Makhnev and I. M. Minakova, On a class of edge-regular graphs, Izv. Gomel. Gos. Univ., Voprosy Algebry 3 (2000), 145–154. (Russian)
- S. P. Zaripov, A. A. Makhnev, and I. P. Yablonko, Edge-regular graphs of diameter $2c\lambda \ge 2k/3-2$, Proc. Ukrain. Math. Congr. (Kiev, 2001), Sect. 1: Algebra and Number Theory, Inst. Mat. Nats. Akad. Nauk Ukrainy, Kiev, 2003, pp. 46–61. (Russian)
- A. A. Makhnev, On the strong regularity of some edge-regular graphs, Izv. Ross. Akad. Nauk Ser. Mat. 68 (2004), no. 1, 159–182 (Russian, with Russian summary); English transl., Izv. Math. 68 (2004), no. 1, 159–180. MR 2096940, DOI 10.1070/IM2004v068n01ABEH000469
- A. A. Makhnev, A. A. Vedenev, A. N. Kuznetsov, and V. V. Nosov, On good pairs in edge-regular graphs, Diskret. Mat. 15 (2003), no. 1, 77–97 (Russian, with Russian summary); English transl., Discrete Math. Appl. 13 (2003), no. 1, 85–104. MR 1996746, DOI 10.1515/156939203321669573
- I. N. Belousov, E. I. Gurskiĭ, A. S. Dergach, and A. A. Makhnev, On almost good pairs in edge-regular graphs, Problems Theor. and Appl. Math. (Proc. Youthful Conf., Ekaterinburg 2004), pp. 9–11 (Russian)
- V. V. Kabanov and A. A. Makhnev, On separable graphs with some regularity conditions, Mat. Sb. 187 (1996), no. 10, 73–86 (Russian, with Russian summary); English transl., Sb. Math. 187 (1996), no. 10, 1487–1501. MR 1438977, DOI 10.1070/SM1996v187n10ABEH000165
- I. N. Belousov and A. A. Makhnev, On almost good vertex pairs in edge-regular graphs, Izv. Ural. Gos. Univ. Mat. Mekh. 7(36) (2005), 35–48, 189 (Russian, with English and Russian summaries). MR 2190940
Bibliographic Information
- I. N. Belousov
- Affiliation: Institute of Mathematics and Mechanics, Ural Branch of RAS, 16 Kovalevskaya Street, Ekaterinburg, Russia 620219
- A. A. Makhnev
- Affiliation: Institute of Mathematics and Mechanics, Ural Branch of RAS, 16 Kovalevskaya Street, Ekaterinburg, Russia 620219
- Email: makhnev@imm.uran.ru
- Received by editor(s): June 27, 2005
- Published electronically: May 25, 2007
- Additional Notes: Supported by RFBR (grant no. 05-01-00046) and RFBR-NSFC (grant no. 05-01-39000)
- © Copyright 2007 American Mathematical Society
- Journal: St. Petersburg Math. J. 18 (2007), 517-538
- MSC (2000): Primary 05C60
- DOI: https://doi.org/10.1090/S1061-0022-07-00959-4
- MathSciNet review: 2262582