کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777606 | 1632967 | 2017 | 23 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Robust Hamiltonicity of random directed graphs
ترجمه فارسی عنوان
همیلتونیت قوی از گراف های تصادفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A natural way to generalize such results to arbitrary graphs (digraphs) is using the notion of local resilience. The local resilience of a graph (digraph) G with respect to a property P is the maximum number r such that G has the property P even if we allow an adversary to remove an r-fraction of (in- and out-going) edges touching each vertex. The theorems of Dirac and Ghouila-Houri state that the local resilience of the complete graph and digraph with respect to Hamiltonicity is 1/2. Recently, this statements have been generalized to random settings. Lee and Sudakov (2012) proved that the local resilience of a random graph with edge probability p=Ï(logâ¡n/n) with respect to Hamiltonicity is 1/2±o(1). For random directed graphs, Hefetz, Steger and Sudakov (2014) proved an analogue statement, but only for edge probability p=Ï(logâ¡n/n). In this paper we significantly improve their result to p=Ï(log8â¡n/n), which is optimal up to the polylogarithmic factor.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 126, September 2017, Pages 1-23
Journal: Journal of Combinatorial Theory, Series B - Volume 126, September 2017, Pages 1-23
نویسندگان
Asaf Ferber, Rajko Nenadov, Andreas Noever, Ueli Peter, Nemanja Å koriÄ,