|
Дискретная математика, 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'$ всех остальных ребер, соединяющих вершины, инцидентные ребрам этого паросочетания.
Статья поступила: 14.07.1989
Образец цитирования:
В. Е. Тараканов, “О реберном числе независимости и числе покрытия для регулярных графов”, Дискрет. матем., 2:1 (1990), 16–25; Discrete Math. Appl., 2:1 (1992), 1–10
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm831 https://www.mathnet.ru/rus/dm/v2/i1/p16
|
Статистика просмотров: |
Страница аннотации: | 461 | PDF полного текста: | 253 | Первая страница: | 3 |
|