کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949518 | 1440193 | 2017 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Almost all regular graphs are normal
ترجمه فارسی عنوان
تقریبا تمام نمودارهای منظم طبیعی هستند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
گرایش گراف نرمال، آنتروپی گراف نمودار منظم تصادفی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In 1999, De Simone and Körner conjectured that every graph without induced C5,C7,C¯7 contains a clique cover C and a stable set cover I such that every clique in C and every stable set in I have a vertex in common. This conjecture has roots in information theory and became known as the Normal Graph Conjecture. Here we prove that all C4-free graphs of bounded maximum degree and sufficiently large odd girth (linear in the maximum degree) are normal. This is used to prove that for every fixed d, random d-regular graphs are a.a.s. normal.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 230, 30 October 2017, Pages 51-55
Journal: Discrete Applied Mathematics - Volume 230, 30 October 2017, Pages 51-55
نویسندگان
Seyed Saeed Changiz Rezaei, Seyyed Aliasghar Hosseini, Bojan Mohar,