HomeIssuesThe maximum number of vertices of primitive regular graphs of orders 2, 3, 4 with exponent 2

The maximum number of vertices of primitive regular graphs of orders 2, 3, 4 with exponent 2 | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2021. № 52. DOI: 10.17223/20710410/52/6

In 2015, the results were obtained for the maximum number of vertices nk in regular graphs of a given order k with a diameter 2: n2 = 5, n3 = 10, n4 = 15. In this paper, we investigate a similar question about the largest number of vertices npk in a primitive regular graph of order k with exponent 2. All primitive regular graphs with exponent 2, except for the complete one, also have diameter d = 2. The following values were obtained for primitive regular graphs with exponent 2: np2 = 3, np3 = 4, np4 = 11.
Download file
Counter downloads: 47
  • Title The maximum number of vertices of primitive regular graphs of orders 2, 3, 4 with exponent 2
  • Headline The maximum number of vertices of primitive regular graphs of orders 2, 3, 4 with exponent 2
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 52
  • Date:
  • DOI 10.17223/20710410/52/6
Keywords
primitive graph, primitive matrix, exponent, regular graph
Authors
References
Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. V. 52. P. 642-648.
Сачков В. Н., Ошкин И. Б. Экспоненты классов неотрицательных матриц // Дискретная математика. 1993. №2. С. 150-159.
Салий В. Н. Минимальные примитивные расширения ориентированных графов // Прикладная дискретная математика. 2008. №1(1). С. 116-119.
Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. №2(11). С. 101-112.
Фомичев В. М., Авезова Я. Э. Точная формула экспонентов перемешивающих орграфов регистровых преобразований // Дискретный анализ и исследование операций. 2020. №2(27). С. 117-135.
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.
Bueno M. I. and Furtado S. On the exponent of r-regular primitive matrices // ELA. 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 Appl. 2005. No. 407. P. 162-168.
Hoa V.D. and Do M. T. k-Regular graph with diameter 2 // Int. J. Adv. Comput. Technol. 2015. V. 4. No. 5. P.14-19.
Лось И. В., Абросимов М. Б., Костин С. В. К вопросу о примитивных однородных графах с экспонентом, равным 2 и 3 // Компьютерные науки и информационные технологии. Материалы Междунар. науч. конф. Саратов: Изд. центр «Наука», 2018. С. 251-253.
Костин С. В. Об использовании задач по теории графов для интеллектуального развития учащихся // Математика в образовании: сб. статей. Вып. 10 / под ред. И. С. Емельяновой. Чебоксары: Изд-во Чуваш. ун-та. 2014. С. 68-74.
The maximum number of vertices of primitive regular graphs of orders 2, 3, 4 with exponent 2 | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2021. № 52. DOI: 10.17223/20710410/52/6
The maximum number of vertices of primitive regular graphs of orders 2, 3, 4 with exponent 2 | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2021. № 52. DOI: 10.17223/20710410/52/6
Download full-text version
Counter downloads: 153