Новое доказательство теоремы Нэш-Вильямса и его применения Full article
| Journal |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||
|---|---|---|---|
| Output data | Year: 2025, Volume: 22, Number: 2, Pages: 1278-1284 Pages count : 7 DOI: 10.33048/semi.2025.22.077 | ||
| Tags | graph, multigraph, tree, forest, decomposition, arboricity, Nash-Williams' Theorem, cover index | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0017 |
Abstract:
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.
Cite:
Глебов А.Н.
Новое доказательство теоремы Нэш-Вильямса и его применения
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2025. Т.22. №2. С.1278-1284. DOI: 10.33048/semi.2025.22.077
Новое доказательство теоремы Нэш-Вильямса и его применения
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2025. Т.22. №2. С.1278-1284. DOI: 10.33048/semi.2025.22.077
Dates:
| Submitted: | Dec 6, 2024 |
Identifiers:
No identifiers
Citing:
Пока нет цитирований