2024/01/18 by Stefanie Gerke, Gregory Gutin, Gerke, Stefanie +5 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2401.10074
openalex publication_date 2024/01/18 · openalex created_date 2024/01/20 · openalex updated_date 2026/07/28
A bisection in a graph is a cut in which the number of vertices in the two parts differ by at most 1. In this paper, we give lower bounds for the maximum weight of bisections of edge-weighted graphs with bounded maximum degree. Our results improve a bound of Lee, Loh, and Sudakov (J. Comb. Th. Ser. B 103 (2013)) for (unweighted) maximum bisections in graphs whose maximum degree is either even or equals 3, and for almost all graphs. We show that a tight lower bound for maximum size of bisections in 3-regular graphs obtained by Bollobás and Scott (J. Graph Th. 46 (2004)) can be extended to weighted subcubic graphs. We also consider edge-weighted triangle-free subcubic graphs and show that a much better lower bound (than for edge-weighted subcubic graphs) holds for such graphs especially if we exclude K1,3. We pose three conjectures.