The Randić index and the diameter of graphs

Abstract: The {it Randi'c index}

R (G)

of a graph

G

is defined as the sum of 1/sqrt{d_ud_v} over all edges

u v

of

G

, where

d_{u}

and

d_{v}

are the degrees of vertices

u

and

v,

respectively. Let

D (G)

be the diameter of

G

when

G

is connected. Aouchiche-Hansen-Zheng conjectured that among all connected graphs

G

on

n

vertices the path

P_{n}

achieves the minimum values for both

R (G) / D (G)

and

R (G) - D (G)

. We prove this conjecture completely. In fact, we prove a stronger theorem: If

G

is a connected graph, then

R (G) - (1 / 2) D (G) g e q s q r t 2 - 1

, with equality if and only if

G

is a path with at least three vertices.

Recommendations

Cites work

Cited in

(13)

Describes a project that uses

Uses Software

This page was built for publication: The Randić index and the diameter of graphs