Прикладная теория графов

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

И. В. Лось, М. Б. Абросимов

Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского, г. Саратов, Россия

Аннотация: Рассматривается вопрос о максимальном числе вершин в примитивных неориентированных регулярных графах с экспонентом, равным $3$. Получена оценка сверху этого числа в зависимости от порядка графа $p: n_p \le p^3-p^2-3p+5$. Найдено точное значение максимального числа вершин в примитивных кубических графах с экспонентом, равным $3$: $n_3 = 12$. Проведён вычислительный эксперимент и найдено число примитивных регулярных графов порядка $p\le 9$ с числом вершин $n \le 16$ и экспонентом, равным $3$, для всех пар $(n,p)$.

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

УДК: 519.17

DOI: 10.17223/20710410/67/5