RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2021 Number 52, Pages 97–104 (Mi pdm740)

Applied Graph Theory

The maximum number of vertices of primitive regular graphs of orders $2, 3, 4$ with exponent $2$

M. B. Abrosimova, S. V. Kostinb, I. V. Losa

a Saratov State University, Saratov, Russia
b MIREA — Russian Technological University, Moscow, Russia

Abstract: In 2015, the results were obtained for the maximum number of vertices $ n_k $ in regular graphs of a given order $ k $ with a diameter $2$: $n_2 = 5$, $n_3 = 10$, $n_4 = 15$. In this paper, we investigate a similar question about the largest number of vertices $ np_k $ in a primitive regular graph of order $ k $ with exponent $2$. All primitive regular graphs with exponent $2$, except for the complete one, also have diameter $d =2 $. The following values were obtained for primitive regular graphs with exponent $2$: $np_2 = 3$, $np_3 = 4$, $np_4 = 11$.

Keywords: primitive graph, primitive matrix, exponent, regular graph.

UDC: 519.17

DOI: 10.17223/20710410/52/6



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024