Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Абросимов М. Б., Лось И. В., Костин С. В. Примитивные однородные графы с экспонентом 2 и числом вершин до 16 // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2021. Т. 21, вып. 2. С. 238-245. DOI: 10.18500/1816-9791-2021-21-2-238-245

Опубликована онлайн: 
31.05.2021
Полный текст:
(downloads: 34)
Язык публикации: 
русский
Рубрика: 
Тип статьи: 
Научная статья
УДК: 
519.17
DOI: 
10.18500/1816-9791-2021-21-2-238-245

Примитивные однородные графы с экспонентом 2 и числом вершин до 16

Авторы: 
Абросимов Михаил Борисович, Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского
Лось Илья Викторович, Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского
Костин Сергей Вячеславович, Российский технологический университет МИРЭА (РТУ МИРЭА)
Аннотация: 

Граф $G = (V, \alpha)$ называется примитивным, если существует натуральное $k$, такое что между любой парой вершин графа $G$ существует маршрут длины $k$. В работе рассматриваются неориентированные графы с экспонентом 2. Доказывается критерий примитивности графа с экспонентом 2 и необходимое условие. Граф является примитивным с экспонентом 2 тогда и только тогда, когда его диаметр равен 1 или 2, а каждое его ребро входит в треугольник. Описывается вычислительный эксперимент по построению всех примитивных однородных графов с числом вершин до 16 и экспонентом 2, анализируются его результаты. Приводятся все однородные графы порядка 2, 3 и 4, которые являются примитивными с экспонентом 2, а для однородных графов порядка 5 определяется количество примитивных графов с экспонентом 2.

Благодарности: 
Работа выполнена при поддержке Минобрнауки России в рамках выполнения государственного задания (проект № FSRR-2020-0006).
Список источников: 
  1. Frobenius F. G. Uber Matrizen aus nicht negativen Elementen. Berlin : Sitzungsberichteder Koniglich Preussischen Akademie der Wissenschaften, 1912. 22 p.
  2. Wiеlandt H. Unzerlegbare, nicht negative Matrizen // Mathematische Zeitschrift. 1950. Vol. 52. P. 642–648. https://doi.org/10.1007/BF02230720
  3. Фомичев В. М., Авезова Я. Э., Коренева А. М., Кяжин С. Н. Примитивность и локальная примитивность орграфов и неотрицательных матриц // Дискретный анализ и исследование операций. 2018. Т. 25, вып. 3. С. 95–125. https://doi.org/10.17377/daio.2018.25.595
  4. Jin M., Lee S. G., Seol H. G. Exponents of r-regular primitive matrices // Information Center for Mathematical Sciences. 2003. Vol. 6, № 2. P. 51–57.
  5. Bueno M. I., Furtado S. On the exponent of R-regular primitive matrices // ELA. The Electronic Journal of Linear Algebra. 2008. Vol. 17. P. 28–47. https://doi.org/10.13001/1081- 3810.1247
  6. Kim B., Song B., Hwang W. Nonnegative primitive matrices with exponent 2 // Linear Algebra and its Applications. 2005. № 407. P. 162–168. https://doi.org/10.1016/j.laa.2005.05.018
  7. Сачков В. Н., Ошкин И. Б. Экспоненты классов неотрицательных матриц // Дискретная математика. 1993. Т. 5, № 2. P. 150–159.
  8. Салий В. Н. Минимальные примитивные расширения ориентированных графов // Прикладная дискретная математика. 2008. № 1 (1). P. 116–119.
  9. Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. № 2 (12). P. 101–112.
  10. Фомичев В. М., Авезова Я. Э. Точная формула экспонентов перемешивающих орграфов регистровых преобразований // Дискретный анализ и исследование операций. 2020. Т. 27, вып. 2 (27). P. 117–135. https://doi.org/10.33048/daio.2020.27.670
  11. Meringer M. Fast generation of regular graphs and construction of cages // Journal of Graph Theory. 1999. Vol. 30, iss. 2. P. 137–146. https://doi.org/10.1002/(SICI)1097- 0118(199902)30:2<_x0031_37:_x003a_AID-JGT7>3.0.CO;2-G
  12. Абросимов М. Б., Костин С. В. К вопросу о примитивных однородных графах с экспонентом равным 2 // Прикладная дискретная математика. Приложение. 2017. № 10. С. 131–134. https://doi.org/10.17223/2226308X/10/51
  13. Костин С. В. Об использовании задач по теории графов для интеллектуального развития учащихся // Математика в образовании. 2014. Вып. 10. С. 68–74.
Поступила в редакцию: 
24.07.2020
Принята к публикации: 
12.10.2020
Опубликована: 
31.05.2021