Max-Bisections in the Network Graphs

Source abstract

A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differs by at most 1, and its size is the number of edges which go across the two parts. In this paper, motivated by a well-known result of Edwards about Max-Cut, we study the maximum bisections on two types of the network graphs. For each $i\ge 1$, let $PN(i)$ be an $n$-vertex pyramid network graph with $m$ edges and let $CQ_i$ be an $n$-vertex crossed hypercube graph with $m$ edges. We show that $PN(i)$ admits a bisection of size at least $m/2+n-\sqrt{3n+1}+1$ and this bound is tight. We also prove that $CQ_i$ admits a bisection of size at least $m/2+(i-1)n/4$ and this bound is tight. Both of the lower bounds are larger than the Edwards' bound.