Эта публикация цитируется в
2 статьях
Остовные деревья с большим количеством висячих вершин: новые нижние оценки через количество вершин степеней 3 и не менее 4
Д. В. Карпов С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, Санкт-Петербург, Россия
Аннотация:
В работе доказывается, что у связного графа
$G$, в котором
$s$ вершин степени 3 и
$t$ вершин степени не менее 4, существует остовное дерево, в котором
$\frac25t+\frac15s+\alpha$ висячих вершин, где
$\alpha\ge\frac85$. Доказано, что для всех графов, кроме трёх исключений,
$\alpha\ge2$. Исключение составляют единственный регулярный граф степени 4 на 6 вершинах и два регулярных графа степени 4 на 8 вершинах (в которых каждое ребро входит в треугольник).
Приводится бесконечная серия примеров графов, содержащих только вершины степеней 3 и 4, для которых максимальное количество висячих вершин в остовном дереве равно
$\frac25t+\frac15s+2$. Тем самым, доказана точность всех оценок. Библ. – 12 назв.
Ключевые слова:
остовное дерево, висячие вершины, количество висячих вершин.
УДК:
519.172.1 Поступило: 03.11.2012