کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9512675 | 1342538 | 2005 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
4-regular claw-free IM-extendable graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A graph G is induced matching extendable (shortly, IM-extendable), if every induced matching of G is included in a perfect matching of G. A graph G is claw-free, if G does not contain any induced subgraph isomorphic to K1,3. The kth power of a graph G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. In this paper, the 4-regular claw-free IM-extendable graphs are characterized. It is shown that the only 4-regular claw-free connected IM-extendable graphs are C62, C82 and Tr, r⩾2, where Tr is the graph with 4r vertices ui,vi,xi,yi, 1⩽i⩽r, such that for each i with 1⩽i⩽r, {ui,vi,xi,yi} is a clique of Tr and xiui+1,yivi+1âE(Tr)(modr). We also show that a 4-regular strongly IM-extendable graph must be claw-free. As a consequence, the only 4-regular strongly IM-extendable graphs are K4ÃK2, C62 and C82.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 294, Issue 3, 6 May 2005, Pages 303-309
Journal: Discrete Mathematics - Volume 294, Issue 3, 6 May 2005, Pages 303-309
نویسندگان
Wang Qin, Yuan Jinjiang,