This chapter focuses on the bounds of the bisection width of cubic graphs. Let G be a finite graph. The bisection width bw(G) of graph G is the minimal number of edges between vertex sets A and Ā of almost equal size, that is AĀ = V(G) and | | A | − | Ā | ≤ 1. Some lemmas and their proofs are also discussed in the chapter. Buser showed the existence of such cubic graphs G that i(G) ≥ 1/128. Clark and Entringer obtained in their latest work the upper bound bw(G) ≤ (n + 138) for cubic graphs.
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics