Decomposing toroidal graphs into circuits and edges
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 147-159 |
Journal / Publication | Discrete Applied Mathematics |
Volume | 148 |
Issue number | 2 |
Publication status | Published - 15 May 2005 |
Link(s)
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.
In: Discrete Applied Mathematics, Vol. 148, No. 2, 15.05.2005, p. 147-159.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review