Full subgraphs
Full subgraphs
复制标题
完整子图
DOI：
10.1002/jgt.22221
复制
发表时间：
2018
影响因子：
0.9
通讯作者：
Verstraëte, Jacques
中科院分区：
文献类型：
--
作者：
Falgas-Ravry, Victor;Markström, Klas;Verstraëte, Jacques
设是一个顶点数为n的图。根据Erdés，Schuuczak和Spencer，G的m-顶点子图H被称为fullifH至少有最小度。记G的最大满子图的阶。如果是一个非负整数，定义Erdés，Schiuczak和Spencer证明，对于，在这篇文章中，我们证明了以下下界：对于，此外，我们表明，这是紧到一个乘法常数因子的无限manypnear的元素。相反，我们证明了对于任何n-顶点图G，eitherGor包含顶点上的完全子图。最后，我们讨论了随机图和伪随机图的完全子图，以及几个开放问题。
Let be a graph of densityponnvertices. Following Erdős, Łuczak, and Spencer, anm‐vertex subgraphHofGis calledfullifHhas minimum degree at least . Let denote the order of a largest full subgraph ofG. If is a nonnegative integer, define Erdős, Łuczak, and Spencer proved that for , In this article, we prove the following lower bound: for , Furthermore, we show that this is tight up to a multiplicative constant factor for infinitely manypnear the elements of . In contrast, we show that for anyn‐vertex graphG, eitherGor contains a full subgraph on vertices. Finally, we discuss full subgraphs of random and pseudo‐random graphs, and several open problems.
登录
查看更多内容
关于三色超图
影响因子：
0.8
作者：
J. Beck
通讯作者：
J. Beck
DOI：
10.1016/0012-365x(89)90093-9
发表时间：
1989
期刊：
Discret. Math.
影响因子：
--
作者：
Julie Haviland;A. Thomason
通讯作者：
A. Thomason
DOI：
--
发表时间：
1992
期刊：
影响因子：
--
作者：
J. Spencer;P. Erdös;T. Luczak
通讯作者：
T. Luczak
差异和大而密集的单色子集
影响因子：
0.3
作者：
Ross J. Kang;V. Patel;Guus Regts
通讯作者：
Guus Regts
埃尔米特矩阵和图：奇异值和差异
影响因子：
0.8
作者：
B. Bollobás;V. Nikiforov
通讯作者：
V. Nikiforov