Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Edge-Bisection of Chordal Rings

Lali BarriéreContact Information and Josep FábregaContact Information

(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.

Contact Information Lali Barriére
Email: lali@mat.upc.es

Contact Information Josep Fábrega
Email: matjfc@mat.upc.es
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.108 • Server: mpweb19
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)