A. A. Makhnev, A. A. Vedenev, A. N. Kuznetsov, V. V. Nosov
On good pairs in edge-regular graphs
An undirected graph on v vertices of valences equal to k, whose each edge belongs to
exactly λ triangles is called edge-regular with parameters (v, k, λ). Let b
1 = k – λ – 1. We say that a pair of vertices u, w is good if these vertices have exactly k – 2b
1 + 1 common neighbours. We prove that if k ≥ 3b
1 – 1, then either for any vertex u at most two vertices in Γ form good pairs
with u, or k = 3b
1 – 1, Γ is a polygon or the icosahedron graph, and any two vertices which are 2
distant from each other form good pairs. We give a new upper bound for the number of vertices in an edge-regular graph of diameter two with k ≥ 3b
1 – 1. We prove that an edge-regular graph with parameters of the triangular graph T (n), n = 5; 6, the Clebsch graph, or the Schläfli graph coincides with the corresponding graph.
Discrete Mathematics and Applications, Walter de Gruyter
Print ISSN: 0924-9266
Volume: 13, 05/2003
Pages: 85 - 104
Show full article (external site)
Show all available items of this journal
Search
