zbMATH — the first resource for mathematics

Bipartite graphs decomposable into closed trails. (English) Zbl 1223.05225
Summary: Let \(G= K_{a,b}\), where \(a\), \(b\) are even or \(G= K_{a,a}- M_{2a}\), where \(a\geq 1\) is an odd integer and \(M_{2a}\) is a perfect matching in \(K_{a,a}\). It has been shown ([S. Cichacz and M. Horňák, Czech. Math. J. 59, No. 1, 129–144 (2009; Zbl 1224.05402); M. Horňák and M. Woźniak, Czech. Math. J. 53, No. 1, 127–134 (2003)]) that \(G\) is arbitrarily decomposable into closed trails. Billington asked if the graph \(K_{r,s}- F\), where \(s\), \(r\) are odd and \(F\) is a (smallest possible) spanning subgraph of odd degree, is arbitrarily decomposable into closed trails ([E. J. Billington, Matematiche 59, No. 1–2, 53–72 (2004; Zbl 1195.05058)]).
In this article we answer the question in the affirmative.
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles