RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика. Приложение // Архив

ПДМ. Приложение, 2017, выпуск 10, страницы 131–134 (Mi pdma340)

Эта публикация цитируется в 3 статьях

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

К вопросу о примитивных однородных графах с экспонентом равным 2

М. Б. Абросимовa, С. В. Костинb

a Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского, г. Саратов
b Московский технологический университет (МИРЭА), г. Москва

Аннотация: Рассматриваются примитивные однородные графы с экспонентом равным 2. Уточняется известный результат о том, что число рёбер неориентированного $n$-вершинного графа с экспонентом 2 должно быть не меньше $(3n-3)/2$ для нечётного $n$ и $(3n-2)/2$ для чётного $n$. Для однородных графов с экспонентом 2 при $n>4$ минимальное число рёбер есть $2n$.

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

УДК: 519.17

DOI: 10.17223/2226308X/10/51



© МИАН, 2024