Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Остовные деревья с большим количеством висячих вершин. / Карпов, Д.В.
в: ЗАПИСКИ НАУЧНЫХ СЕМИНАРОВ САНКТ-ПЕТЕРБУРГСКОГО ОТДЕЛЕНИЯ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН, Том 381, 2010, стр. 78-87.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Остовные деревья с большим количеством висячих вершин
AU - Карпов, Д.В.
PY - 2010
Y1 - 2010
N2 - Пусть $G$ -- связный граф, в котором максимальная цепочка последовательно соединённых вершин степени 2 состоит из $k>0$ вершин. В работе доказывается, что у графа $G$ существует остовное дерево, в котором более ${1\over 2k+4}$ всех вершин являются висячими. С помощью серии примеров показывается, что константу~${1\over 2k+4}$ нельзя заменить на большую.
AB - Пусть $G$ -- связный граф, в котором максимальная цепочка последовательно соединённых вершин степени 2 состоит из $k>0$ вершин. В работе доказывается, что у графа $G$ существует остовное дерево, в котором более ${1\over 2k+4}$ всех вершин являются висячими. С помощью серии примеров показывается, что константу~${1\over 2k+4}$ нельзя заменить на большую.
KW - Остовное дерево
KW - висячие вершины
KW - количество висячих вершин [spanning tree
KW - leaves
KW - number of leaves]
M3 - статья
VL - 381
SP - 78
EP - 87
JO - ЗАПИСКИ НАУЧНЫХ СЕМИНАРОВ САНКТ-ПЕТЕРБУРГСКОГО ОТДЕЛЕНИЯ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН
JF - ЗАПИСКИ НАУЧНЫХ СЕМИНАРОВ САНКТ-ПЕТЕРБУРГСКОГО ОТДЕЛЕНИЯ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН
SN - 0373-2703
ER -
ID: 5250033