On Bounds of the Bisection Width of Cubic Graphs

A. V. Kostochka, L. S. Mel'nikov

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)151-154
Number of pages4
JournalAnnals of Discrete Mathematics
Volume51
Issue numberC
DOIs
StatePublished - Jan 1 1992
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On Bounds of the Bisection Width of Cubic Graphs'. Together they form a unique fingerprint.

Cite this