On edge-regular graphs with \(b_1=5\). (Russian) Zbl 1324.05159

Kazarina, V. I.; Makhnev, A. A.

Vladikavkaz. Mat. Zh. 11, No. 1, 29-42 (2009).

Summary: A nonoriented \(v\)-vertex graph in which the degrees of all the vertices are equal to \(k\) and every edge belongs to exactly \(\lambda\) triangles is said to be edge-regular with the parameters \((v,k,\lambda)\). By definition, put \(b_1=k-\lambda-1\). In [A. E. Brouwer et al., Distance-regular graphs. Berlin: Springer (1989; Zbl 0747.05073)], it is proved that a connected edge-regular graph with \(b_1=1\) is a polygon or a complete multipartite graph with parts of order 2. In [A. A. Makhnev and I. M. Minakova, Izv. Gomel. Gos. Univ. Im. F. Skoriny 2000, No. 3(16), Vopr. Algebry 16, 145–154 (2000; Zbl 1157.05326)] edge-regular graphs with \(b_1\leq 3\) and \(b_1=4\), \(k\geq 10\) are described. In the present paper, we classify connected edge-regular graphs with \(b_1=5\) under one of the following conditions: the graph is strongly regular or \(k\geq 14\).

MSC:

05C75

Structural characterization of families of graphs

Keywords:

edge-regular graph; triangular graph; Klein graph

Citations:

Zbl 0747.05073; Zbl 1157.05326