×

On edge-regular graphs with \(k\geq 3b_1-3\). (English. Russian original) Zbl 1157.05338

St. Petersbg. Math. J. 18, No. 4, 517-538 (2007); translation from Algebra Anal. 18, No. 4, 10-38 (2006).
Summary: 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\geq 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)|\leq 1\) for each vertex \( u\).

MSC:

05E30 Association schemes, strongly regular graphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[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. · Zbl 0747.05073
[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) · Zbl 1157.05326
[3] S. P. Zaripov, A. A. Makhnev, and I. P. Yablonko, Edge-regular graphs of diameter \( 2c\lambda\geq 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) · Zbl 1099.05512
[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. · Zbl 1080.05100
[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. · Zbl 1050.05119
[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. · Zbl 0868.05045
[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). · Zbl 1189.05174
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.