Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs

Abstract

We improve existing lower bounds on the size of maximum edge cuts in cubic graphs with no short cycles. Our method is based on a probabilistic approach.

Keywords

• cubic graphs
• edge-cuts
• large girth