On a conjecture of the harmonic index with given minimum degree of graphs and short proof of Liu’s result on Randić index

Deng, Hanyuan; Balachandran, S.; Balachandar,  S.

doi:10.61091/ars157-03

Abstract

References

Ars Combinatoria

Volume 157
Pages: 39-44

Research article

On a conjecture of the harmonic index with given minimum degree of graphs and short proof of Liu’s result on Randić index

^¹, ^²,³, ^⁴

¹College of Mathematics and Statistics, Hunan Normal University, Changsha,Hunan 410081, P. R. China.

²Department of Mathematics and Applied Mathematics, University of the Free State, Bloemfontein, South Africa.

³Department of Mathematics, School of Arts, Sciences and Humanities, SASTRA Deemed University, Thanjavur, India.

⁴Department of Mathematics, School of Arts, Sciences and Humanities, SASTRA Deemed University, Thanjavur, India.

Received: 22/04/2018
Accepted: 25/01/2019
Published: 29/11/2023

Copyright Link
License

Abstract

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 $u v$ 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].

Keywords: Randić index, Harmonic index, Minimum degree,

k

-tree.

1. Introduction

Let $G = (V, E)$ denote a simple connected graph. The Randić (or connectivity) index $R (G)$ is defined in [4] by $R (G) = \sum_{u v \in E (G)} \frac{1}{\sqrt{d_{u} d_{v}}}$ , where $d_{u}$ denotes the degree of a vertex $u$ in $G$ , and $\frac{1}{\sqrt{d_{u} d_{v}}}$ is called the weight of the edge $u v$ 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_{u v \in E (G)} \frac{2}{d_{u} + d_{v}}$ , where $\frac{2}{d_{u} + d_{v}}$ is called the weight of the edge $u v$ 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 ≅ 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 $δ (G) \geq k$ , where $1 \leq k \leq ⌊ \frac{n}{2} ⌋ + 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{2 k (n - k)}{n + k - 1}$ with equality if and only if $G ≅ 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].

2. Main Results

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{2 k (n - k)}{n + k - 1} \end{aligned}$ with equality if and only if $G ≅ K_{k, n - k}^{*}$ .

. It is easy to compute that $H (K_{k, n - k}^{*}) = \frac{k (k - 1)}{2 (n - 1)} + \frac{2 k (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 ≇ 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 ≅ K_{k, n - k}^{*}$ .

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)} \end{aligned}$ with equality if and only if $G ≅ 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 ≇ 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 ≅ K_{k, n - k}^{*}$ .

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}) = {v_{1}, v_{2}, \dots, v_{k}}$ 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}, \dots, d_{k}) . \end{aligned}$ where $f (d_{1}, d_{2}, \dots, d_{k}) = \sum_{i = 1}^{k} (\frac{2 (d_{i} - k + 1)}{k + d_{i}} - \frac{2 (d_{i} - k)}{k + d_{i} - 1}) + \sum_{1 \leq i < j \leq k} (\frac{2}{d_{i} + d_{j}} - \frac{2}{d_{i} + d_{j} - 2})$ . Moreover, $f (d_{1}, d_{2}, \dots, d_{k}) \geq f (n - 1, n - 1, \dots, n - 1)$ , and $H (G) - H (G - v_{0}) = f (n - 1, n - 1, \dots, 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} (\frac{2}{d_{i} + d_{j}} - \frac{2}{d_{i} + d_{j} - 2}) \\ + \sum_{i = 1}^{k} \sum_{x \in N (v_{i}) - {v_{0}, v_{1}, \dots, v_{k}}} (\frac{2}{d_{x} + d_{i}} - \frac{2}{d_{x} + d_{i} - 1}) \\ \geq \sum_{i = 1}^{k} \frac{2}{k + d_{i}} + \sum_{1 \leq i < j \leq k} (\frac{2}{d_{i} + d_{j}} - \frac{2}{d_{i} + d_{j} - 2}) \\ + \sum_{i = 1}^{k} (\frac{2 (d_{i} - k)}{k + d_{i}} - \frac{2 (d_{i} - k)}{k + d_{i} - 1}) (by Lemma ??? and d_{x} \geq k) \\ = \sum_{i = 1}^{k} (\frac{2 (d_{i} - k + 1)}{k + d_{i}} - \frac{2 (d_{i} - k)}{k + d_{i} - 1}) + \sum_{1 \leq i < j \leq k} (\frac{2}{d_{i} + d_{j}} - \frac{2}{d_{i} + d_{j} - 2}) \\ = f (d_{1}, d_{2}, \dots, d_{k}) . \end{aligned}$

