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.

UDC: 519.17

DOI: 10.17223/20710410/67/5