This article is cited in 3 papers

Applied Theory of Coding, Automata and Graphs

About primitive regular graphs with exponent 2

M. B. Abrosimov^a, S. V. Kostin<sup>b

a</sup> Saratov State University, Saratov
^b Moscow Technological University, Moscow

Abstract: Primitive regular graphs with exponent 2 are considered. We refine the known result that the number of edges of an undirected $n$-vertex graph with exponent 2 must be at least $(3n-3)/2$ for odd $n$ and $(3n-2)/2$ for an even $n$. For regular $n$-vertex graph with exponent 2 and $n>4$, the minimal number of edges is $2n$.

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

UDC: 519.17

DOI: 10.17223/2226308X/10/51