Пусть $G$ -- связный граф, в котором максимальная цепочка последовательно соединённых вершин степени 2 состоит из $k>0$ вершин. В работе доказывается, что у графа $G$ существует остовное дерево, в котором более ${1\over 2k+4}$ всех вершин являются висячими. С помощью серии примеров показывается, что константу~${1\over 2k+4}$ нельзя заменить на большую.
Язык оригиналарусский
Страницы (с-по)78-87
ЖурналЗАПИСКИ НАУЧНЫХ СЕМИНАРОВ САНКТ-ПЕТЕРБУРГСКОГО ОТДЕЛЕНИЯ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН
Том381
СостояниеОпубликовано - 2010

    Области исследований

  • Остовное дерево, висячие вершины, количество висячих вершин [spanning tree, leaves, number of leaves]

ID: 5250033