Note that the partial derivatives $\begin{aligned} \frac{\partial f (d_{1}, d_{2}, \dots, d_{k})}{\partial d_{i}} \\ = & \frac{2 k - 1}{(k + d_{i})^{2}} - \frac{(2 k - 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}} \\ \leq & \frac{2 k - 1}{(k + d_{i})^{2}} - \frac{(2 k - 1)}{(k + d_{i} - 1)^{2}} - \frac{k - 1}{(d_{i} + k)^{2}} + \frac{k - 1}{(d_{i} + k - 2)^{2}} (by Lemma ??? and d_{j} \geq k) \\ < & 0 \end{aligned}$ for $i = 1, 2, \dots, k$ , and $k \leq d_{i} \leq n - 1$ ( $i = 1, 2, \dots, k$ ), we have $f (d_{1}, d_{2}, \dots, d_{k}) \geq f (n - 1, n - 1, \dots, 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}, \dots, v_{k}}$ ( $i = 1, 2, \dots, k$ ), and $G$ is $K_{k, n - k}^{*}$ .

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{2 k (n - k)}{n + k - 1}$ with equality if and only if $G ≅ 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}) = {v_{1}, v_{2}, \dots, v_{k}}$ and $d_{v_{i}} = d_{i}$ $(i = 1, 2, \dots, k)$ . By Lemma 3 and the inductive assumption, we have $\begin{aligned} H (G) & \geq H (G - v_{0}) + f (n - 1, n - 1, \dots, n - 1) \\ \geq H (K_{k, n - 1 - k}^{*}) + f (n - 1, n - 1, \dots, n - 1) \\ = \frac{k (k - 1)}{2 (n - 2)} + \frac{2 k (n - 1 - k)}{n + k - 2} + \sum_{i = 1}^{k} (\frac{2 (n - k)}{k + n - 1} - \frac{2 (n - 1 - k)}{k + n - 2}) \\ + \sum_{1 \leq i < j \leq k} (\frac{2}{2 n - 2} - \frac{2}{2 n - 4}) \\ = \frac{k (k - 1)}{2 (n - 1)} + \frac{2 k (n - k)}{n + k - 1} \end{aligned}$ with equality if and only if $G = K_{k, n - k}^{*}$ .

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 ≅ S_{n}$ .

Conflict of Interest

The authors declare no conflict of interests.

References:

