Geodesic
About the maximum number of vertices in primitive regular graphs with exponent~3
Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 112-114.

Voir la notice de l'article provenant de la source Math-Net.Ru

This paper presents some results about the maximum number of vertices in primitive regular graphs with exponent 3. A computational experiment was conducted. We have found the numbers of primitive regular graphs with degree $p\le9$, number of vertices $n\le16$ and exponent 3 for each pair $(n,p)$. We have found the upper bound $n_p$ for the maximum number of vertices in primitive regular graphs with exponent 3 and degree $p$: $n_p\le3(p-1)+2(p-2)(p-1)+(p-2)^2(p+1)$. Also, we have found the exact value of the maximum number of vertices in primitive regular graphs with degree 3 and exponent 3, namely, $n_3=12$.
Keywords: primitive graph, regular graph, the maximum number of vertices. 
@article{PDMA_2018_11_a34,
     author = {I. V. Los and M. B. Abrosimov},
     title = {About the maximum number of vertices in primitive regular graphs with exponent~3},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {112--114},
     publisher = {mathdoc},
     number = {11},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2018_11_a34/}
}
TY  - JOUR
AU  - I. V. Los
AU  - M. B. Abrosimov
TI  - About the maximum number of vertices in primitive regular graphs with exponent~3
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2018
SP  - 112
EP  - 114
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2018_11_a34/
LA  - ru
ID  - PDMA_2018_11_a34
ER  - 
%0 Journal Article
%A I. V. Los
%A M. B. Abrosimov
%T About the maximum number of vertices in primitive regular graphs with exponent~3
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2018
%P 112-114
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2018_11_a34/
%G ru
%F PDMA_2018_11_a34
I. V. Los; M. B. Abrosimov. About the maximum number of vertices in primitive regular graphs with exponent~3. Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 112-114. http://geodesic.mathdoc.fr/item/PDMA_2018_11_a34/

[1] Wielandt H., “Unzerlegbare nicht negative Matrizen”, Math. Zeitschr., 52 (1950), 642–648 | DOI | MR | Zbl

[2] Knyazev A. V., Otsenki ekstremalnykh znachenii osnovnykh metricheskikh kharakteristik psevdosimmetricheskikh grafov, Dis. $\dots$ dokt. fiz.-mat. nauk, M., 2002, 203 pp.

[3] Kogos K. N., Fomichev V. M., “Polozhitelnye svoistva neotritsatelnykh matrits”, Prikladnaya diskretnaya matematika, 2012, no. 4(18), 5–13

[4] Jin M., Lee S. G., Seol H. G., “Exponents of $r$-regular primitive matrices”, Inform. Center Math. Sci., 6:2 (2003), 51–57

[5] Bueno M. I., Furtado S., “On the exponent of $r$-regular primitive matrices”, Electronic J. Linear Algebra, 17 (2008), 28–47 | DOI | MR | Zbl

[6] Kim B., Song B., Hwang W., “Nonnegative primitive matrices with exponent 2”, Linear Algebra and its Appl., 407 (2005), 162–168 | DOI | MR | Zbl

[7] Abrosimov M. B., Kostin S. V., “K voprosu o primitivnykh odnorodnykh grafakh s eksponentom, ravnym 2”, Prikladnaya diskretnaya matematika. Prilozhenie, 2017, no. 10, 131–134

[8] Meringer M., “Fast Generation of Regular Graphs and Construction of Cages”, J. Graph Theory, 30 (1999), 137–146 | 3.0.CO;2-G class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[9] Smart N., “Algoritmy vozvedeniya v stepen”, Kriptografiya, Tekhnosfera, M., 2005