ASYMPTOTIC BOUNDS ON THE INTEGRITY OF GRAPHS AND SEPARATOR THEOREMS FOR GRAPHS

摘要

In this paper we study the integrity of certain graph families. These include planar graphs, graphs with a given genus, graphs on the ri-dimensional integer lattice 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 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.