Remote Access St. Petersburg Mathematical Journal

St. Petersburg Mathematical Journal

ISSN 1547-7371(online) ISSN 1061-0022(print)



On edge-regular graphs with $ k\ge 3 b_1-3$

Authors: I. N. Belousov and A. A. Makhnev
Translated by: B. M. Bekker
Original publication: Algebra i Analiz, tom 18 (2006), nomer 4.
Journal: St. Petersburg Math. J. 18 (2007), 517-538
MSC (2000): Primary 05C60
Published electronically: May 25, 2007
MathSciNet review: 2262582
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 $ \vert\Gamma_3(u)\vert\le 1$ for each vertex $ u$.

References [Enhancements On Off] (What's this?)

  • 1. A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-regular graphs, Ergeb. Math. Grenzgeb. (3), vol. 18, Springer-Verlag, Berlin, 1989. MR 1002568 (90e:05001)
  • 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)
  • 3. 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)
  • 4. A. A. Makhnev, On the strong regularity of some edge-regular graphs, Izv. Ross. Akad. Nauk Ser. Mat. 68 (2004), no. 1, 159-182; English transl., Izv. Math. 68 (2004), no. 1, 159-180. MR 2096940 (2005f:05171)
  • 5. 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; English transl., Discrete Math. Appl. 13 (2003), no. 1, 85-104. MR 1996746 (2004d:05205)
  • 6. I. N. Belousov, E. I. Gurskii, 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)
  • 7. V. V. Kabanov and A. A. Makhnev, On separable graphs with some regulatory conditions, Mat. Sb. 187 (1996), no. 10, 73-86; English transl., Sb. Math. 187 (1996), no. 10, 1487-1501. MR 1438977 (98d:05154)
  • 8. I. N. Belousov and A. A. Makhnev, On almost good vertex pairs in edge-regular graphs, Izv. Ural. Gos. Univ. Mat. Mekh. No. 7 (36) (2005), 35-48. (Russian) MR 2190940 (2006h:05241)

Similar Articles

Retrieve articles in St. Petersburg Mathematical Journal with MSC (2000): 05C60

Retrieve articles in all journals with MSC (2000): 05C60

Additional 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

Keywords: Undirected graph, edge-regular graph, locally hexagonal graph
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)
Article copyright: © Copyright 2007 American Mathematical Society

American Mathematical Society