Delorme, C., Favaron, O. and Rautenbach, D., 2002. On the Randic index. Discrete Mathematics, 257(1), pp.29-38.[Google Scholor]
Cheng, M. and Wang, L., 2016. A lower bound for the harmonic index of a graph with minimum degree at least three. Filomat, 30(8), pp.2249-2260.[Google Scholor]
Liu, J., 2013. On a conjecture of the Randić index and the minimum degree of graphs. Discrete Applied Mathematics, 161(16-17),pp.2544-2548.[Google Scholor]
Randić, M., 1975. Characterization of molecular branching. Journal of the American Chemical Society, 97(23), pp.6609-6615.[Google Scholor]
Fajtlowicz, S., 1987. On conjectures of Graffiti-II. Congressus numerantium, 60, pp.187-197.[Google Scholor]
Favaron, O., Mahéo, M. and Saclé, J.F., 1993. Some eigenvalue properties in graphs (conjectures of Graffiti-II). Discrete mathematics, 111(1-3), pp.197-220.[Google Scholor]
Zhong, L., 2012. The harmonic index for graphs. Applied mathematics letters, 25(3), pp.561-566.[Google Scholor]
Wu, R., Tang, Z. and Deng, H., 2013. A lower bound for the harmonic index of a graph with minimum degree at least two. Filomat,27(1), pp.51-55.[Google Scholor]
Harary, F. and Palmer, E.M., 1968. On acyclic simplicial complexes. Mathematika, 15(1), pp.115-122.
Patil, H.P., 1986. On the structure of k-trees. Journal of Combinatorics, Information and System Sciences, 11(2-4), pp.57-64.[Google Scholor]
Pavlović, L., 2007. On the conjecture of Delorme, Favaron and Rautenbach about the Randić. European journal of operational research, 180(1), pp.369-377.[Google Scholor]
Pavlović, L. and Divnić, T., 2004. The new approach to the Randić index. Research report, Faculty of Science, University of Kragujevac, Serbia and Monte Negro.[Google Scholor]
Aouchiche, M. and Hansen, P., 2007. On a conjecture about the Randić index. Discrete Mathematics, 307(2), pp.262-265.[Google Scholor]
Deng, H., Balachandran, S. and Raja Balachandar, S., 2020. The minimum value of the harmonic index for a graph with the minimum degree two. Asian-European Journal of Mathematics, 13(03), p.2050054.[Google Scholor]
Pavlović, L., 2003. Graphs with extremal Randic index when the minimum degree of vertices is two. Kragujevac Journal of Mathematics, 25(25), pp.55-63.[Google Scholor]
Deng, H., Balachandran, S., Ayyaswamy, S.K. and Venkatakrishnan, Y.B., 2013. On the harmonic index and the chromatic number of a graph. Discrete Applied Mathematics, 161(16-17), pp.2740-2744.[Google Scholor]
Deng, H., Balachandran, S. and Ayyaswamy, S.K., 2014. On two conjectures of Randic index and the largest signless Laplacian eigenvalue of graphs. Journal of Mathematical Analysis and Applications, 411(1), pp.196-200.[Google Scholor]
Deng, H., Tang, Z. and Zhang, J., 2015. On a conjecture of Randić index and graph radius. Filomat, 29(6), pp.1369-1375.[Google Scholor]
Deng, H., Balachandran, S., Venkatakrishnan, Y.B. and Balachandar, S.R., 2016. Trees with smaller harmonic indices. Filomat, 30(11), pp.2955-2963.[Google Scholor]
Deng, H., Balachandran, S., Ayyaswamy, S.K. and Venkatakrishnan, Y.B., 2017. On harmonic indices of trees, unicyclic graphs and bicyclic graphs. Ars Combinatoria, 130, pp.239-248.[Google Scholor]
Deng, H., Balachandran, S. and Ayyaswamy, S.K., 2018. A Note on Harmonic Index and Coloring Number of a Graph. Ars Combinatoria, 137, pp.257-262.[Google Scholor]
Deng, H., Balachandran, S. and Elumalai, S., 2019. Some tight bounds for the harmonic index and the variation of the Randic index of graphs.Discrete Mathematics, 342(7), pp.2060-2065.[Google Scholor]
Li, J. and Shiu, W.C., 2014. The harmonic index of a graph. The Rocky Mountain Journal of Mathematics, 44(5), pp.1607-1620.[Google Scholor]
Liu, J., 2015. Harmonie index of dense graphs. Ars Combinatoria, 120, pp.293-304.[Google Scholor]
Liu, J. and Zhang, Q., 2012. Remarks on harmonic index of graphs. Utilitas Mathematica, 88, pp.281-285.[Google Scholor]
Jian, B.L., Li, J. and Chee, S.W., 2014. The harmonic index of unicyclic graphs with given matching number. Kragujevac Journal of Mathematics, 38(1), pp.173-183.[Google Scholor]
Ma, Y., Shi, Y., Gutman, I. and Furtula, B., 2018. From the connectivity index to various Randic-type descriptors. MATCH Communications in Mathematical and in Computer Chemistry, 80(1), pp.85-106.[Google Scholor]
Rasi, R., Sheikholeslami, S.M. and Gutman, I., 2017. On harmonic index of trees. MATCH Communications in Mathematical and in Computer Chemistry, 78, pp.405-416.[Google Scholor]
Rasi, R. and Sheikholeslami, S.M., 2017. The harmonic index of unicyclic graphs. Asian-European Journal of Mathematics, 10(03), p.1750039.[Google Scholor]
Wu, R., Tang, Z. and Deng, H., 2013. On the harmonic index and the girth of a graph. Utilitas Mathematica, 91, pp.65-69.[Google Scholor]
Zhong, L., 2012. The harmonic index on unicyclic graphs. Ars Combinatoria, 104, pp.261-269.[Google Scholor]
Zhong, L. and Xu, K., 2013. The harmonic index for bicyclic graphs. Utilitas Mathematica, 90, pp.23-32.[Google Scholor]
Zhong, L. and Cui, Q., 2015. The harmonic index for unicyclic graphs with given girth. Filomat, 29(4), pp.673-686.[Google Scholor]
Zhu, Y. and Chang, R., 2014. On the harmonic index of bicyclic conjugated molecular graphs. Filomat, 28(2), pp.421-428.
Bollobás, B. and Erdoś, P., 1998. Graphs of extremal weights. Ars combinatoria, 50, pp.225-233[Google Scholor]

