Max-Bisections on Strong Product of Paths and Cycles

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 that go across the two parts. In this paper, motivated by a well-known result of Edwards about Max-Cut, we study maximum bisections of graphs. Let [Formula: see text]. For each [Formula: see text], we show that [Formula: see text] admits a bisection of size larger than Edwards’ bound. We also study the maximum bisection of graphs that seem closely related to the strong product of two paths.