Bipartite graphs decomposable into closed trails

Sylwia Cichacz, Dalibar Froncek

Research output: Contribution to journalArticlepeer-review


Let G = Ka,b, where a, b are even or G = Ka,a -M 2a,, where a > 1 is an odd integer and M2a is a perfect matching in Ka,a. It has been shown ([3,4]) that G is arbitrarily decomposable into closed trails. Billington asked if the graph Kr,s, -F, where s,r are odd and F is a (smallest possible) spanning subgraph of odd degree, is arbitrarily decomposable into closed trails ([2]). In this article we answer the question in the affirmative.

Original languageEnglish (US)
Pages (from-to)207-216
Number of pages10
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
StatePublished - Aug 1 2010


Dive into the research topics of 'Bipartite graphs decomposable into closed trails'. Together they form a unique fingerprint.

Cite this