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