Spanning Trees of Dense Directed Graphs
Spanning Trees of Dense Directed Graphs
复制标题
稠密有向图的生成树
DOI：
10.1016/j.entcs.2019.08.056
复制
发表时间：
2019
影响因子：
--
通讯作者：
Mycroft R
中科院分区：
文献类型：
--
作者：
Mycroft R
在九十年代，Komlós， Sárközy和szemerdi证实了Bollobás的一个猜想，表明对于每一个正的α， Δ和足够大的，每一个最小度（1/2 +α）n的图包含每一个有序树和最大度最多Δ。我们获得了他们结果的有向图模拟，其中最小度被最小半度取代（这是所有顶点上所有进出度的最小值），最大度被底层图的最大度取代（即，我们通过忽略边的方向获得的图的最大度）。事实上，我们证明了一个更强的结果，它说明了一个有序树存在于每一个有序且最小半次（1/2 +α）n的有向图中的充分条件。该结果表明，对于所有正实数α和足够大的有向图，每一个阶为最小半度（1/2+α）n的有向图几乎包含每一个阶为生成有向树。
In the nineties, Komlós, Sárközy and Szemerédi confirmed a conjecture of Bollobás, showing that for every positiveα, Δ and sufficiently largen, every graph with minimum degree (1/2 +α)ncontains every tree of ordernand maximum degree at most Δ. We obtain a directed graph analogue of their result, where the minimum degree is replaced by minimum semidegree (which is the minimum of all in- and out-degrees over all vertices) and the maximum degree is replaced by the maximum degree of the underlying graph (i.e., the maximum degree of the graph we obtain by ignoring the orientation of edges).In fact, we prove a stronger result, which states a sufficient condition for a tree of ordernto be contained in every directed graph of ordernand minimum semidegree (1/2 +α)n. This result implies that for all positive realαand sufficiently largenevery directed graph of ordernwith minimum semidegree (1/2+α)ncontains almost every spanning oriented treeTof ordern.