TY - JOUR
T1 - Complete solution for unicyclic graphs with minimum general Randić index
AU - Li, Xueliang
AU - Wang, Lusheng
AU - Zhang, Yuting
PY - 2006
Y1 - 2006
N2 - The general Randić index of a (molecular) graph G is defined by Rα(G) = Σuv(d(u)d(v))α, where d(u) denotes the degree of a vertex u in G, uv runs over the edge set of G and α is an arbitrary real number. Wu and Zhang studied unicyclic graphs with minimum general Randić index. For α ≥ -1 they got the unique minimum unicyclic graph by distinguishing or into intervals α ≥ 0 and -1 ≤ α <0. But, unfortunately, for α <-1 they could not completely solve this minimum problem. At the end they figured out two classes G and H of possible minimum unicyclic graphs. In this paper, we completely solve this problem by showing that for α <-1 and n ≥ 5, the unique unicyclic graph with minimum general Randić index is either S n
+ or t[n-3/2],[n-3/2]k, where Sn
+ denotes the unicyclic graph obtained from the star Sn on n vertices by joining its two vertices of degree 1, whereas t[n-3/2],[n-3/2]* denotes the unicyclic graph that has a triangle as its unique cycle and the vertices not on the cycle are leaves that are adjacent to two vertices of the triangle such that the numbers of leaf vertices on the two branches are almost equal. Furthermore, we observe that as α approaches to -1, if t[n-3/2],[n-3/2]k has the minimum value then n must be considerably large, that is to say, when α is near -1, it is almost sure that Sn
+ is the unique minimum unicyclic graph, whereas when α is at a distance from -1, it is almost sure that t[n-3/2],[n-3/2]k is the unique minimum unicyclic graph. In particular, for α ≤ -2, Sn
+ for 5 ≤ n ≤ 41 and t[n-3/2],[n-3/2]k for n ≥ 42, respectively, is the unique unicyclic graph with minimum general Randić index.
AB - The general Randić index of a (molecular) graph G is defined by Rα(G) = Σuv(d(u)d(v))α, where d(u) denotes the degree of a vertex u in G, uv runs over the edge set of G and α is an arbitrary real number. Wu and Zhang studied unicyclic graphs with minimum general Randić index. For α ≥ -1 they got the unique minimum unicyclic graph by distinguishing or into intervals α ≥ 0 and -1 ≤ α <0. But, unfortunately, for α <-1 they could not completely solve this minimum problem. At the end they figured out two classes G and H of possible minimum unicyclic graphs. In this paper, we completely solve this problem by showing that for α <-1 and n ≥ 5, the unique unicyclic graph with minimum general Randić index is either S n
+ or t[n-3/2],[n-3/2]k, where Sn
+ denotes the unicyclic graph obtained from the star Sn on n vertices by joining its two vertices of degree 1, whereas t[n-3/2],[n-3/2]* denotes the unicyclic graph that has a triangle as its unique cycle and the vertices not on the cycle are leaves that are adjacent to two vertices of the triangle such that the numbers of leaf vertices on the two branches are almost equal. Furthermore, we observe that as α approaches to -1, if t[n-3/2],[n-3/2]k has the minimum value then n must be considerably large, that is to say, when α is near -1, it is almost sure that Sn
+ is the unique minimum unicyclic graph, whereas when α is at a distance from -1, it is almost sure that t[n-3/2],[n-3/2]k is the unique minimum unicyclic graph. In particular, for α ≤ -2, Sn
+ for 5 ≤ n ≤ 41 and t[n-3/2],[n-3/2]k for n ≥ 42, respectively, is the unique unicyclic graph with minimum general Randić index.
KW - General Randić index
KW - Star
KW - Triangle with two balanced leaf branches
KW - Unicyclic graph
UR - http://www.scopus.com/inward/record.url?scp=33845461916&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-33845461916&origin=recordpage
M3 - 21_Publication in refereed journal
VL - 55
SP - 391
EP - 408
JO - Match
JF - Match
SN - 0340-6253
IS - 2
ER -