Edge-Bisection of Chordal Rings
Lali Barriére6
and Josep Fábrega6 
| (6) |
Dept. de Matemática Aplicada i Telemática, Universitat Politécnica de Catalunya, Barcelona |
Abstract
An edge-bisector of a graph is a set of edges whose removing separates the graph into two subgraphs of same order, within
one. The edge-bisection of a graph is the cardinality of the smallest edge-bisector. The main purpose of this paper is to
estimate the quality of general bounds on the edge-bisection of Cayley graphs. For this purpose we have focused on chordal
rings of degree 3. These graphs are Cayley graphs on the dihedral group and can be considered as the simplest Cayley graphs
on a non-abelian group (the dihedral group is metabelian). Moreover, the natural plane tessellation used to represent and
manipulate these graphs can be generalized to other types of tessellations including abelian Cayley graphs. We have improved
previous bounds on the edge-bisection of chordal rings and we have shown that, for any fixed chord, our upper bound on the
edge-bisection of chordal rings is optimal up to an O(log n) factor. Finally, we have given tight bounds for optimal chordal rings, that are those with the maximum number of vertices
for a given diameter.
Work supported by the Spanish Research Council (Comisión Interministerial de Ciencia y Tecnología, CICYT) under project TIC-97-0963.
References secured to subscribers.