|Abstract of Paper|
Edge-bisection of Chordal Rings
by Lali Barriere and J. Fabrega
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.