Connectivity, graph minors, and subgraph multiplicity
Connectivity, graph minors, and subgraph multiplicity
复制标题
连接性、次要图和子图多重性
DOI：
10.1002/jgt.3190170314
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
D. Eppstein
中科院分区：
文献类型：
--
作者：
D. Eppstein
作者：Eppstein，大卫|翻译后摘要：这是众所周知的，任何平面图包含最多O（n）完全子图。我们扩展到一个精确的特征：G出现O（n）次作为任何平面图的子图，当且仅当G是三连通的。更一般地说，G作为无K_B，c图的子图B/= c出现O（n）次当且仅当G是c-连通的，G作为无K_a图的子图出现O（n）次当且仅当G是（a - 1）-连通的.我们的结果使用一个简单的拉姆齐理论引理，可能是独立的利益。
Author(s): Eppstein, David | Abstract: It is well known that any planar graph contains at most O(n) complete subgraphs. We extend this to an exact characterization: G occurs O(n) times as a subgraph of any planar graph, if and only if G is three-connected. Even more generally, G occurs O(n) times as a subgraph of the K_b,c free graphs, b g/= c, if and only if G is c-connected; G occurs O(n) times as a subgraph of the K_a-free graphs if and only if G is (a - 1)-connected. Our results use a simple Ramsey-theoretic lemma that may be of independent interest.