Minors in Expanding Graphs
Minors in Expanding Graphs
复制标题
扩展图中的未成年人
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
Michael Krivelevich;B. Sudakov
摘要。我们提出了一个与图形无关的统一框架，该框架与给定图中的大型未成年人有关，然后将开发的框架应用于几个极端问题。 （a）每个$$ k_ {s，s^prime} $$ - 带有平均度r（$$ 2 leq s leq s^prime $$常数）的免费图G g，其中一个未成年人，平均度$$ cr^{1 + {frac {1} {2（s-1）}}} $$，对于某些常数$$ c = c（s，s^prime）> 0 $$; r（k≥2是常数）包含一个未成年人，平均度$$ cr^{frac {k+1} {2}}} $$，对于某些常数c = c（k）> 0。随机，伪随机和扩展图的次要密度上的边界。
Abstract.We propose a unifying framework for studying extremal problems related to graph minors. This framework relates the existence of a large minor in a given graph to its expansion properties. We then apply the developed framework to several extremal problems and prove in particular that: (a) Every $$K_{s,s^prime}$$-free graph G with average degree r ($$2 leq s leq s^prime$$ are constants) contains a minor with average degree $$cr^{1+ {frac{1}{2(s-1)}}}$$, for some constant $$c = c(s, s^prime) > 0$$; (b) Every C2k-free graph G with average degree r (k ≥ 2 is a constant) contains a minor with average degree $$cr^{frac{k+1}{2}}$$, for some constant c = c(k) > 0. We also derive explicit lower bounds on the minor density in random, pseudo-random and expanding graphs.
影响因子：
1
作者：
Fountoulakis N
通讯作者：
Fountoulakis N