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 р: np ≤ р3 - р2 - 3р + 5. Also, the exact value of the maximum number of vertices in primitive cubic graphs with exponent 3 is given: n3 = 12. A computation experiment has been conducted, and we have found the number of primitive regular graphs with degree р ≤ 9, number of vertices n ≤ 16 and exponent 3 for each (п,р) pair.
Download file
Counter downloads: 16
- Title About the maximum number of vertices in primitive regular graphs with exponent equals 3
- Headline About the maximum number of vertices in primitive regular graphs with exponent equals 3
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 67
- Date:
- DOI 10.17223/20710410/67/5
Keywords
primitive graph, regular graph, the maximum number of verticesAuthors
References
Смарт Н. Криптография. М.: Техносфера, 2005. 528с.
Haffman A. J. and Singletan R. R. Moore graphs with diameter 2 and 3 // IBM J. Research and Development. 1960. V. 4. P.497-504.
Meringer M. Fast generation of regular graphs and construction of cages // J. Graph Theory. 1999. V. 30. P. 137-146.
Kim B., Sang B., and Hwang W. Nonnegative primitive matrices with exponent 2 // Linear Algebra Appl. 2005. No. 407. P. 162-168.
Buena M. I. and Furtada S. On the exponent of r-regular primitive matrices // ELA. Electronic J. Linear Algebra. 2008. V. 17. P.28-47.
Jin M., Lee S. G., and Seal H. G. Exponents of r-regular primitive matrices // Inform. Center for Math. Sci. 2003. V. 6. No. 2. P.51-57.
Абросимов М. Б., Костин С. В., Лось И. В. О наибольшем числе вершин примитивных однородных графов порядка 2, 3, 4 с экспонентом, равным 2 // Прикладная дискретная математика. 2021. №52. С. 97-104.
Абросимов М. Б., Лось И. В., Костин С. В. Примитивные однородные графы с экспонентом 2 и числом вершин до 16 // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2021. T.21. Вып.2. С. 238-245.
Фомичев В. М., Авезова Я. Э. Точная формула экспонентов перемешивающих орграфов регистровых преобразований // Дискрет. анализ исслед. опер. 2020. №2(27). С. 117-135.
Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. №2(11). С. 101-112.
Салий В. Н. Минимальные примитивные расширения ориентированных графов // Прикладная дискретная математика. 2008. №1(1). С. 116-119.
Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. V. 52. P. 642-648.
Сачков В. Н., Ошкин И. Б. Экспоненты классов неотрицательных матриц // Дискретная математика. 1993. Т. 5. №2. С. 150-159.
About the maximum number of vertices in primitive regular graphs with exponent equals 3 | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 67. DOI: 10.17223/20710410/67/5
Download full-text version
Counter downloads: 220