کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871136 | 1440179 | 2018 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the representation number of a crown graph
ترجمه فارسی عنوان
در شماره نمایندگی یک گراف تاج
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار قابل بیان کلمه نمودار تاج نمودار حزب کوکتل، تعداد نمایندگی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A crown graph (also known as a cocktail party graph) Hn,n is a graph obtained from the complete bipartite graph Kn,n by removing a perfect matching. In this paper, we show that for nâ¥5, Hn,n's representation number is ânâ2â. This result not only provides a complete solution to the open Problem 7.4.2 in Kitaev and Lozin (2015), but also gives a negative answer to the question raised in Problem 7.2.7 in Kitaev and Lozin (2015) on 3-word-representability of bipartite graphs. As a byproduct, we obtain a new example of a graph class with a high representation number.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 244, 31 July 2018, Pages 89-93
Journal: Discrete Applied Mathematics - Volume 244, 31 July 2018, Pages 89-93
نویسندگان
Marc Glen, Sergey Kitaev, Artem Pyatkin,