[1] Delorme, C., Favaron, O. and Rautenbach, D., 2002. On the Randic index. Discrete Mathematics, 257(1), pp.29-38.[Google Scholor]

[2] Cheng, M. and Wang, L., 2016. A lower bound for the harmonic index of a graph with minimum degree at least three. Filomat, 30(8), pp.2249-2260.[Google Scholor]

[3] Liu, J., 2013. On a conjecture of the Randić index and the minimum degree of graphs. Discrete Applied Mathematics, 161(16-17),pp.2544-2548.[Google Scholor]

[4] Randić, M., 1975. Characterization of molecular branching. Journal of the American Chemical Society, 97(23), pp.6609-6615.[Google Scholor]

[5] Fajtlowicz, S., 1987. On conjectures of Graffiti-II. Congressus numerantium, 60, pp.187-197.[Google Scholor]

[6] Favaron, O., Mahéo, M. and Saclé, J.F., 1993. Some eigenvalue properties in graphs (conjectures of Graffiti-II). Discrete mathematics, 111(1-3), pp.197-220.[Google Scholor]

[7] Zhong, L., 2012. The harmonic index for graphs. Applied mathematics letters, 25(3), pp.561-566.[Google Scholor]

[8] Wu, R., Tang, Z. and Deng, H., 2013. A lower bound for the harmonic index of a graph with minimum degree at least two. Filomat,27(1), pp.51-55.[Google Scholor]

[9] Harary, F. and Palmer, E.M., 1968. On acyclic simplicial complexes. Mathematika, 15(1), pp.115-122.

[10] Patil, H.P., 1986. On the structure of k-trees. Journal of Combinatorics, Information and System Sciences, 11(2-4), pp.57-64.[Google Scholor]

[11] Pavlović, L., 2007. On the conjecture of Delorme, Favaron and Rautenbach about the Randić. European journal of operational research, 180(1), pp.369-377.[Google Scholor]

[12] Pavlović, L. and Divnić, T., 2004. The new approach to the Randić index. Research report, Faculty of Science, University of Kragujevac, Serbia and Monte Negro.[Google Scholor]

[13] Aouchiche, M. and Hansen, P., 2007. On a conjecture about the Randić index. Discrete Mathematics, 307(2), pp.262-265.[Google Scholor]

[14] Deng, H., Balachandran, S. and Raja Balachandar, S., 2020. The minimum value of the harmonic index for a graph with the minimum degree two. Asian-European Journal of Mathematics, 13(03), p.2050054.[Google Scholor]

[15] Pavlović, L., 2003. Graphs with extremal Randic index when the minimum degree of vertices is two. Kragujevac Journal of Mathematics, 25(25), pp.55-63.[Google Scholor]

[16] Deng, H., Balachandran, S., Ayyaswamy, S.K. and Venkatakrishnan, Y.B., 2013. On the harmonic index and the chromatic number of a graph. Discrete Applied Mathematics, 161(16-17), pp.2740-2744.[Google Scholor]

