کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647438 | 1632424 | 2014 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On maximum matchings in almost regular graphs
ترجمه فارسی عنوان
در حداکثر سازگاری در نمودارهای تقریبا منظم
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
گراف دو طرفه، نمودار منظم حداکثر تطبیق
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
In 2010, Mkrtchyan, Petrosyan, and Vardanyan proved that every graph G with 2â¤Î´(G)â¤Î(G)â¤3 contains a maximum matching M such that no two vertices uncovered by M share a neighbor, where Î(G) and δ(G) denote the maximum and minimum degrees of vertices in G, respectively. In the same paper they suggested the following conjecture: every graph G with Î(G)âδ(G)â¤1 contains a maximum matching M such that no two vertices uncovered by M share a neighbor. Recently, Picouleau disproved this conjecture by constructing a bipartite counterexample G with Î(G)=5 and δ(G)=4. In this note, we show that the conjecture is false for graphs G with Î(G)âδ(G)=1 and Î(G)â¥4, and for r-regular graphs when râ¥7.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 318, 6 March 2014, Pages 58-61
Journal: Discrete Mathematics - Volume 318, 6 March 2014, Pages 58-61
نویسندگان
Petros A. Petrosyan,