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
DOI: https://doi.org/10.1090/S1061-0022-07-00959-4
Published electronically: May 25, 2007
MathSciNet review: 2262582
Full-text PDF

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, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 18, Springer-Verlag, Berlin, 1989. MR 1002568
  • 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 (Russian, with Russian summary); English transl., Izv. Math. 68 (2004), no. 1, 159–180. MR 2096940, https://doi.org/10.1070/IM2004v068n01ABEH000469
  • 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 (Russian, with Russian summary); English transl., Discrete Math. Appl. 13 (2003), no. 1, 85–104. MR 1996746, https://doi.org/10.1515/156939203321669573
  • 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 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, https://doi.org/10.1070/SM1996v187n10ABEH000165
  • 8. 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

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
Email: makhnev@imm.uran.ru

DOI: https://doi.org/10.1090/S1061-0022-07-00959-4
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