کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9655105 | 684025 | 2005 | 29 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A novel giant-subgraph phase-transition in sparse random k-partite graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A novel giant-subgraph phase-transition in sparse random k-partite graphs A novel giant-subgraph phase-transition in sparse random k-partite graphs](/preview/png/9655105.png)
چکیده انگلیسی
We describe a novel subgraph of k-partite graphs suddenly appearing at an average degree c=4.91⦠(for k=3) in random graphs with a built-in k-partition. These magic subgraphs consist of directed edges and comprise a constant fraction of the nodes, as soon as they appear. The phenomenon is similar to the Sudden Emergence of a Giant k-Core [B. Pittel, J. Spence, N. Wormald, Sudden emergence of a giant k-core in a random graph, J. Combin. Theory Ser. B 67 (1996) 111-151] and can be easily demonstrated in simulations. Thus generated magic subgraphs appear to be 'almost' uniquely colourable. On the theoretical side, we give an indication how central parts of our novel proof for the aforementioned k-core phenomenon [U. Voll, Threshold phenomena in branching trees and random graphs, Ph.D. Thesis, Lehrstuhl für Effiziente Algorithmen, Technische Universität München, Germany, 2001.] can be modified in order to prove the sudden appearance of a subgraph which is (obviously) closely related to the empirically observed magic subgraph, appearing at the right critical average degree and having the right size compared to simulations. We conclude with discussing a number of open questions related to the magic subgraph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 153, Issues 1â3, 1 December 2005, Pages 153-181
Journal: Discrete Applied Mathematics - Volume 153, Issues 1â3, 1 December 2005, Pages 153-181
نویسندگان
Ulrich Voll,