Decomposing toroidal graphs into circuits and edges

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

3 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)147-159
Journal / PublicationDiscrete Applied Mathematics
Volume148
Issue number2
Publication statusPublished - 15 May 2005

Abstract

Erdos et al. (Canad. J. Math. 18 (1966) 106-112) conjecture that there exists a constant dce such that every simple graph on n vertices can be decomposed into at most dcen circuits and edges. We consider toroidal graphs, where the graphs can be embedded on the torus, and give a polynomial time algorithm to decompose the edge set of an even toroidal graph on n vertices into at most (n+3)/2 circuits. As a corollary, we get a polynomial time algorithm to decompose the edge set of a toroidal graph (not necessarily even) on n vertices into at most 3(n-1)/2 circuits and edges. This settles the conjecture for toroidal graphs. © 2005 Elsevier B.V. All rights reserved.

Research Area(s)

  • Circuit, Decomposition, Torus

Citation Format(s)

Decomposing toroidal graphs into circuits and edges. / Xu, Baogang; Wang, Lusheng.
In: Discrete Applied Mathematics, Vol. 148, No. 2, 15.05.2005, p. 147-159.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review