کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436297 | 689986 | 2014 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Incidence coloring on hypercubes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let χi(G)χi(G) and Δ(G)Δ(G) denote the incidence coloring number and the maximum degree of a graph G , respectively. An easy observation shows that χi(G)⩾Δ(G)+1χi(G)⩾Δ(G)+1. In this paper, we consider incidence coloring number on hypercubes QnQn. Based on the technique of Hamming codes, we present algorithms to obtain upper bounds of χi(Qn)χi(Qn) for n in certain forms of integers. Let p,qp,q be positive integers. We show that (1) χi(Qn)=n+1χi(Qn)=n+1 if n=2p−1n=2p−1 for p⩾1p⩾1; (2) χi(Qn)=n+2χi(Qn)=n+2 if the following conditions hold: (i) n=2p−2n=2p−2 for p⩾2p⩾2; (ii) n=2p+2q−2n=2p+2q−2 for p,q⩾1p,q⩾1; (iii) n=2p+2q−3n=2p+2q−3 for p,q⩾2p,q⩾2; and (3) χi(Qn)⩾n+2χi(Qn)⩾n+2 otherwise.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 557, 6 November 2014, Pages 59–65
Journal: Theoretical Computer Science - Volume 557, 6 November 2014, Pages 59–65
نویسندگان
Kung-Jui Pai, Jou-Ming Chang, Jinn-Shyong Yang, Ro-Yu Wu,