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

Дискрет. матем., 1990, том 2, выпуск 1, страницы 16–25 (Mi dm831)

О реберном числе независимости и числе покрытия для регулярных графов

В. Е. Тараканов


Аннотация: Рассматривается совокупность регулярных графов на $N$ вершинах степени регулярности $n\geqslant3$. Устанавливается следующая оценка снизу реберного числа независимости $\beta_1(G)$ для такого графа $G$:
$$ \beta_1(n)\geqslant\frac n{3n-2}N, $$
а также связанная с ней оценка сверху числа реберного покрытия $\alpha_1(G)$ такого графа
$$ \alpha_1(G)\leqslant\biggl[\frac{2n-2}{3n-2}N\biggr] $$
($[x]$ – целая часть числа $x$). Эти оценки выводятся с помощью представления матрицы инцидентности $A$ графа $G$ из в некоторой канонической форме $\tilde A$ и ряда построений в $\tilde A$, позволяющих вывести соотношение $\mu'/\mu\geqslant n/2$ между числом ребер $\mu$ в произвольном наибольшем паросочетании графа $G$ и числом $\mu'$ всех остальных ребер, соединяющих вершины, инцидентные ребрам этого паросочетания.

УДК: 519.17

Статья поступила: 14.07.1989


 Англоязычная версия: Discrete Mathematics and Applications, 1992, 2:1, 1–10

Реферативные базы данных:


© МИАН, 2024