Asymptotic Bounds on the Integrity of Graphs and Separator Theorems for Graphs
Asymptotic Bounds on the Integrity of Graphs and Separator Theorems for Graphs
复制标题
图完整性的渐近界和图的分隔定理
DOI：
10.1137/070692698
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
D. Lanphier
中科院分区：
文献类型：
--
作者：
D. Benko;C. Ernst;D. Lanphier
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.
