About the maximum number of vertices in primitive regular graphs with exponent
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 ^ 9, number of vertices n ^ 16 and exponent 3 for each pair (n,p). We have found the upper bound np for the maximum number of vertices in primitive regular graphs with exponent 3 and degree p: np ^ 3(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, n3 = 12.
Download file
Counter downloads: 143
Keywords
regular graph, the maximum number of vertices, primitive graph, регулярный граф, максимальное число вершин, примитивный графAuthors
| Name | Organization | |
| Los I. V. | Saratov National Research University | los.ilia.ru@gmail.com |
| Abrosimov M. B. | Saratov National Research University | mic@rambler.ru |
References
Смарт Н. Алгоритмы возведения в степень // Криптография. М.: Техносфера, 2005.
Абросимов М. Б., Костин С. В. К вопросу о примитивных однородных графах с экспонентом, равным 2 // Прикладная дискретная математика. Приложение. 2017. №10. С. 131-134.
Meringer M. Fast Generation of Regular Graphs and Construction of Cages // J. Graph Theory. 1999. V. 30. P. 137-146.
Bueno M. I. and Furtado S. On the exponent of r-regular primitive matrices // Electronic J. Linear Algebra. 2008. V. 17. P. 28-47.
Kim B., Song B., and Hwang W. Nonnegative primitive matrices with exponent 2 // Linear Algebra and its Appl. 2005. No. 407. P. 162-168.
Когос К. Н., Фомичев В. М. Положительные свойства неотрицательных матриц // Прикладная дискретная математика. 2012. №4(18). С. 5-13.
Jin M., Lee S. G., and Seol H. G. Exponents of r-regular primitive matrices // Inform. Center Math. Sci. 2003. V.6. No. 2. P. 51-57.
Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. B.52. S. 642-648.
Князев А. В. Оценки экстремальных значений основных метрических характеристик псевдосимметрических графов: дис.. докт. физ.-мат. наук. М., 2002. 203 с.
