Abstract of Paper

Edge-bisection of Chordal Rings
by Lali Barriere and J. Fabrega

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. The
reason why we are interested in these graphs is two folded. On one hand,
they can be considered as the simplest Cayley graphs on a non-abelian group
(the dihedral group is metabelian). On the other hand, the natural plane
tessellation used to represent and manipulate these graphs allows
generalizations to other types of tessellations including abelian Cayley
graphs. We have improved previous bounds on the edge-bisection of chordal
rings. 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 is those
with the maximum number of vertices for a given diameter.