Proof of the first part of the conjecture of Aouchiche and Hansen about the Randi? index
Let G(k,n) G ( k , n ) be the set of connected simple n n -vertex graphs with minimum vertex degree k k . The Randi? index R(G) R ( G ) of a graph G G is defined by: R ( G ) = ? u v ? E ( G ) 1 d ( u ) d ( v ) , where d(u) d ( u ) is the degree of vertex u u and the summation extends over all edges uv u v of G G . In this paper we prove for k ? n 2 the conjecture of Aouchiche and Hansen about the graphs in G(k,n) G ( k , n ) for which the Randi? index attains its minimum value. We show that the extremal graphs are complete split graphs K k , n ? k ? , which have only two degrees, i.e. degree k k and degree n?1 n ? 1 , and the number of vertices of degree k k is n?k n ? k , while the number of vertices of degree n?1 n ? 1 is k k . At the end we generalize our results to graphs with prescribed maximum degree q q .
conjecture randi? index minimum degree combinatorial optimization quadratic programming