Menu
The harmonic index \(H(G)\) of a graph \(G\) is defined as the sum of the weights \(\frac{2}{d_{u}+ d_{v}}\) of all edges \(uv\) of \(G\), where \(d_{u}\) denotes the degree of a vertex \(u\). Delorme et al. [1] (2002) put forward a conjecture concerning the minimum Randić index among all connected graphs with \(n\) vertices and the minimum degree at least \(k\). Motivated by this paper, a conjecture related to the minimum harmonic index among all connected graphs with \(n\) vertices and the minimum degree at least \(k\) was posed in [2]. In this work, we show that the conjecture is true for a connected graph on $n$ vertices with \(k\) vertices of degree \(n-1\), and it is also true for a \(k\)-tree. Moreover, we give a shorter proof of Liu’s result [3].
Let \(G=(V,E)\) denote a simple connected graph. The Randić (or connectivity) index \(R(G)\) is defined in [4] by \(R(G)=\sum\limits_{uv\in E(G)}\frac{1}{\sqrt{d_ud_v}}\), where \(d_{u}\) denotes the degree of a vertex \(u\) in \(G\), and \(\frac{1}{\sqrt{d_ud_v}}\) is called the weight of the edge \(uv\) in the Randić index. This index was extensively studied in mathematical chemistry. The harmonic index \(H(G)\) is defined in [5] as \(H(G)=\sum\limits_{uv\in E(G)}\frac{2}{d_{u}+ d_{v}}\), where \(\frac{2}{d_{u}+ d_{v}}\) is called the weight of the edge \(uv\) in the harmonic index. In [6], the authors considered the relation between the harmonic index and the eigenvalues of graphs. In [7], the author presented the minimum and maximum values of harmonic index on simple connected graphs and trees, and characterized the corresponding extremal graphs. In [8], the authors gave a best possible lower bound for the harmonic index of a graph (a triangle-free graph, respectively) with minimum degree at least two and characterized the corresponding extremal graphs.
In 1968, Harary and Palmer [9] defined an \(n\)-plex as an \(n\)-dimensional complex in which every \(k\)-simplex with \(k<n\) is contained in an \(n\)-complex. For convenience, 0-simplexes, 1-simplexes, and 2-simplexes are called points, lines, and cells respectively. The two-dimensional trees, also called 2-trees can now be defined inductively. The 2-plex with three points is a 2-tree, and a 2-tree with \(p+1\) points is obtained from a 2-tree with \(p\) points by adjoining a new point \(w\) adjoint to each of two adjacent points \(u\) and \(v\) together with the accompanying cell \(\{u,v,w\}\). The definition of a \(k\)-tree for \(k>2\) is similar. In graph theory, a \(k\)-tree is a chordal graph all of whose maximal cliques are the same size \(k+1\) and all of whose minimal clique separators are also all the same size \(k\). Every \(k\)-tree may be formed by starting with a \((k+1)\)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex has exactly \(k\) neighbors that form a clique (see [10]). The minimum degree of a \(k\)-tree is \(k\). And a 1-tree is a tree in traditional graph theory.
Delorme et al. (2002) [1] put forward a conjecture concerning the minimum Randić index among all connected graphs with \(n\) vertices and the minimum degree at least \(k\).
Conjecture 1. ([1]) For any connected graph with \(n\) vertices and the minimum degree at least \(k\), \(R(G)\geq\frac{k(n-k)}{\sqrt{k(n-1)}}+\frac{k(k-1)}{2(n-1)}\), the equality holds if and only if \(G\cong K^{*}_{k, n-k}\), which arises from complete bipartite graph \(K_{n, n-k}\) by joining each pair of vertices in the partite set with \(k\) vertices by a new edge.
Using linear programming, Pavlovic [11] proved that Conjecture 1 holds when \(k=\frac{n-1}{2}\) or \(k=\frac{n}{2}\) (see also [12] for further results proved by quadratic programming). Liu [3] showed that Conjecture 1 is true given the graph contains \(k\) vertices of degree \(n-1\) and it is true among \(k\)-trees. But, Aouchiche and Hansen [13] refuted the conjecture by using the AutoGraphiX 2 system, and modified the conjecture. Motivated by this paper, a conjecture related to the minimum harmonic index among all connected graphs with \(n\) vertices and the minimum degree at least \(k\) was also posed in [2].
Conjecture 2. ([2]) Let \(G\) be a graph with \(n \geq 4\) vertices and the minimum degree \(\delta(G) \geq k\), where \(1 \leq k \leq \left\lfloor \frac{n}{2}\right\rfloor +1\). Then \(H(G) \geq H(K_{k, n-k}^{*})\) with equality if and only if \(G = K_{k, n-k}^{*}\).
Deng et al posed the following conjecture in [14].
Conjecture 3. ([14]) For any simple and connected graph \(G\) with \(n\) vertices and the minimum degree at least \(k\), \(H(G)\geq \frac{k(k-1)}{2(n-1)}+ \frac{2k(n-k)}{n+k-1}\) with equality if and only if \(G\cong K^{*}_{k, n-k}\).
A counter-example to Conjecture 1 is the graph obtained from \(K_7\) by deleting two independent edges.
Motivated by the paper [3] and [15], here, we will show that Conjecture 2 and Conjecture 3 is true for a connected graph containing \(k\) vertices of degree \(n-1\) with \(n\) vertices and the minimum degree at least \(k\), and it is also true for a \(k\)-tree. For additional results on this index, see [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34].
In the following, we first determine the minimum value of \(H(G)\) of a graph on \(n\) vertices with \(k\) vertices of degree \(n-1\), and show that Conjecture 1 and Conjecture 1 is true for a graph containing \(k\) vertices of degree \(n-1\).
Lemma 1. ([8]) If \(e\) is an edge with maximum weight in \(G\), then \(H(G-e)<H(G)\).
Theorem 1. Let \(G\) be a graph with \(n\) vertices and \(k\) vertices of degree \(n-1\). Then \[\begin{aligned} H(G)\geq \frac{k(k-1)}{2(n-1)}+ \frac{2k(n-k)}{n+k-1} \nonumber \end{aligned}\] with equality if and only if \(G\cong K_{k,n-k}^{*}\).
. It is easy to compute that \(H(K_{k,n-k}^{*})=\frac{k(k-1)}{2(n-1)}+ \frac{2k(n-k)}{n+k-1}\).
Let \(G\) be the graph with the minimum harmonic index among all graphs with \(n\) vertices and \(k\) vertices of degree \(n-1\). Suppose \(X\) denotes the set of \(k\) vertices of degree \(n-1\) in \(G\) and \(Y=V(G)-X\). Then the subgraph induced by \(X\) is a clique. If \(G\not\cong K_{k,n-k}^{*}\), then the subgraph induced by \(Y\) is not an empty graph. Since the degree of every vertex in \(Y\) is at most \(n-2\), an edge \(e\) with the maximum weight belongs to the subgraph induced by \(Y\). By Lemma 1, \(H(G-e)<H(G)\) and \(G-e\) is also a graph with \(n\) vertices and \(k\) vertices of degree \(n-1\), a contradiction. So, the subgraph induced by \(Y\) is an empty graph, and \(G\cong K_{k,n-k}^{*}\). \(\Box\)
Theorem 1 shows that Conjecture 2 and Conjecture 3 is true for a connected graph on \(n\) vertices with \(k\) vertices of degree \(n-1\), certainly, the minimum degree at least \(k\).
Using linear programming, Liu [3] showed that Conjecture 1 is true for a connected graph with \(n\) vertices and \(k\) vertices of degree \(n-1\). In the following, we give a shorter proof of this result.
Lemma 2. ([35]) Let \(e\) be an edge with maximum weight in a graph \(G\). Then \(R(G-e)<R(G)\).
Theorem 2. ([3]) Let \(G\) be a graph with \(n\) vertices and \(k\) vertices of degree \(n-1\). Then \[\begin{aligned} R(G)\geq \frac{k(n-k)}{\sqrt{k(n-1)}}+ \frac{k(k-1)}{2(n-1)} \nonumber \end{aligned}\] with equality if and only if \(G\cong K_{k,n-k}^{*}\).
. It is easy to compute that \(R(K_{k,n-k}^{*})= \frac{k(n-k)}{\sqrt{k(n-1)}}+ \frac{k(k-1)}{2(n-1)}\).
Let \(G\) be the graph with the minimum Randić index among all graphs with \(n\) vertices and \(k\) vertices of degree \(n-1\). \(X\) denotes the set of \(k\) vertices of degree \(n-1\) in \(G\) and \(Y=V(G)-X\). Then the subgraph induced by \(X\) is a clique. If \(G\not\cong K_{k,n-k}^{*}\), then the subgraph induced by \(Y\) is not an empty graph. Since the degree of every vertex in \(Y\) is at most \(n-2\), an edge \(e\) with the maximum weight belongs to the subgraph induced by \(Y\). By Lemma 1, \(R(G-e)<R(G)\) and \(G-e\) is also a graph with \(n\) vertices and \(k\) vertices of degree \(n-1\), a contradiction. So, the subgraph induced by \(Y\) is an empty graph, and \(G\cong K_{k,n-k}^{*}\). \(\Box\)
Now, we consider the harmonic index of a \(k\)-tree. The following lemma can be proved easily and it will be used in the back.
Lemma 3. If \(x\geq k\), then \(\frac{1}{x+d}-\frac{1}{x+d-1}\geq\frac{1}{k+d}-\frac{1}{k+d-1}\) and \(\frac{1}{(x+d)^2}-\frac{1}{(x+d-2)^2}\geq\frac{1}{(k+d)^2}-\frac{1}{(k+d-2)^2}\).
Lemma 4. Let \(G\) be a \(k\)-tree with \(n\) (\(n\geq k+1\)) vertices. \(v_{0}\) is a vertex of degree \(k\) in \(G\) and its neighbors \(N(v_{0})=\left\{v_{1}, v_{2}, \cdots, v_{k}\right\}\) and \(d_{v_{i}}=d_{i}\) \((i= 1, 2, \dots, k)\), then \[\begin{aligned} H(G)-H(G-v_{0})\geq f(d_{1}, d_{2}, \cdots, d_{k}). \nonumber \end{aligned}\] where \(f(d_{1}, d_{2}, \cdots, d_{k})=\sum\limits_{i=1}^{k}\left(\frac{2(d_{i}-k+1)}{k+d_{i}}- \frac{2(d_{i}-k)}{k+d_{i}-1}\right)+\sum\limits_{1\leq i<j\leq k}\left(\frac{2}{d_{i}+d_{j}}-\frac{2}{d_{i}+d_{j}-2}\right)\). Moreover, \(f(d_{1}, d_{2}, \cdots, d_{k}) \geq f(n-1, n-1, \cdots, n-1)\), and \(H(G)-H(G-v_{0})=f(n-1, n-1, \cdots, n-1)\) if and only if \(G=K_{k,n-k}^{*}\).
. By the definition of a \(k\)-tree, the subgraph induced by \(N(v_0)\) is a clique. We have \[\begin{aligned} & H(G)-H(G-v_{0})=\sum_{i=1}^{k}\frac{2}{k+d_{i}}+\sum_{1\leq i<j \leq k}\left(\frac{2}{d_{i}+d_{j}}- \frac{2}{d_{i}+d_{j}-2}\right)\nonumber \\ &+\sum_{i=1}^{k}\sum_{x\in N(v_i)-\{v_0,v_1,\cdots,v_k\}}\left(\frac{2}{d_x+d_{i}}-\frac{2}{d_x+d_{i}-1}\right)\nonumber \\ &\geq\sum_{i=1}^{k}\frac{2}{k+d_{i}}+ \sum_{1\leq i<j \leq k}\left(\frac{2}{d_{i}+d_{j}}-\frac{2}{d_{i}+d_{j}-2}\right) \nonumber \\ &+\sum_{i=1}^{k}\left(\frac{2(d_{i}-k)}{k+d_{i}}-\frac{2(d_{i}-k)}{k+d_{i}-1}\right) \mbox{ (by Lemma \ref{l-2} and $d_x\geq k$)}\nonumber \\ &=\sum_{i=1}^{k}\left(\frac{2(d_{i}-k+1)}{k+d_{i}}-\frac{2(d_{i}-k)}{k+d_{i}-1}\right) +\sum_{1 \leq i<j \leq k}\left(\frac{2}{d_{i}+d_{j}}-\frac{2}{d_{i}+d_{j}-2}\right) \nonumber \\ &=f(d_{1}, d_{2}, \cdots, d_{k}). \nonumber \end{aligned}\]
Note that the partial derivatives \[\begin{aligned} & \frac{\partial f(d_{1},d_{2},\cdots, d_{k})}{\partial d_{i}} \nonumber \\ =&\frac{2k-1}{(k+d_{i})^{2}}-\frac{(2k-1)}{(k+d_{i}-1)^{2}}-\sum_{1 \leq j \leq k, j\neq i}\frac{1}{(d_{i}+d_{j})^{2}}+\sum_{1 \leq j \leq k, j\neq i}\frac{1}{(d_{i}+d_{j}-2)^{2}} \nonumber \\ \leq & \frac{2k-1}{(k+d_{i})^{2}}-\frac{(2k-1)}{(k+d_{i}-1)^{2}}-\frac{k-1}{(d_{i}+k)^{2}} +\frac{k-1}{(d_{i}+ k-2)^{2}} \mbox{ (by Lemma \ref{l-2} and $d_j\geq k$)} \nonumber \\ < & 0 \nonumber \end{aligned}\] for \(i=1,2,\cdots,k\), and \(k\leq d_{i}\leq n-1\) (\(i=1,2,\cdots,k\)), we have \(f(d_1, d_2, \cdots ,d_k)\geq f(n-1, n-1, \cdots, n-1)\) if and only if equalities hold throughout the above inequalities, i.e., \(d_{i}=n-1\) and \(d_x=k\) for all \(x\in N(v_i)-\{v_0,v_1,\cdots,v_k\}\) (\(i=1,2,\cdots,k\)), and \(G\) is \(K_{k,n-k}^{*}\). \(\Box\)
Theorem 3. Let \(G\) be a \(k\)-tree with \(n\) \((n \geq k+1)\) vertices. Then \(H(G) \geq \frac{k(k-1)}{2(n-1)}+ \frac{2k(n-k)}{n+k-1}\) with equality if and only if \(G\cong K_{k,n-k}^{*}\).
. We prove the result by induction on \(n\). The result is true for \(n=k+1\), since a \(k\)-tree \(G\) with \(k+1\) is a complete graph \(K_{k+1}\) and \(H(G)=\frac{k+1}{2}\). Assume that the result is true for any \(k\)-tree with \(n=n_{0}\) \((n_{0}\geq k+1)\) vertices. Let \(G\) be a \(k\)-tree with \(n_{0}+1\) vertices. From the structure of a \(k\)-tree, there is a vertex \(v_0\) of degree \(k\) such that \(G-v_0\) is a \(k\)-tree with \(n_0\) vertices. Denote \(N(v_{0})=\left\{v_{1}, v_{2}, \cdots, v_{k}\right\}\) and \(d_{v_{i}}=d_{i}\) \((i=1, 2, \cdots, k)\). By Lemma 3 and the inductive assumption, we have \[\begin{aligned} H(G)&\geq H(G-v_{0})+f(n-1,n-1,\cdots,n-1) \nonumber \\ &\geq H(K^*_{k,n-1-k})+f(n-1,n-1,\cdots,n-1) \nonumber \\ &=\frac{k(k-1)}{2(n-2)}+\frac{2k(n-1-k)}{n+k-2}+ \sum_{i=1}^{k}\left(\frac{2(n-k)}{k+n-1}-\frac{2(n-1-k)}{k+n-2}\right)\nonumber \\ &+\sum_{1\leq i<j\leq k}\left(\frac{2}{2n-2}-\frac{2}{2n-4}\right)\nonumber \\ & = \frac{k(k-1)}{2(n-1)}+ \frac{2k(n-k)}{n+k-1} \nonumber \end{aligned}\] with equality if and only if \(G=K_{k,n-k}^{*}\). \(\Box\)
Theorem 1 shows that Conjecture 2 and Conjecture 3 is true for \(k\)-trees. Note that a \(1\)-tree is a tree, we get the following result immediately.
Corollary 1. ([7]) Let \(T\) be a tree with \(n\) vertices. Then \(H(T)\geq \frac{2(n-1)}{n}\) with equality if and only if \(T\cong S_{n}\).
The authors declare no conflict of interests.