Asymptotic Bounds on the Integrity of Graphs and Separator Theorems for Graphs
D. Benko, Claus Ernst, Dominic Lanphier · SIAM Journal on Discrete Mathematics · 2009
In this paper we study the integrity of certain graph families. These include planar graphs, graphs with a given genus, graphs on the d-dimensional integer lattice $\mathbb{Z}^d$, and graphs that have no $K_h$-minor. We give upper bounds for the integrity in terms of the order n of the graph. We also give lower bounds for box-graphs in $\mathbb{Z}^d$. As a consequence, the integrity of planar graphs is on the order of $n^{2/3}$, where $2/3$ is the best possible exponent.