[17] Deng, H., Balachandran, S. and Ayyaswamy, S.K., 2014. On two conjectures of Randic index and the largest signless Laplacian eigenvalue of graphs. Journal of Mathematical Analysis and Applications, 411(1), pp.196-200.[Google Scholor]

[18] Deng, H., Tang, Z. and Zhang, J., 2015. On a conjecture of Randić index and graph radius. Filomat, 29(6), pp.1369-1375.[Google Scholor]

[19] Deng, H., Balachandran, S., Venkatakrishnan, Y.B. and Balachandar, S.R., 2016. Trees with smaller harmonic indices. Filomat, 30(11), pp.2955-2963.[Google Scholor]

[20] Deng, H., Balachandran, S., Ayyaswamy, S.K. and Venkatakrishnan, Y.B., 2017. On harmonic indices of trees, unicyclic graphs and bicyclic graphs. Ars Combinatoria, 130, pp.239-248.[Google Scholor]

[21] Deng, H., Balachandran, S. and Ayyaswamy, S.K., 2018. A Note on Harmonic Index and Coloring Number of a Graph. Ars Combinatoria, 137, pp.257-262.[Google Scholor]

[22] Deng, H., Balachandran, S. and Elumalai, S., 2019. Some tight bounds for the harmonic index and the variation of the Randic index of graphs.Discrete Mathematics, 342(7), pp.2060-2065.[Google Scholor]

[23] Li, J. and Shiu, W.C., 2014. The harmonic index of a graph. The Rocky Mountain Journal of Mathematics, 44(5), pp.1607-1620.[Google Scholor]

[24] Liu, J., 2015. Harmonie index of dense graphs. Ars Combinatoria, 120, pp.293-304.[Google Scholor]

[25] Liu, J. and Zhang, Q., 2012. Remarks on harmonic index of graphs. Utilitas Mathematica, 88, pp.281-285.[Google Scholor]

[26] Jian, B.L., Li, J. and Chee, S.W., 2014. The harmonic index of unicyclic graphs with given matching number. Kragujevac Journal of Mathematics, 38(1), pp.173-183.[Google Scholor]

[27] Ma, Y., Shi, Y., Gutman, I. and Furtula, B., 2018. From the connectivity index to various Randic-type descriptors. MATCH Communications in Mathematical and in Computer Chemistry, 80(1), pp.85-106.[Google Scholor]

[28] Rasi, R., Sheikholeslami, S.M. and Gutman, I., 2017. On harmonic index of trees. MATCH Communications in Mathematical and in Computer Chemistry, 78, pp.405-416.[Google Scholor]

[29] Rasi, R. and Sheikholeslami, S.M., 2017. The harmonic index of unicyclic graphs. Asian-European Journal of Mathematics, 10(03), p.1750039.[Google Scholor]

[30] Wu, R., Tang, Z. and Deng, H., 2013. On the harmonic index and the girth of a graph. Utilitas Mathematica, 91, pp.65-69.[Google Scholor]

[31] Zhong, L., 2012. The harmonic index on unicyclic graphs. Ars Combinatoria, 104, pp.261-269.[Google Scholor]

[32] Zhong, L. and Xu, K., 2013. The harmonic index for bicyclic graphs. Utilitas Mathematica, 90, pp.23-32.[Google Scholor]

[33] Zhong, L. and Cui, Q., 2015. The harmonic index for unicyclic graphs with given girth. Filomat, 29(4), pp.673-686.[Google Scholor]

[34] Zhu, Y. and Chang, R., 2014. On the harmonic index of bicyclic conjugated molecular graphs. Filomat, 28(2), pp.421-428.

[35] Bollobás, B. and Erdoś, P., 1998. Graphs of extremal weights. Ars combinatoria, 50, pp.225-233[Google Scholor]

Contents

Ars Combinatoria

On a conjecture of the harmonic index with given minimum degree of graphs and short proof of Liu’s result on Randić index

Abstract

1. Introduction

2. Main Results

Conflict of Interest

References:

Information

Guidelines

CP Initiatives

Follow CP