Реферат: The famous Nash-Williams' Theorem states that the edge set of a multigraph $G = (V,E)$ can be decomposed into $k$ forests iff for every subset $X ⊆ V$ the induced subgraph $G[X]$ contains at most $k(|X|−1)$ edges. In 2017, Glebov conjectured that if a graph $G$ satisfies the conditions of Nash-Williams' Theorem and has minimum degree $δ(G) ≥ k + 1$, then its edge set can be decomposed into $k$ forests such that none of these forests has an isolated vertex. Here we prove this conjecture. Moreover, we present a new proof of Nash-Williams' Theorem which allows us to prove a more general result on edge decomposition of a multigraph into $k$ forests such that the size of connected components in these forests is greater than a given constant.

Библиографическая ссылка: Глебов А.Н.
Новое доказательство теоремы Нэш-Вильямса и его применения
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2025. Т.22. №2. С.1278-1284. DOI: 10.33048/semi.2025.22.077

Даты:

Поступила в редакцию:

6 дек. 2024 г.

Идентификаторы БД: Нет идентификаторов

Цитирование в БД: Пока нет цитирований

Альметрики: