Decomposing toroidal graphs into circuits and edges

Erdős et al. (Canad. J. Math. 18 (1966) 106–112) conjecture that there exists a constant d ce such that every simple graph on n vertices can be decomposed into at most d ce n circuits and edges. We consider toroidal graphs, where the graphs can be embedded on the torus, and give a polynomial time al...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2005-05, Vol.148 (2), p.147-159
Main Authors: Xu, Baogang, Wang, Lusheng
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Circuit
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Decomposition
Exact sciences and technology
Graph theory
Information retrieval. Graph
Mathematics
Sciences and techniques of general use
Theoretical computing
Torus
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Erdős et al. (Canad. J. Math. 18 (1966) 106–112) conjecture that there exists a constant d ce such that every simple graph on n vertices can be decomposed into at most d ce n 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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2004.10.006