К вопросу о максимальном числе вершин в примитивных регулярных графах с экспонентом 3

Лось, Илья Викторович; Абросимов, Михаил Борисович

К вопросу о максимальном числе вершин в примитивных регулярных графах с экспонентом 3

Лось, Илья Викторович, Абросимов, Михаил Борисович

Дата публикации: 2025

Дата публикации в реестре: 2025-05-27T16:40:51Z

Аннотация:

Рассматривается вопрос о максимальном числе вершин в примитивных неориентированных регулярных графах с экспонентом, равным 3. Получена оценка сверху этого числа в зависимости от порядка графа p: np ≤ p3 − p2 − 3p + 5. Найдено точное значение максимального числа вершин в примитивных кубических графах с экспонентом, равным 3: n3 = 12. Проведен вычислительный эксперимент и найдено число примитивных регулярных графов порядка p ≤ 9 с числом вершин n ≤ 16 и экспонентом, равным 3, для всех пар (n, p).

Ключевые слова:
примитивные графы, регулярные графы, максимальное число вершин

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2025. № 67. С. 98-109