Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911761788043264 |
|---|---|
| author | Gerke, Stefanie Gutin, Gregory Yeo, Anders Zhou, Yacong |
| author_facet | Gerke, Stefanie Gutin, Gregory Yeo, Anders Zhou, Yacong |
| contents | 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 $K_{1,3}$. We pose three conjectures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_10074 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees Gerke, Stefanie Gutin, Gregory Yeo, Anders Zhou, Yacong Combinatorics Discrete Mathematics 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 $K_{1,3}$. We pose three conjectures. |
| title | Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2401.10074 |