Random directed graphs are robustly Hamiltonian
Random directed graphs are robustly Hamiltonian
复制标题
随机有向图具有稳健的哈密顿量
DOI：
10.1002/rsa.20631
复制
发表时间：
2016
影响因子：
1
通讯作者：
Hefetz D
中科院分区：
文献类型：
--
作者：
Hefetz D
Ghouila-Houri在1960年提出的一个经典定理证明了n个顶点的有向图中至少包含一个有向汉密尔顿圈，其中n个顶点的出度和入度都最小.本文将这一定理推广到随机有向图，即任意有序对（u，v）成为概率p独立于其他所有有序对的弧的有向图。受随机图弹性性质研究的启发，我们证明了，如果，则a.a.s.的每一个具有最小出度和入度的子有向图至少包含一个有向汉密尔顿圈.常数1/2是渐近最佳可能的。我们的结果也加强了经典的结果存在的有向汉密尔顿圈的随机有向图。© 2016 Wiley Periodicals，Inc.随机结构算法，49，345-362，2016
A classical theorem of Ghouila‐Houri from 1960 asserts that every directed graph onnvertices with minimum out‐degree and in‐degree at least contains a directed Hamilton cycle. In this paper we extend this theorem to a random directed graph , that is, a directed graph in which every ordered pair (u, v) becomes an arc with probabilitypindependently of all other pairs. Motivated by the study of resilience of properties of random graphs, we prove that if , then a.a.s. every subdigraph of with minimum out‐degree and in‐degree at least contains a directed Hamilton cycle. The constant 1/2 is asymptotically best possible. Our result also strengthens classical results about the existence of directed Hamilton cycles in random directed graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 345–362, 2016
登录
查看更多内容
在密集图和有向图中计算和打包汉密尔顿循环
DOI：
10.1016/j.jctb.2016.06.001
发表时间：
2012
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Asaf Ferber;Michael Krivelevich;B. Sudakov
通讯作者：
B. Sudakov
关于随机图中的哈密尔顿循环数
DOI：
10.1002/jgt.3190130608
发表时间：
1989
期刊：
J. Graph Theory
影响因子：
--
作者：
C. Cooper;A. Frieze
通讯作者：
A. Frieze
高最小次数图中哈密顿循环的最优堆积
DOI：
10.1017/s0963548312000569
发表时间：
2012
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
KÜHN D
通讯作者：
KÜHN D
关于稀疏随机图中的哈密顿循环数
DOI：
10.1137/120884316
发表时间：
2013
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
R. Glebov;M. Krivelevich
通讯作者：
M. Krivelevich
随机有向图的鲁棒哈密顿性
DOI：
--
发表时间：
2014
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Asaf Ferber;R. Nenadov;A. Noever;Ueli Peter;N. Skoric
通讯作者：
N. Skoric