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

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
نویسندگان
, ,