کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649627 | 1342462 | 2009 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Variable neighborhood search for extremal graphs. 23. On the Randić index and the chromatic number
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let G=(V,E)G=(V,E) be a simple graph with vertex degrees d1,d2,…,dnd1,d2,…,dn. The Randić index R(G)R(G) is equal to the sum over all edges (i,j)∈E(i,j)∈E of weights 1/didj. We prove several conjectures, obtained by the system AutoGraphiX, relating R(G)R(G) and the chromatic number χ(G)χ(G). The main result is χ(G)≤2R(G)χ(G)≤2R(G). To prove it, we also show that if v∈Vv∈V is a vertex of minimum degree δδ of GG, G−vG−v the graph obtained from GG by deleting vv and all incident edges, and ΔΔ the maximum degree of GG, then R(G)−R(G−v)≥12δ/Δ.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 13, 6 July 2009, Pages 4228–4234
Journal: Discrete Mathematics - Volume 309, Issue 13, 6 July 2009, Pages 4228–4234
نویسندگان
Pierre Hansen, Damir Vukicević,