On the conjecture of Delorme, Favaron and Rautenbach about the Randic index
On the conjecture of Delorme, Favaron and Rautenbach about the Randic index
复制标题
DOI：
10.1016/j.ejor.2006.02.035
复制
发表时间：
2007-07
期刊：
影响因子：
--
通讯作者：
Ljiljana Pavlović
中科院分区：
文献类型：
--
作者：
Ljiljana Pavlović
设G(k，n)是无多条边或圈的连通图的集合，G有n个顶点，最小度为k.图G的ć指标χ=χ(G)定义为：χ=∑(Uv)(δuδv)-1/2，其中δu是顶点u的度，求和延伸到G的所有边(Uv).本文证明了Delorme，Favaron和Rautenbach关于当k=n2时Randić指标达到最小值的图的猜想.我们证明了极图必有n−k个k度顶点和k个n−1度顶点。
Let G(k,n) be the set of connected graphs without multiple edges or loops which have n vertices and the minimum degree of vertices is k. The Randić index χ=χ(G) of a graph G is defined by: χ=∑(uv)(δuδv)-1/2, where δuis the degree of vertex u and the summation extends over all edges (uv) of G. In this paper we prove the conjecture of Delorme, Favaron and Rautenbach about the graphs for which the Randić index attains its minimum value when k=n2. We show that the extremal graphs must have n−k vertices of degree k and k vertices of degree n−1.