Mathematics – Combinatorics
Scientific paper
2011-04-03
Mathematics
Combinatorics
17 pages, accepted by Discrete Mathematics
Scientific paper
10.1016/j.disc.2011.03.020
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 $uv$ 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)\geq \sqrt{2}-1$, with equality if and only if $G$ is a path with at least three vertices.
Lu Linyuan
Yang Yiting
No associations
LandOfFree
The Randic index and the diameter of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Randic index and the diameter of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Randic index and the diameter of graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-316917