کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418883 | 681723 | 2014 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bipartite finite Toeplitz graphs
ترجمه فارسی عنوان
گراف دوتلیتیت محدود دو است؟
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let n,a1,…,akn,a1,…,ak be distinct positive integers. A finite Toeplitz graph Tn(a1,…,ak)=(V,E)Tn(a1,…,ak)=(V,E) is a graph where V={v0,…,vn−1}V={v0,…,vn−1} and E={(vi,vj):|i−j|∈{a1,…,ak}}E={(vi,vj):|i−j|∈{a1,…,ak}}. In this paper, we characterize bipartite finite Toeplitz graphs with k≤3k≤3. In most cases, the characterization takes O(loga3)O(loga3) arithmetic steps; in the remaining cases, it takes O(a1)O(a1). A consequence of the proposed results is the complete characterization of the chromatic number of finite Toeplitz graphs with k≤3k≤3. In addition, we characterize some classes of infinite bipartite Toeplitz graphs with k≥4k≥4.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 165, 11 March 2014, Pages 233–244
Journal: Discrete Applied Mathematics - Volume 165, 11 March 2014, Pages 233–244
نویسندگان
Sara Nicoloso, Ugo Pietropaoli,