Isoperimetric numbers and bisection widths of double coverings of a complete graph

Abstract

The aim of this paper is to study the isoperimetric numbers of double coverings of a complete graph. It turns out that these numbers are very closely related to the bisection widths of the double coverings and the degrees of unbalance of the signed graphs which derive the double coverings. For example, the bisection width of a double covering of a complete graph K-m is equal to m times its isoperimetric number. We determine which numbers can be the isoperimetric numbers of double coverings of a complete graph.