Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 151-154 |
Number of pages | 4 |
Journal | Annals of Discrete Mathematics |
Volume | 51 |
Issue number | C |
DOIs | |
State | Published - Jan 1 1992 |
Externally published | Yes |
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics