Available in electronic format
Available in print format
St.Petersburg Mathematical Journal
St.Petersburg Mathematical Journal
ISSN: 1547-7371(e) ISSN: 1061-0022(p)
     

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

Author(s): I. N. Belousov; 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
Posted: May 25, 2007
Retrieve article in: PDF DVI PostScript

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:

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

DOI: 10.1090/S1061-0022-07-00959-4
PII: S 1061-0022(07)00959-4
Keywords: Undirected graph, edge-regular graph, locally hexagonal graph
Received by editor(s): 27/JUN/2005
Posted: May 25, 2007
Additional Notes: Supported by RFBR (grant no. 05-01-00046) and RFBR-NSFC (grant no. 05-01-39000)
Copyright of article: Copyright 2007, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google