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

ID: 5250033