کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333870 | 689653 | 2016 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Proper connection number of random graphs
ترجمه فارسی عنوان
تعداد اتصالات مناسب نمودارهای تصادفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شماره اتصال مناسب، رنگ صحیح مسیر، نمودار تصادفی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A path in an edge-colored graph is called a proper path if no two adjacent edges of the path are colored with the same color. For a connected graph G, the proper connection number pc(G) of G is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of G is connected by at least one proper path in G. In this paper, we show that almost all graphs have the proper connection number 2. More precisely, let G(n,p) denote the Erdös-Rényi random graph model, in which each of the (n2) pairs of vertices appears as an edge with probability p independent from other pairs. We prove that for sufficiently large n, pc(G(n,p))â¤2 if pâ¥logâ¡n+α(n)n, where α(n)ââ.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 609, Part 2, 4 January 2016, Pages 336-343
Journal: Theoretical Computer Science - Volume 609, Part 2, 4 January 2016, Pages 336-343
نویسندگان
Ran Gu, Xueliang Li, Zhongmei Qin,