RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2017 Volume 14, Pages 1324–1329 (Mi semr873)

Discrete mathematics and mathematical cybernetics

An enhancement of Nash–Williams' Theorem on edge arboricity of graphs

A. N. Glebov

Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia

Abstract: The well-known Nash–Williams' Theorem states that for any positive integer $k$ a multigraph $G=(V,E)$ admits an edge decomposition into $k$ forests iff every subset $X\subseteq V$ induces a subgraph $G[X]$ with at most $k(|X|-1)$ edges. In this paper we prove that, under certain conditions, this decomposition can be chosen so that each forest contains no isolated vertices. More precisely, we prove that if either $G$ is a bipartite multigraph with minimum degree $\delta(G)\ge k$, or $k=2$ and $\delta(G)\ge 3$, then $G$ can be decomposed into $k$ forests without isolated vertices.

Keywords: graph, multigraph, tree, forest, decomposition, arboricity, cover index.

UDC: 519.174.5

MSC: 05C70

Received November 7, 2017, published December 6, 2017

DOI: 10.17377/semi.2017.14.113



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025