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

Abstrakt

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.

Klíčová slova

• cubic graphs
• edge-cuts
• large girth