|
Applied Graph Theory
About the maximum number of vertices in primitive regular graphs with exponent equals $3$
I. V. Los, M. B. Abrosimov Saratov State University, Saratov, Russia
Abstract:
Some results on the maximum number of vertices in primitive regular graphs with exponent $3$ are presented. We have found upper bound of this number depending on the degree $p: n_p \le p^3-p^2-3p+5$. Also, the exact value of the maximum number of vertices in primitive cubic graphs with exponent $3$ is given: $n_3 = 12$. A computation experiment has been conducted, and we have found the number of primitive regular graphs with degree $p \le 9$, number of vertices $n \le 16$ and exponent $3$ for each $(n,p)$ pair.
Keywords:
primitive graph, regular graph, the maximum number of vertices.
Citation:
I. V. Los, M. B. Abrosimov, “About the maximum number of vertices in primitive regular graphs with exponent equals $3$”, Prikl. Diskr. Mat., 2025, no. 67, 98–109
Linking options:
https://www.mathnet.ru/eng/pdm865 https://www.mathnet.ru/eng/pdm/y2025/i1/p98
|
|