Abstract
The aim of this paper is to obtain new inequalities involving some topological indices of a graph and characterize graphs extremal with respect to them. Our main results provide lower bounds on several indices involving just the minimum and the maximum degree of the graph G. This family of indices includes, among others, the Wiener index and several of its generalizations, the harmonic index and the general sum-connectivity index, and the geometric-arithmetic index. We also include some chemical applications of our results and some open problems.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
A topological descriptor is a single number that represents a chemical structure in graph-theoretical terms via the molecular graph, they play a significant role in mathematical chemistry especially in the QSPR/QSAR investigations. A topological descriptor is called a topological index if it correlates with a molecular property. Topological indices are used to understand physicochemical properties of chemical compounds, since they capture some properties of a molecule in a single number. Hundreds of topological indices have been introduced and studied, starting with the seminal work by Wiener [41]. Since then, its mathematical properties and chemical applications have been intensively studied. The Wiener index of G is defined as
where \(\{ u,v\}\) runs over every pair of vertices in G.
Topological indices based on end-vertex degrees of edges have been used over 40 years. Among them, several indices are recognized to be useful tools in chemical researches. Probably, the best know such descriptor is the Randić connectivity index [30].
Two of the main successors of the Randić index are the first and second Zagreb indices, denoted by \(M_1\) and \(M_2\), respectively, and introduced by Gutman et al. in (see [21]). They are defined as
where uv denotes the edge of the graph G connecting the vertices u and v, and \(d_u\) is the degree of the vertex u.
The general sum-connectivity index was defined by Zhou and Trinajstić in [45] as
Note that \(\chi _{_{1}}\) is the first Zagreb index \(M_1\), \(2\chi _{_{-1}}\) is the harmonic index, \(\chi _{_{-1/2}}\) is the sum-connectivity index, etc.
The concept of variable molecular descriptors was proposed as a new way of characterizing heteroatoms in molecules (see [31, 32]), but also to assess the structural differences (e.g., the relative role of carbon atoms of acyclic and cyclic parts in alkylcycloalkanes [34]). The idea behind the variable molecular descriptors is that the variables are determined during the regression so that the standard error of estimate for a particular studied property is as small as possible.
In the paper of Gutman and Tošović [20], the correlation abilities of 20 vertex-degree-based topological indices occurring in the chemical literature were tested for the case of standard heats of formation and normal boiling points of octane isomers. It is remarkable to realize that variable indices provide indices that perform significantly better than the Randić index.
Countless applications of topological indices were reported, most of them concerned with exploring medicinal and pharmacological issues. A turning point in the mathematical examination of topological indices happened in the second half of the 1990s, when a significant and ever growing research field on this matter started, resulting in numerous publications. In this context, especially the papers of Erdös [1] and [2] should be mentioned.
Throughout this work, \(G=(V (G),E (G))\) denotes a (non-oriented) finite simple (without multiple edges and loops) non-trivial (\(E(G) \ne \emptyset \)) graph. A main topic in the study of topological indices is to find bounds of the indices involving several parameters. The aim of this paper is to obtain new inequalities for a large family of topological indices and to characterize the set of extremal graphs with respect to them. Our main results provide lower bounds on this family of topological indices involving just the minimum and the maximum degree of the graph. This family of indices includes, among others, the Wiener index and several of its generalizations (in Sect. 2), the harmonic index and the general sum-connectivity index (see Sects. 4 and 5, respectively), and the geometric-arithmetic index (in Sect. 6). Theorem 6 and Corollary 3 show some applications of our results in mathematical chemistry.
2 Wiener index and its generalizations
Along this section we just consider connected graphs G, in order to have defined d(u, v) for every \(u,v \in V(G)\).
Motivated by the Wiener index, Randić introduced in [33] an extension of the Wiener index for trees, and this has come to be known as the hyper-Wiener index. In [25], this extension was generalized to graphs as
WW(G) has been useful in correlations (see, e.g., [16] and the references therein). For information about the hyper-Wiener index in mathematics see, e.g., [3, 16, 23].
Also, it is interesting to generalize the Wiener index in the following way
with \(\lambda \in \mathbb {R}\). Obviously, if \(\lambda =1\), then \(W^\lambda \) coincides with the ordinary Wiener index W. Note that \(W^{-2}\) is the Harary index; \(W^{-1}\) is the reciprocal Wiener index; the quantity \(W^{2}\) is closely related to the hyper-Wiener index, since \(WW = (W^1 + W^2)/2\). Another topological index, proposed in [38] is expressed in terms of \(W^1\), \(W^2\) and \(W^3\) as \((2W^1+3W^2+W^3)/6\). See [24] for more connections of the same kind.
Three different variants of the q-Wiener index (\(q>0, \,q \ne 1\)) were defined in [42] as
where L is the diameter of G, and
Since \(\lim _{q\rightarrow 1}[k]_{q}=k\), we have
The Schultz index and the modified Schultz index of G are defined as
respectively.
For each fixed real number \(\alpha \), let us define the generalized Schultz-type indices by
see, e.g., [22]. For \(\alpha = 1\) the indices \(W_{\ddag }^{(\alpha )}(G)\), \(W_+^{(\alpha )}(G)\), and \(W_*^{(\alpha )}(G)\), reduce to \(W_+(G)\), and \(W_*(G)\), respectively.
Given any positive symmetric function \(g:[\delta ,\varDelta ]\times [\delta ,\varDelta ]\cap \mathbb {Z}^2 \rightarrow (0,\infty )\) and any non-negative function \(h:[\delta ,\varDelta ]\cap \mathbb {Z}\rightarrow [1,\infty )\), the (g, h)-Wiener index of G is defined as
This general approach allows to study in a unified way the previous indices.
Let us start with regular graphs. As usual, denote by \(K_{n}\) the complete graph with n vertices. Also, we write \(G_1 \cong G_2\) if the graphs \(G_1\) and \(G_2\) are isomorphic.
Theorem 1
Given \(1 \le \varDelta \), if h is a non-decreasing function, then we have for any graph G with minimum and maximum degree \(\varDelta \),
Furthermore, if h is strictly increasing, then \(W_{g,h}(G) = W_{g,h}(K_{\varDelta +1})\) if and only if \(G \cong K_{\varDelta +1}\).
Proof
Since every vertex in G has degree \(\varDelta \), there are at least \(\varDelta +1\) vertices and \(\frac{(\varDelta +1)\varDelta }{2}\) pairs of vertices. Furthermore, we have \(g(d_u,d_v) = g(\varDelta ,\varDelta )\) for every \(\{u,v\}\subseteq V(G)\). Hence, we have
Assume that h is strictly increasing. If \(\varDelta =1\), then \(G \cong K_{2}\) and the last statement holds. Assume now that \(\varDelta > 1\). If G is not isomorphic to \(K_{\varDelta +1}\), then there are at least \(\varDelta +2\) vertices and \(\frac{(\varDelta +2)(\varDelta +1)}{2}\) pairs of vertices, and at least \(\frac{\varDelta +2}{2}\) of these pairs are non-adjacent. Therefore,
This finishes the proof. \(\square \)
For any \(1 \le \delta <\varDelta \), let \({\mathcal {H}}_{\delta ,\varDelta }\) denote the family of graphs with \(\varDelta +1\) vertices where one of them has degree \(\delta \), \(\delta \) of them have degree \(\varDelta \), and \(\varDelta -\delta \) have degree \(\varDelta -1\).
In [27] we obtained the following:
Proposition 1
Given \(1 \le \delta < \varDelta \), there is a unique graph (up to isomorphism), \(H_{\delta ,\varDelta }\), in \({\mathcal {H}}_{\delta ,\varDelta }\).
Notice that in \(H_{\delta ,\varDelta }\) there are \(\frac{(\varDelta +1)\varDelta }{2}\) pairs of vertices, \(\frac{(\varDelta -1)\varDelta +2\delta }{2}\) of them are at distance 1 and \(\varDelta -\delta \) are at distance 2 (those with degree \(\varDelta -1\) from the vertex with degree \(\delta \)).
Therefore,
First, we prove a non-sharp (but simple) lower bound of \(W_{g,h}(G)\) (for any non-regular graph G) involving just the minimum and maximum degrees of G.
Theorem 2
Given \(1 \le \delta < \varDelta \), if g is a non-increasing function in the first variable and h is a non-decreasing function, then we have for any graph G with minimum degree \(\delta \) and maximum degree \(\varDelta \),
Proof
Since G has a vertex with degree \(\varDelta \), there are at least \(\varDelta +1\) vertices and \(\frac{(\varDelta +1)\varDelta }{2}\) pairs of vertices (since g is a non-increasing function in the first variable, we have \(g(d_u,d_v) \ge g(\varDelta ,\varDelta )\) for every \(\{u,v\}\subseteq V(G)\)). Since a vertex \(u_0\) has degree \(\delta \), there are at least \(\varDelta -\delta \) pairs of non-adjacent vertices, and we have \(g(d_{u_0},d_v) \ge g(\delta ,\varDelta )\) for these pairs of vertices \(\{u_0,v\}\subseteq V(G)\). Therefore,
\(\square \)
Next, we obtain sharp lower bounds of \(W_{g,h}\).
Definition 1
Let \({\mathcal {I}}\) be any topological index. A graph G with minimum degree \(\delta \) and maximum degree \(\varDelta \) is minimal for \({\mathcal {I}}\) if \({\mathcal {I}}(G) \le {\mathcal {I}}(\varGamma )\) for every graph \(\varGamma \) with minimum degree \(\delta \) and maximum degree \(\varDelta \). A graph G with minimum degree \(\delta \), maximum degree \(\varDelta \) and n vertices is n-minimal for \({\mathcal {I}}\) if \({\mathcal {I}}(G) \le {\mathcal {I}}(\varGamma )\) for every graph \(\varGamma \) with minimum degree \(\delta \), maximum degree \(\varDelta \) and n vertices.
Theorem 3
Given \(1 \le \delta < \varDelta \), if g is a non-increasing function in the first variable and h is a non-decreasing function, then \(H_{\delta ,\varDelta }\) is \((\varDelta +1)\)-minimal for \(W_{g,h}\). Moreover, if g is strictly decreasing in the first variable or h is strictly increasing, then G is \((\varDelta +1)\)-minimal for \(W_{g,h}\) if and only if \(G\cong H_{\delta ,\varDelta }\).
Proof
Suppose G has \(\varDelta +1\) vertices, \(x_0,x_1,\dots , x_{\varDelta }\). Without loss of generality we can assume that \(x_0\) has degree \(\delta \) and that \(x_{\delta +1},\dots , x_{\varDelta }\) are not adjacent to \(x_0\). Therefore, \(d(x_0,x_i)\ge 2\) and \(x_i\) has degree at most \(\varDelta -1\) for every \(i>\delta \). Thus, since g is non-increasing in the first variable and h is non-decreasing,
If \(G\not \cong H_{\delta ,\varDelta }\), then there is some other pair of vertices which are not adjacent and there exist either two vertices with degree less than \(\varDelta -1\) or \(\varDelta -\delta +2\) vertices with degree less than \(\varDelta \). Therefore, if g is strictly decreasing in the first variable or h is strictly increasing, it is immediate to check that \(W_{g,h}(G)>W_{g,h}(H_{\delta ,\varDelta }).\)\(\square \)
Theorem 4
Suppose \(1 \le \delta < \varDelta \), g is a non-increasing function in the first variable and h is a non-decreasing function. If G is any graph with minimum degree \(\delta \) and maximum degree \(\varDelta \) and the following conditions hold
-
(i)
\(\left[ \left( {\begin{array}{c}\varDelta +1\\ 2\end{array}}\right) - \left( {\begin{array}{c}\delta \\ 2\end{array}}\right) \right] g(\varDelta ,\varDelta )\ge \left[ \left( {\begin{array}{c}\varDelta \\ 2\end{array}}\right) - \left( {\begin{array}{c}\delta \\ 2\end{array}}\right) \right] g(\varDelta -1,\varDelta -1)\),
-
(ii)
\((\varDelta -\delta +1)g(\delta ,\varDelta )\ge (\varDelta -\delta )g(\delta ,\varDelta -1)\),
then
Furthermore, if either g is strictly decreasing in the first variable or h is strictly increasing, then \(W_{g,h}(G) = W_{g,h}(H_{\delta ,\varDelta })\) if and only if \(G \cong H_{\delta ,\varDelta }\).
Proof
If G has \(\varDelta +1\) vertices, then the results follow from Theorem 3. Suppose G has at least \(\varDelta +2\) vertices, \(x_0,\dots , x_{\varDelta +1}\). Then, there are \(\left( {\begin{array}{c}\varDelta +2\\ 2\end{array}}\right) \) pairs of vertices in G. We can assume that \(x_0\) has degree \(\delta \), and that \(x_0\) is not adjacent to \(x_{\delta +1},\dots , x_{\varDelta +1}\). Also, since the maximum degree is \(\varDelta \), the vertices \(x_1,\dots ,x_\delta \) are not adjacent to every vertex. Therefore, there are at least \(\frac{\delta }{2}\) pairs of non-adjacent vertices in \(\{x_1,\dots ,x_{\varDelta +1}\}\). Thus,
Now, notice that since h is non-decreasing,
and since g is non-increasing,
where
Thus, it suffices to check that
and this holds if conditions (i), (ii) are satisfied.
If h (respectively, g) is strictly increasing (respectively, decreasing in the first variable), then the inequality (1) (respectively, (2)) is strict, and then \(W_{g,h}(G) > W_{g,h}(H_{\delta ,\varDelta })\). This finishes the proof. \(\square \)
Corollary 1
Suppose \(1 \le \delta < \varDelta \), g is a constant function \(g=c\) and h is a non-decreasing function. If G is any graph with minimum degree \(\delta \) and maximum degree \(\varDelta \), then
Furthermore, if h is strictly increasing, then \(W_{g,h}(G) = W_{g,h}(H_{\delta ,\varDelta })\) if and only if \(G \cong H_{\delta ,\varDelta }\).
Thus, by taking \(g=1\) and \(h(t)=t\) in Corollary 1, we obtain the following inequality for one of the main topological indices: the Wiener index.
Theorem 5
Given \(1 \le \delta < \varDelta \), we have for any graph G with minimum degree \(\delta \) and maximum degree \(\varDelta \),
with equality if and only if \(G \cong H_{\delta ,\varDelta }\).
Although only about 1000 benzenoid hydrocarbons are known, the number of possible benzenoid hydrocarbons is huge. For instance, the number of possible benzenoid hydrocarbons with 35 benzene rings is 5851000265625801806530 [39]. Therefore, the modeling of their physico-chemical properties is very important in order to predict properties of currently unknown species. The main reason for use topological indices is to obtain prediction of some property of molecules (see, e.g., [13, 17, 20, 34]). Therefore, given some fixed parameters, a natural problem is to find the graphs that minimize (or maximize) the value of a topological index on the set of chemical graphs (graphs with maximum degree at most 4) satisfying the restrictions given by the parameters (see, e.g., [1, 2, 4, 5, 10,11,12, 18]).
Theorems 1 and 5 have the following consequence for chemical graphs.
Theorem 6
Let G be a chemical graph with minimum degree \(\delta \) and maximum degree \(\varDelta \).
If \((\varDelta ,\delta )=(4,4)\), then \(W(G) \ge 10,\) with equality if and only if \(G \cong K_{5}\).
If \((\varDelta ,\delta )=(4,3)\), then \(W(G) \ge 11,\) with equality if and only if G has five vertices, two of them with degree 3 and three with degree 4.
If \((\varDelta ,\delta )=(4,2)\), then \(W(G) \ge 12,\) with equality if and only if G has five vertices, one of them with degree 2, two with degree 3 and two with degree 4.
If \((\varDelta ,\delta )=(4,1)\), then \(W(G) \ge 13,\) with equality if and only if G has five vertices, one of them with degree 1, three with degree 3 and one with degree 4.
If \((\varDelta ,\delta )=(3,3)\), then \(W(G) \ge 6,\) with equality if and only if \(G \cong K_{4}\).
If \((\varDelta ,\delta )=(3,2)\), then \(W(G) \ge 7,\) with equality if and only if G has four vertices, two of them with degree 2 and two with degree 3.
If \((\varDelta ,\delta )=(3,1)\), then \(W(G) \ge 8,\) with equality if and only if G has four vertices, one of them with degree 1, two with degree 2 and one with degree 3.
If \((\varDelta ,\delta )=(2,2)\), then \(W(G) \ge 3,\) with equality if and only if \(G \cong K_{3}\).
If \((\varDelta ,\delta )=(2,1)\), then \(W(G) \ge 4,\) with equality if and only if G is a path graph with 3 vertices.
If \((\varDelta ,\delta )=(1,1)\), then \(W(G) \ge 1,\) with equality if and only if \(G \cong K_{2}\).
The pictures of the minimizing chemical graphs in Theorem 6 appear in Fig. 1.
Other choices of h in Corollary 1 with \(g=1\), give the following results.
Theorem 7
Given \(1 \le \delta < \varDelta \), we have for any graph G with minimum degree \(\delta \) and maximum degree \(\varDelta \),
with equality if and only if \(G \cong H_{\delta ,\varDelta }\).
Theorem 8
Given \(1 \le \delta < \varDelta \) and \(\lambda >0\), we have for any graph G with minimum degree \(\delta \) and maximum degree \(\varDelta \),
with equality if and only if \(G \cong H_{\delta ,\varDelta }\).
Since \([k]_{q}\) (respectively, \([k]_{q} \, q^{L-k}\) and \([k]_{q} \, q^{k}\)) is an increasing function on k for \(q>0\) (respectively, \(0<q<1\) and \(q>1\)), Corollary 1 has the following consequence.
Theorem 9
Given \(1 \le \delta < \varDelta \) and \(q>0\), we have for any graph G with minimum degree \(\delta \) and maximum degree \(\varDelta \),
with equality in each inequality if and only if \(G \cong H_{\delta ,\varDelta }\).
Given \(1 \le \delta < \varDelta \), let us define
Notice that \(\sigma _{\delta ,\varDelta },\eta _{\delta ,\varDelta },\mu _{\delta ,\varDelta }<0\). Then, Theorem 4 yields the following results:
Theorem 10
Given \(1 \le \delta < \varDelta \) and \(\alpha <0\), for any graph G with minimum degree \(\delta \) and maximum degree \(\varDelta \):
-
If \(\alpha \ge \sigma _{\delta ,\varDelta }\) and \((\varDelta -\delta +1)(\delta ^\alpha +\varDelta ^\alpha )\ge (\varDelta -\delta )[\delta ^\alpha + (\varDelta -1)^\alpha ]\), then
$$\begin{aligned} \begin{aligned} W_{\ddag }^{(\alpha )}(G)&\ge \delta (\delta ^\alpha +\varDelta ^\alpha )+2\left( {\begin{array}{c}\delta \\ 2\end{array}}\right) \varDelta ^\alpha +2\left( {\begin{array}{c}\varDelta -\delta \\ 2\end{array}}\right) (\varDelta -1)^\alpha \\&\quad + \delta (\varDelta -\delta )((\varDelta -1)^\alpha +\varDelta ^\alpha )+2(\varDelta -\delta )(\delta ^\alpha +(\varDelta -1)^\alpha ), \end{aligned} \end{aligned}$$ -
If \(\alpha \ge \sigma _{\delta ,\varDelta }\) and \(\alpha \ge \eta _{\varDelta ,\delta }\), then
$$\begin{aligned} \begin{aligned} W_+^{(\alpha )}(G)&\ge \delta (\delta +\varDelta )^\alpha +2^\alpha \left( {\begin{array}{c}\delta \\ 2\end{array}}\right) \varDelta ^\alpha +2^\alpha \left( {\begin{array}{c}\varDelta -\delta \\ 2\end{array}}\right) (\varDelta -1)^\alpha \\&\quad + \delta (\varDelta -\delta )(2\varDelta -1)^\alpha +2(\varDelta -\delta )(\delta +\varDelta -1)^\alpha , \end{aligned} \end{aligned}$$ -
If \(\alpha \ge \frac{1}{2}\, \sigma _{\delta ,\varDelta }\) and \(\alpha \ge \mu _{\varDelta ,\delta }\), then
$$\begin{aligned} \begin{aligned} W_*^{(\alpha )}(G)&\ge \delta ^{\alpha +1}\varDelta ^\alpha +\left( {\begin{array}{c}\delta \\ 2\end{array}}\right) \varDelta ^{2\alpha }+ \left( {\begin{array}{c}\varDelta -\delta \\ 2\end{array}}\right) (\varDelta -1)^{2\alpha } \\&\quad + \delta (\varDelta -\delta )(\varDelta -1)^\alpha \varDelta ^\alpha +2(\varDelta -\delta )\delta ^\alpha (\varDelta -1)^\alpha , \end{aligned} \end{aligned}$$
with equality in each inequality if and only if \(G \cong H_{\delta ,\varDelta }\).
The multiplicative Wiener index of G is defined in [19] as
The mathematical arguments leading to this index have been outlined in due detail in [19].
Given any function \(f:[\delta ,\varDelta ]\cap \mathbb {Z}\rightarrow [1,\infty )\), the f-multiplicative Wiener index of G is defined as
Theorem 11
Suppose \(1 \le \delta < \varDelta \), and f is a non-decreasing function. If G is any graph with minimum degree \(\delta \) and maximum degree \(\varDelta \), then
Furthermore, if f is strictly increasing, then \(\pi _{f}(G) = \pi _{f}(H_{\delta ,\varDelta })\) if and only if \(G \cong H_{\delta ,\varDelta }\).
Proof
Since
\(\log f \ge 0\) and the logarithm is a strictly increasing function, Corollary 1 gives the result. \(\square \)
Therefore, by taking \(f(t)=t\), we obtain the following.
Corollary 2
Suppose \(1 \le \delta < \varDelta \). If G is any graph with minimum degree \(\delta \) and maximum degree \(\varDelta \), then
Furthermore, \(\pi (G) = \pi (H_{\delta ,\varDelta })\) if and only if \(G \cong H_{\delta ,\varDelta }\).
Corollary 3
The minimizing graphs in Theorems 7, 8, 9, 10, 11 and 6 are identical. They are represented in Fig. 1.
3 General estimates
Given integers \(1 \le \delta \le \varDelta \), let us define \({\mathcal {G}}_{\delta ,\varDelta }\) as the set of graphs G with \(|V(G)|=\varDelta +1\), minimum degree \(\delta \), maximum degree \(\varDelta \), and such that:
(1) G is isomorphic to the complete graph with \(\varDelta +1\) vertices \(K_{\varDelta +1}\), if \(\delta = \varDelta \),
(2) there are \(\varDelta \) vertices with degree \(\delta \), if \(\delta < \varDelta \) and \(\varDelta (\delta +1)\) is even,
(3) there are \(\varDelta -1\) vertices with degree \(\delta \) and a vertex with degree \(\delta +1\), if \(\delta < \varDelta -1\) and \(\varDelta (\delta +1)\) is odd,
(4) there are \(\varDelta -1\) vertices with degree \(\delta \) and two vertices with degree \(\varDelta \), if \(\delta = \varDelta -1\) and \(\varDelta \) is odd (and thus \(\varDelta (\delta +1)\) is odd).
Remark 1
Every graph \(G \in {\mathcal {G}}_{\delta ,\varDelta }\) has maximum degree \(\varDelta \) and \(|V(G)|=\varDelta +1\). Hence, every graph \(G \in {\mathcal {G}}_{\delta ,\varDelta }\) is connected.
Proposition 2
For any integers \(1 \le \delta \le \varDelta \), we have \({\mathcal {G}}_{\delta ,\varDelta } \ne \emptyset \). Let G be a graph with minimum degree \(\delta \) and maximum degree \(\varDelta \). Then
and
with equality if and only if \(G \in {\mathcal {G}}_{\delta ,\varDelta }\).
In [28] we obtained the following:
Theorem 12
Let us consider \(\alpha \in \mathbb {R}\) with \(\alpha <0\), any integers \(1 \le \delta \le \varDelta \), and a graph G with minimum degree \(\delta \) and maximum degree \(\varDelta \). The following inequalities hold:
If \(\varDelta (\delta +1)\) is even and
then \(G\in {\mathcal {G}}_{\delta ,\varDelta }\) is minimal for \(\chi _{\alpha }\) and thus,
Moreover, if the inequality (3) is strict, then G is minimal for \(\chi _{\alpha }\) if and only if \(G\in {\mathcal {G}}_{\delta ,\varDelta }\).
If \(\varDelta (\delta +1)\) is odd and
then \(G\in {\mathcal {G}}_{\delta ,\varDelta }\) is minimal for \(\chi _{\alpha }\) and thus,
Moreover, if the inequality (4) is strict, then G is minimal for \(\chi _{\alpha }\) if and only if \(G\in {\mathcal {G}}_{\delta ,\varDelta }\).
Corollary 4
For any \(\alpha \in \mathbb {R}\) with \(\alpha <0\), a graph G with minimum and maximum degree \(\delta =\varDelta \ge 1\) is mimimal for \(\chi _{\alpha }\) if and only if \(G \cong K_{\varDelta +1}\).
4 Harmonic index
Another remarkable topological descriptor is the harmonic index, defined in [14] as
This index has attracted a great interest in the lasts years (see, e.g., [9, 15, 43, 44] and the references therein).
If G is a graph with m edges and maximum degree \(\varDelta \), then it is trivial to check that
Proposition 3
Let G be a graph with minimum degree \(\delta \) and maximum degree \(\varDelta \). Then
with equality if and only if \(G \cong K_{\varDelta +1}\).
Proof
The inequality follows from (5) and Proposition 2. If G is isomorphic to the complete graph \(K_{\varDelta +1}\), then it is clear that the equality holds. If the equality holds, then the number of edges is minimal, and so, \(G \in {\mathcal {G}}_{\delta ,\varDelta }\) by Proposition 2. Also, every edge joins two vertices with degree \(\varDelta \). Therefore, \(\delta =\varDelta \) and G is isomorphic to the complete graph \(K_{\varDelta +1}\). \(\square \)
Proposition 4
For every integers \(1\le \delta \le \varDelta \) and \(G \in {\mathcal {G}}_{\delta ,\varDelta }\), we have
and
Proof
The equalities follow from the definitions of H and \({\mathcal {G}}_{\delta ,\varDelta }\). The inequality is trivial. \(\square \)
Remark 2
Notice that the expression \(\frac{2(\varDelta -1) }{\delta +\varDelta }+\frac{2 }{\delta +1+\varDelta }+\frac{2\delta }{2\delta +1}+\frac{(\varDelta -2)(\delta -1)-1}{2\delta }\) can be greater (see, e.g., \(\delta =3\) and \(\varDelta =7\)) or smaller (see, e.g., \(\delta =10\) and \(\varDelta =11\)) than \(\frac{2\varDelta }{\delta +\varDelta } +\frac{\varDelta (\delta -1)}{2\delta }\).
Note that the harmonic index of the complete bipartite graph is \(H(K_{\delta ,\varDelta })=\frac{2\delta \varDelta }{\delta +\varDelta }\). Also notice that if \(\delta =1\), then \(K_{\delta ,\varDelta }\) and \(G\in {\mathcal {G}}_{\delta ,\varDelta }\) are both the star graph.
Proposition 5
Consider any integers \(1 < \delta \le \varDelta \) with \(\varDelta (\delta +1)\) even and define \(\alpha =\delta / \varDelta \). Then for any \(G\in {\mathcal {G}}_{\delta ,\varDelta }\),
-
\(H(K_{\delta ,\varDelta })> H(G)\) if and only if \(\alpha > \frac{1}{3}\),
-
\(H(K_{\delta ,\varDelta })= H(G)\) if and only if \(\alpha = \frac{1}{3}\),
-
\(H(K_{\delta ,\varDelta })< H(G)\) if and only if \(\alpha < \frac{1}{3}\).
Proof
We have
Therefore, if suffices to check if
This follows immediately since \(\delta >1\) and \(\frac{2}{1+\alpha }\ge \frac{1}{2\alpha }\) if and only if \(\alpha \in [\frac{1}{3},1]\). Moreover, the equality only holds for \(\alpha =\frac{1}{3}\). \(\square \)
Notice that Theorem 12 is not very useful to find the minimal graph for the harmonic index since for almost every case, the inequalities (3) and (4) do not hold. (Notice that a graph is minimal for the harmonic index if and only if it is minimal for \(\chi _{_{-1}}\).) Let us analyze the (easier) case when \(\varDelta (\delta +1)\) is even.
Proposition 6
Suppose \(\alpha =-1\), \(1 \le \delta \le \varDelta \) and \(\varDelta (\delta +1)\) is even. Given a graph G with minimum degree \(\delta \) and maximum degree \(\varDelta \), then (3) holds if and only if
Proof
It is immediate to check that
\(\square \)
Thus, it can be seen that (3) holds in a few cases:
Corollary 5
Given \(\alpha =-1\), \(1 = \delta \le \varDelta \), and a graph G with minimum degree \(\delta \) and maximum degree \(\varDelta \), then (3) holds if and only if \(1\le \varDelta \le 3\).
Corollary 6
Given \(\alpha =-1\), \(2 = \delta \le \varDelta \) with \(\varDelta \) even, and a graph G with minimum degree \(\delta \) and maximum degree \(\varDelta \), then (3) holds if and only if \(\varDelta =2\).
Proof
By Proposition 6, (3) holds if and only if (6) holds. Thus, since \(\delta =2\), it suffices to see that
The solutions of this cubic equation are \(x_1\approx -7.4\), \(x_2\approx 0.4\) and \(x_3\approx 3.04\). Thus, the only solutions of the inequality where \(\varDelta \ge \delta \) are \(\varDelta =2\) or \(\varDelta =3\) and in this last case, \(\varDelta (\delta +1)\) is not even. \(\square \)
Corollary 7
Given \(\alpha =-1\), \(3 \le \delta \le \varDelta \) with \(\varDelta (\delta +1)\) even, and a graph G with minimum degree \(\delta \) and maximum degree \(\varDelta \), then (3) holds if and only if \(\delta =\varDelta \).
Proof
By Corollary 4, (3) holds if \(\delta =\varDelta \). Assume now that \(\delta < \varDelta \). By Proposition 6, (3) holds if and only if (6) holds. It is immediate to check that:
However, since \(3\le \delta <\varDelta \), it is trivial that
and therefore
\(\square \)
5 General sum-connectivity index
Theorem 12 is not very useful either to find minimal graphs for the sum-connectivity index since the inequalities (3) and (4) almost never hold. Let us analyze the (easier) case when \(\varDelta (\delta +1)\) is even.
Let us define
Notice that \(N_{\delta ,\varDelta }\) is increasing in both variables for \(1\le \delta \le \varDelta \) and that \(\varepsilon _{\delta ,\varDelta }> \lambda _{\delta ,\varDelta }>1\) for every \(\varDelta >\delta \).
Since \(\chi _{_{-1/2}}\) is the sum-connectivity index \(\chi \), Theorem 12 implies the following:
Proposition 7
Suppose \(\alpha =-\frac{1}{2}\), \(1 \le \delta < \varDelta \) and \(\varDelta (\delta +1)\) is even. Given a graph G with minimum degree \(\delta \) and maximum degree \(\varDelta \), then (3) does not hold if
Proof
First, let us see that
Notice that, since \(\delta <\varDelta \),
Therefore, (3) does not hold if
and, since \(\varDelta -\delta +\frac{\varDelta (\delta -1)}{2}=N_{\delta ,\varDelta }\), then (3) does not hold if
\(\square \)
Proposition 8
If \(9\le \delta < \varDelta \), then \(N_{\delta ,\varDelta } > \frac{1}{\lambda _{\delta ,\varDelta }-1}\).
Proof
Since \(\varDelta >\delta \) then \(N_{\delta ,\varDelta } \ge \frac{(\delta +1)^2}{2}-\delta \) and \(\lambda _{\delta ,\varDelta }\ge \sqrt{\frac{2(\delta +1)}{2\delta +1}}\) which means that
Thus, it suffices to check that
The real solutions of the equation \(\delta ^4-8\delta ^3-2\delta ^2-16\delta -7=0\) are \(x_1\approx -0.4\) and \(x_2\approx 8.5\). Therefore, \(N_{\delta ,\varDelta } > \frac{1}{\lambda _{\delta ,\varDelta }-1}\) for every \(\delta \ge 9\). \(\square \)
Corollary 8
Suppose \(\alpha =-\frac{1}{2}\), \(9 \le \delta \le \varDelta \) and \(\varDelta (\delta +1)\) is even. If G is a graph with minimum degree \(\delta \) and maximum degree \(\varDelta \), then (3) holds if and only if \(\delta =\varDelta \).
Proposition 9
Suppose \(\alpha =-\frac{1}{2}\), \(1 \le \delta < \varDelta \) and \(\varDelta (\delta +1)\) is even. If G is a graph with minimum degree \(\delta \) and maximum degree \(\varDelta \), then (3) holds if
Proof
First, let us see that
Notice that, since \(\delta <\varDelta \),
Therefore, (3) holds if
and, since \(\varDelta -\delta +\frac{\varDelta (\delta -1)}{2}=N_{\delta ,\varDelta }\), then (3) holds if
\(\square \)
However, this proposition does not provide many positive results:
Proposition 10
If \(4\le \delta < \varDelta \), then \(N_{\delta ,\varDelta } > \frac{1}{\varepsilon _{\delta ,\varDelta }-1}\).
Proof
Since \(\varDelta >\delta \) then \(N_{\delta ,\varDelta } \ge \frac{(\delta +1)^2}{2}-\delta \) and \(\varepsilon _{\delta ,\varDelta }\ge \sqrt{\frac{\delta +1}{\delta }}\) which means that
Thus, it suffices to check that
which is trivially satisfied for every \(\delta \ge 4\). \(\square \)
Corollary 9
If \(1=\delta < \varDelta \), then \(N_{\delta ,\varDelta } \le \frac{1}{\varepsilon _{\delta ,\varDelta }-1}\) if and only if \(\varDelta = 2\).
Proof
Note that, in this case, \(\varDelta (\delta +1)=2\varDelta \) is even. \(N_{\delta ,\varDelta } \le \frac{1}{\varepsilon _{\delta ,\varDelta }-1}\) if and only if \(\frac{N_{\delta ,\varDelta }+1}{N_{\delta ,\varDelta }}\ge \varepsilon _{\delta ,\varDelta }\). Thus, it suffices to check that
and therefore, \(\varDelta \in \{1,2\}\). Since \(\varDelta >1\), this is equivalent to \(\varDelta = 2\). \(\square \)
Corollary 10
If \(2=\delta < \varDelta \) with \(\varDelta (\delta +1)\) even, then \(N_{\delta ,\varDelta } > \frac{1}{\varepsilon _{\delta ,\varDelta }-1}\).
Proof
Note that
The solutions of the equation \(9\varDelta ^3-42\varDelta ^2+40\varDelta -8 = 0\) are \(x_1\approx 0.3\), \(x_2\approx 0.9\), \(x_3\approx 3.4\) and therefore, there are no even integer solutions such that \(2<\varDelta \). \(\square \)
Corollary 11
If \(3=\delta < \varDelta \), then \(N_{\delta ,\varDelta } \le \frac{1}{\varepsilon _{\delta ,\varDelta }-1}\) if and only if \(\varDelta =4\).
Proof
Note that, in this case, \(\varDelta (\delta +1)\) is even. We have
The solutions of the equation \(4\varDelta ^3-24\varDelta ^2+33\varDelta -12 = 0\) are \(x_1\approx 0.6\), \(x_2\approx 1.2\), \(x_3\approx 4.2\) and therefore, the only integer solution with \(\varDelta >3\) is \(\varDelta =4\). \(\square \)
6 Geometric-arithmetic index
The first geometric-arithmetic index\(GA_1\), defined in [40] as
where uv denotes the edge of the graph G connecting the vertices u and v, and \(d_u\) is the degree of the vertex u, is one of the successors of the Randić index. Although \(GA_1\) was introduced in 2009, there are many papers dealing with this index (see, e.g., [6,7,8, 29, 36, 37, 40] and the references therein).
Let us recall Corollary 2.3 in [35].
Corollary 12
Let g be the function \(g(x, y) = \frac{2\sqrt{xy}}{x+y}\) with \(0 < a\le x, y \le b\). Then \(\frac{2\sqrt{ab}}{a+b}\le g(x,y)\le 1.\) The equality in the lower bound is attained if and only if either \(x = a\) and \(y = b\), or \(x = b\) and \(y = a\), and the equality in the upper bound is attained if and only if \(x = y\).
Let us recall the following example from [26, Example 2.11].
Example 1
Let us suppose \(\delta =4\) and \(\varDelta =56\). Consider a graph G with 57 vertices, two of them, \(a_1,a_2\) with degree 56 and the rest, \(b_1,\dots ,b_{55}\) with degree 4. Let us assume the edges are as follows. There is an edge \(a_ib_j\) for every i, j, an edge \(a_1a_2\) and the vertices \(b_1,\dots ,b_{55}\) induce a cycle of length 55. Note that these edges produce the claimed degree in each vertex.
Notice that G has 166 edges, one of them joins two vertices of degree 56, 110 of them join vertices with degree 56 with vertices with degree 4 and 55 of them join vertices with degree 4. Therefore, \(GA_1(G)=\frac{2\cdot 110 \sqrt{4\cdot 56}}{4+56} + 56=\frac{ 220 \sqrt{224}}{60} + 56\approx 110.8776.\)
However, \(GA_1(H)=\frac{112\sqrt{224}}{60}+84\approx 111.9377\) for every \(H \in {\mathcal {G}}_{4,56}\), and \(GA_1(K_{4,56})=\frac{448 \sqrt{224}}{60}\approx 111.7508. \)
Given integers \(0<i\le \delta < \varDelta \), let us define \({\mathcal {H}}^i_{\delta ,\varDelta }\) as the set of graphs H with minimum degree \(\delta \), maximum degree \(\varDelta \), \(|V(H)|=\varDelta +1\), and such that:
(1) there are i vertices with degree \(\varDelta \) and \(\varDelta -i+1\) vertices with degree \(\delta \), if \((\varDelta -i+1) (\delta -i)\) is even,
(2) there are i vertices with degree \(\varDelta \), \(\varDelta -i\) vertices with degree \(\delta \) and an additional vertex with degree \(\delta +1\) (possibly \(\varDelta \) if \(\delta =\varDelta -1\)), if \((\varDelta -i+1) (\delta -i)\) is odd.
Note that the graph from Example 1 belongs to \({\mathcal {H}}^2_{4,56}\).
Remark 3
Every graph \(H \in {\mathcal {H}}_{\delta ,\varDelta }\) has maximum degree \(\varDelta \) and \(|V(H)|=\varDelta +1\). Hence, every graph \(H \in {\mathcal {H}}_{\delta ,\varDelta }\) is connected. Notice also that the subgraph of H induced by the set of vertices with degree \(\varDelta \) is complete.
Remark 4
By definition, \({\mathcal {G}}_{\delta ,\varDelta }={\mathcal {H}}^1_{\delta ,\varDelta }\) for every \(\delta <\varDelta \) and \({\mathcal {G}}_{\varDelta -1,\varDelta }={\mathcal {H}}^2_{\varDelta -1,\varDelta }\) if \(\varDelta \) is odd (and therefore, \(\varDelta ^2\) is odd and \((\varDelta -1)(\varDelta -3)\) is even).
Proposition 11
For any integers \(1 \le i\le \delta < \varDelta \), we have \({\mathcal {H}}^i_{\delta ,\varDelta } \ne \emptyset \).
Proof
We are going to define a graph H with \(\varDelta +1\) vertices, \(v_1,\dots ,v_{\varDelta +1}\). The vertices \(v_{\varDelta -i+2},\dots ,v_{\varDelta +1}\) define a complete graph, and let us define an edge joining \(v_j\) with \(v_k\) for every \(j\le \varDelta -i+1 <k\). Thus, \(d_{v_j}= \varDelta \) for every \(j>\varDelta -i+1\).
First, suppose \(\delta -i\) is even. Thus, \((\varDelta -i+1) (\delta -i)\) is even. We have already i edges in each \(v_j\) with \(j\le \varDelta -i+1\). We are going to add edges so that \(d_{v_j}=\delta \) for every \(j\le \varDelta -i+1\). Note that this holds if \(\delta =i\), so we can assume that \(\delta > i\). Let us define for every \(1\le j,k\le \varDelta -i+1\), \(||j-k||=\min \{|j-k|,\varDelta -i+1-|j-k|\}\), i.e., \(||j-k||\) is the distance between the vertices \(v_j\) and \(v_k\) in the cycle \(v_1,v_2,\dots ,v_{\varDelta -i+1},v_1\). Consider an edge \(v_jv_k\) for every pair of vertices with \(||j-k||\le \frac{\delta -i}{2}\). This is possible since \(\delta -i\) is even and \(\delta -i<\varDelta -i\). Then, every vertex \(v_j\) with \(j\le \varDelta -i+1\) satisfies that \(d_{v_j}=\delta \) and \(H \in {\mathcal {H}}^i_{\delta ,\varDelta }\).
Now, suppose \(\delta -i\) is odd and \(\varDelta -i+1\) is even. Thus, \((\varDelta -i+1) (\delta -i)\) is even. Consider an edge \(v_jv_k\) for every pair of vertices with \(||j-k||\le \frac{\delta -i-1}{2} \) and an edge \(v_jv_k\) if \(||j-k||=\frac{\varDelta -i+1}{2}\). Notice that this is well defined since \(\varDelta -i+1\) is even and it is a new edge (recall that \(\frac{\varDelta -i+1}{2}>\frac{\delta -i-1}{2}\)). Thus, every vertex \(v_j\) with \(j\le \varDelta -i+1\) satisfies that \(d_{v_j}=\delta \) and \(H \in {\mathcal {H}}^i_{\delta ,\varDelta }\).
Finally, suppose \(\delta -i\) and \(\varDelta -i+1\) are odd. Therefore, \((\varDelta -i+1) (\delta -i)\) is odd. Consider an edge \(v_jv_k\) for every pair of vertices with \(||j-k||\le \frac{\delta -i-1}{2}\). Now every vertex \(v_j\) with \(j\le \varDelta -i+1\) has degree \(\delta -1\). Let us define, for every \(1\le j<k\le \varDelta -i\), an edge \(v_jv_k\) if \(k-j=\frac{\varDelta -i}{2}\) (this edge is new since \(\frac{\delta -i-1}{2}<\frac{\varDelta -i}{2}\)). Now, \(d_{v_j}=\delta \) for every \(1\le j\le \varDelta -i\). It suffices to define an edge joining \(v_{\varDelta -i+1}\) to any non-adjacent vertex \(v_{j_0}\), for example \(j_0=\frac{\delta -i-1}{2}+1\), and therefore, \(H \in {\mathcal {H}}^i_{\delta ,\varDelta }\). Notice that, in this case, \(d_{v_k}=\varDelta \) for every \(k> \varDelta -i+1\), \(d_{v_{j_0}}=\delta +1\) and \(d_{v_j}=\delta \) for every \(j\le \varDelta -i+1\) with \(j\ne j_0\). \(\square \)
Proposition 12
For every integers \(1 \le i \le \delta < \varDelta \) and \(H \in {\mathcal {H}}^i_{\delta ,\varDelta }\), we have
Proof
The equalities follow from the definitions of \(GA_1\) and \({\mathcal {H}}^i_{\delta ,\varDelta }\).
To obtain the inequality, it suffices to check that
The first claim follows from Corollary 12. For the second claim it suffices to check that
Since \(\delta \ge i\), then it is immediate to see that
\(\square \)
Proposition 13
For any integers \(1<i\le \delta <\varDelta \), if \(\varDelta (\delta +1)\) is even, \(\alpha =\frac{\delta }{\varDelta }\) and \(\frac{\varDelta }{\varDelta -i}>\frac{2(1-\sqrt{\alpha }\,)^2}{1-\alpha ^2}\), then for any \(G\in {\mathcal {G}}_{\delta ,\varDelta }\) and \(H\in {\mathcal {H}}^i_{\delta ,\varDelta }\), we have \(GA_1(H)>GA_1(G).\)
Proof
Let us see that
Notice that
with \(\delta +\varDelta -i>0\). Therefore, if \(\varepsilon =\frac{2\sqrt{\delta \varDelta }}{\delta +\varDelta }\), it suffices to check that
\(\square \)
Corollary 13
For any integers \(1<i\le \delta <\varDelta \), if \(\varDelta (\delta +1)\) is even and \(\delta \ge 0.09 \varDelta \), then for any \(G\in {\mathcal {G}}_{\delta ,\varDelta }\) and \(H\in {\mathcal {H}}^i_{\delta ,\varDelta }\), we have \(GA_1(H)>GA_1(G).\)
Proof
Let us define \(\alpha =\delta /\varDelta \in (0,1)\). Notice that we have \(\frac{\varDelta }{\varDelta -i}> 1\) for every \(i>1\). Thus, let us check that
Since the real roots of the equation \(x^4+4x^3+6x^2-12x+1=0\) are \(x_1\approx 0.087\) and \(x_1=1\), it is clear that the condition is satisfied for every \(\alpha \in [0.09,1)\). \(\square \)
Conjecture 13
Given any integers \(1< \delta <\varDelta \), a graph G is minimal for \(GA_1\) if and only if \(G\in {\mathcal {H}}^i_{\delta ,\varDelta }\) for some \(1\le i \le \delta \).
References
B. Bollobás, P. Erdös, Graphs of extremal weights. Ars Comb. 50, 225–233 (1998)
B. Bollobás, P. Erdös, A. Sarkar, Extremal graphs for weights. Discrete Math. 200, 5–19 (1999)
G.G. Cash, Relationship between the Hosoya polynomial and the hyper-Wiener index. Appl. Math. Lett. 15, 893–895 (2002)
R. Cruz, H. Giraldo, J. Rada, Extremal values of vertex-degree topological indices over hexagonal systems. MATCH Commun. Math. Comput. Chem. 70, 501–512 (2013)
K.C. Das, Maximizing the sum of the squares of the degrees of a graph. Discrete Math. 285, 57–66 (2004)
K.C. Das, On geometric-arithmetic index of graphs. MATCH Commun. Math. Comput. Chem. 64, 619–630 (2010)
K.C. Das, I. Gutman, B. Furtula, Survey on geometric-arithmetic indices of graphs. MATCH Commun. Math. Comput. Chem. 65, 595–644 (2011)
K.C. Das, I. Gutman, B. Furtula, On first geometric-arithmetic index of graphs. Discrete Appl. Math. 159, 2030–2037 (2011)
H. Deng, S. Balachandran, S.K. Ayyaswamy, Y.B. Venkatakrishnan, On the harmonic index and the chromatic number of a graph. Discrete Appl. Math. 161, 2740–2744 (2013)
Z. Du, B. Zhou, N. Trinajstić, Minimum general sum-connectivity index of unicyclic graphs. J. Math. Chem. 48, 697–703 (2010)
Z. Du, B. Zhou, N. Trinajstić, Minimum sum-connectivity indices of trees and unicyclic graphs of a given matching number. J. Math. Chem. 47, 842–855 (2010)
C.S. Edwards, The largest vertex degree sum for a triangle in a graph. Bull. Lond. Math. Soc. 9, 203–208 (1977)
E. Estrada, L. Torres, L. Rodríguez, I. Gutman, An Atom-bond connectivity index: modelling the enthalpy of formation of alkanes. Indian J. Chem. 37A, 849–855 (1998)
S. Fajtlowicz, On conjectures of Graffiti-II. Congr. Numer. 60, 187–197 (1987)
O. Favaron, M. Mahéo, J.F. Saclé, Some eigenvalue properties in graphs (conjectures of Graffiti-II). Discrete Math. 111, 197–220 (1993)
I. Gutman, Relation between hyper-Wiener and Wiener index. Chem. Phys. Lett. 364, 352–356 (2002)
I. Gutman, B. Furtula, Vertex-degree-based molecular structure descriptors of benzenoid systems and phenylenes. J. Serb. Chem. Soc. 77, 1031–1036 (2012)
I. Gutman, B. Furtula, M. Ivanovic, Notes on trees with minimal atom-bond connectivity index. MATCH Commun. Math. Comput. Chem. 67, 467–482 (2012)
I. Gutman, W. Linert, I. Lukovits, Ž. Tomović, The multiplicative version of the Wiener index. J. Chem. Inf. Comput. Sci. 40, 113–116 (2000)
I. Gutman, J. Tošović, Testing the quality of molecular structure descriptors. Vertex–degreebased topological indices. J. Serb. Chem. Soc. 78(6), 805–810 (2013)
I. Gutman, N. Trinajstić, Graph theory and molecular orbitals. Total \(\pi \)–electron energy of alternant hydrocarbons. Chem. Phys. Lett. 17, 535–538 (1972)
I. Gutman, W. Yan, Y.-N. Yeh, B.-Y. Yang, Generalized Wiener indices of zigzagging pentachains. J. Math. Chem. 42(2), 103–117 (2007)
S. Klavzar, P. Zigert, I. Gutman, An algorithm for the calculation of the hyper-Wiener index of benzenoid hydrocarbons. Comput. Chem. 24, 229–233 (2000)
D.J. Klein, I. Gutman, Wiener-number-related sequences. J. Chem. Inf. Comput. Sci. 39, 534–536 (1999)
D.J. Klein, I. Lukovits, I. Gutman, On the definition of the hyper-Wiener index for cycle-containing structures. J. Chem. Inf. Comput. Sci. 35, 50–52 (1995)
A. Martínez-Pérez, J.M. Rodríguez, New lower bounds for the geometric-arithmetic index. MATCH Commun. Math. Comput. Chem. 79, 451–466 (2018)
Martínez-Pérez, A., Rodríguez, J.M.: New lower bounds for the first variable Zagreb index. arXiv:1806.02063 (2018)
A. Martínez-Pérez, J.M. Rodríguez, New lower bounds for the second variable Zagreb index. J. Comb. Optim. 36(1), 194–210 (2018)
M. Mogharrab, G.H. Fath-Tabar, Some bounds on \(GA_1\) index of graphs. MATCH Commun. Math. Comput. Chem. 65, 33–38 (2010)
M. Randić, On characterization of molecular branching. J. Am. Chem. Soc. 97, 6609–6615 (1975)
M. Randić, Novel graph theoretical approach to heteroatoms in QSAR. Chemom. Intell. Lab. Syst. 10, 213–227 (1991)
M. Randić, On computation of optimal parameters for multivariate analysis of structure-property relationship. J. Chem. Inf. Comput. Sci. 31, 970–980 (1991)
M. Randić, Novel molecular descriptor for structure-property studies. Chem. Phys. Lett. 211, 478–483 (1993)
M. Randić, D. Plavšić, N. Lerš, Variable connectivity index for cycle-containing structures. J. Chem. Inf. Comput. Sci. 41, 657–662 (2001)
J.M. Rodríguez, J.M. Sigarreta, On the geometric-arithmetic index. MATCH Commun. Math. Comput. Chem. 74, 103–120 (2015)
J.M. Rodríguez, J.M. Sigarreta, Spectral study of the geometric-arithmetic index. MATCH Commun. Math. Comput. Chem. 74, 121–135 (2015)
J.M. Rodríguez, J.M. Sigarreta, Spectral properties of geometric-arithmetic index. Appl. Math. Comput. 277, 142–153 (2016)
S.S. Tratch, M.I. Stankevich, N.S. Zefirov, Combinatorial models and algorithms in chemistry. The expanded wiener numbers—a novel topological index. J. Comput. Chem. 11, 899–908 (1990)
M. Vöge, A.J. Guttmann, I. Jensen, On the number of benzenoid hydrocarbons. J. Chem. Inf. Comput. Sci. 42, 456–466 (2002)
D. Vukičević, B. Furtula, Topological index based on the ratios of geometrical and arithmetical means of end-vertex degrees of edges. J. Math. Chem. 46, 1369–1376 (2009)
H. Wiener, Structural determination of paraffin boiling points. J. Am. Chem. Soc. 69, 17–20 (1947)
Y.S. Zhang, I. Gutman, J.G. Liu, Z.C. Mu, q-Analog of Wiener index. MATCH Commun. Math. Comput. Chem. 67, 347–356 (2012)
L. Zhong, The harmonic index for graphs. Appl. Math. Lett. 25, 561–566 (2012)
L. Zhong, K. Xu, Inequalities between vertex-degree-based topological Indices. MATCH Commun. Math. Comput. Chem. 71, 627–642 (2014)
B. Zhou, N. Trinajstić, On general sum-connectivity index. J. Math. Chem. 47, 210–218 (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Álvaro Martínez-Pérez was supported in part by a Grant from Ministerio de Economía y Competitividad (MTM 2015-63612P), Spain. José M. Rodríguez supported in part by two Grants from Ministerio de Economía y Competitividad , Agencia Estatal de Investigación (AEI) and Fondo Europeo de Desarrollo Regional (FEDER) (MTM2016-78227-C2-1-P and MTM2015-69323-REDT), Spain.
Rights and permissions
About this article
Cite this article
Martínez-Pérez, Á., Rodríguez, J.M. Some results on lower bounds for topological indices. J Math Chem 57, 1472–1495 (2019). https://doi.org/10.1007/s10910-018-00999-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10910-018-00999-7
Keywords
- Wiener index
- Generalized Wiener index
- Harmonic index
- General sum-connectivity index
- Geometric-arithmetic index