- Research
- Open access
- Published:
Bounds for the global cyclicity index of a general network via weighted majorization
Journal of Inequalities and Applications volume 2015, Article number: 113 (2015)
Abstract
In this paper we define a new graph-theoretic cyclicity index \(CW(G)\) as a natural generalization of the global cyclicity index \(C(G)\) when arbitrary resistances are allocated to each edge of an electrical network. Upper and lower bounds for \(CW(G)\) are then provided using a powerful technique, based on p-majorization, which extends our prior studies (Bianchi et al. in Discrete Appl. Math., 2014, doi:10.1016/j.dam.2014.10.037; Bianchi et al. in Math. Inequal. Appl. 16(2):329-347, 2013). These new results on weighted majorization are of interest in themselves and may be applied also in other scenarios.
1 Introduction
A simple connected undirected graph (or network) \(G=(V,E)\), where each edge is endowed with a unit resistance, is the basic model for molecules in mathematical chemistry: vertices represent atoms and edges represent bonds. Several graph measures based on distances, degrees, and graph entropies have been investigated in the recent literature to study a variety of physicochemical properties of these molecules [1, 2]. In the sequel, among the mathematical descriptors in the field, we focus on those indices based on electrical network theory like the Kirchhoff index [3–9] defined as
where \(R_{ij}\) is the effective resistance between vertices i and j, and the global cyclicity index [10] defined as
where \(m=|E|\).
When introducing a new topological index it is desirable to investigate its discriminative power (see [11] and [12]). In this regard, the global cyclicity index appears to be able to capture cyclicity meaningfully (see [10] for a thorough discussion on this matter and for a plethora of examples). Besides its appearance in the realm of mathematical chemistry, cyclicity is a key concept in other purely mathematical contexts, like measures of connectivity or complexity of graphs [13].
Through the majorization technique discussed in [14–16] and [17] significant bounds have been obtained by the authors for the Kirchhoff index as well as for some of its generalizations like the additive/multiplicative degree-Kirchhoff indices. Recently, using this powerful tool, Yang provided good bounds for the global cyclicity index [18].
One natural generalization of the molecular model described above is to endow the edges with arbitrary resistances. This is customary when studying random walks [19] but it has not received much attention in the area of molecular descriptors. We can single out the article [20] where they minimize the Kirchhoff index of a graph when there is a fixed total conductance to be allocated among the edges of the graph. Also, in references [21] and [22], they study the Kirchhoff index for networks where the effective resistances \(R_{ij}\) are made to depend on a single parameter λ and a set of weights on the vertices.
In this direction, we allow the edges of our graph to have arbitrary resistances \(r_{ij}\) and we consider the weighted global cyclicity index
as a natural extension of the global cyclicity index, which can be recovered when \(r_{ij}=1\) for all \((i,j) \in E\).
In order to tackle this new descriptor, we extend prior results of majorization into the realm of weighted majorization [23], and then we express the descriptor as an appropriate p-Schur-convex function to which the new technique can be applied. We believe that the new results on weighted majorization are of interest in themselves and may be of interest in other scenarios.
2 Notations and preliminaries
We recall in this section some notions on p-majorization (for further details see [23] and [24]).
We will denote by \([x_{1}^{\alpha_{1}}, x_{2}^{\alpha_{2}}, \ldots, x_{p}^{\alpha_{p}}]\) a vector in \(\mathbb{R}^{n}\) with \(\alpha_{i}\) components equal to \(x_{i}\), where \(\sum_{i=1}^{p} \alpha_{i}=n\). If \(\alpha_{i}=1\), we use for convenience \(x_{i}\) instead of \(x_{i}^{1}\), while \(x_{i}^{0}\) means that the component \(x_{i}\) is not present. Let \(\mathbf{e}^{\mathbf{j}}\), \(j=1,\ldots,n\), be the fundamental vectors of \(\mathbb{R}^{n}\). Recalling that the Hadamard product of two vectors \(\mathbf{x},\mathbf{y}\in \mathbb{R}^{n}\) is defined as follows:
it is easy to verify the following properties, where \(\langle\cdot ,\cdot \rangle\) denotes the inner product in \(\mathbb{R}^{n}\), \(\mathbf{s}^{\mathbf{j}}=[1^{j},0^{n-j}]\), with \(j=1,2,\ldots,n\) and \(\mathbf {v}^{\mathbf{j}}=[0^{j},1^{n-j}]\), with \(j=0, \ldots, n\):
-
(i)
\(\langle\mathbf{x}\circ \mathbf{y},\mathbf{z} \rangle= \langle \mathbf{x},\mathbf{y}\circ \mathbf{z} \rangle\),
-
(ii)
\(\langle\mathbf{s}^{\mathbf{h}},\mathbf{v}^{\mathbf{k}}\rangle =h-\min \{ h,k \} \),
-
(iii)
\(\mathbf{s}^{\mathbf{k}}\circ\mathbf{s}^{\mathbf {j}}=\mathbf{s}^{\mathbf{h}}\), \(h=\min \{ k,j \} \),
-
(iv)
\(\mathbf{v}^{\mathbf{k}}\circ\mathbf{s}^{\mathbf{j}}=\mathbf {s}^{\mathbf{j}}-\mathbf{s}^{\mathbf{h}} =\mathbf{v}^{\mathbf{h}}-\mathbf{v}^{\mathbf{j}}\), \(h=\min \{ k,j \} \).
Definition 1
Fix \(\mathbf{p}>\mathbf{0}\). Given two vectors \(\mathbf{y}, \mathbf{z}\in D=\{\mathbf{x}\in\mathbb{R}^{n}:x_{1} \geq x_{2}\geq\cdots\geq x_{n}\}\), the p-majorization order \(\mathbf{y}\trianglelefteq_{p} \mathbf{z}\) means:
and
Notice that for \(\mathbf{p}=\mathbf{s}^{\mathbf{n}}\) p-majorization reduces to the usual majorization. Thus in the sequel all our results entail as particular cases the results known for majorization (see [24, 25]).
Let \(\mathbf{x}^{\mathbf{\ast p}}(S)\) and \(\mathbf{x}_{\mathbf{\ast p }}(S)\) denote the maximal and the minimal elements of a subset \(S\subseteq \mathbb{R}^{n}\) with respect to the p-majorization order.
Given a positive real number a, let
By direct calculations we can show that the maximal and the minimal elements of \(\Sigma_{a}\) with respect to the p-majorization order are, respectively,
(see also [23]).
For the maximal element we have \(\langle\mathbf{p} \circ\mathbf{x}^{\mathbf{\ast p} } (\Sigma_{a}), \mathbf{s}^{\mathbf{j}} \rangle= a\), for all \(j=1, 2, \ldots, n\) and thus \(\langle\mathbf{p} \circ \mathbf{x}, \mathbf{s}^{\mathbf{j}} \rangle\le\langle \mathbf{p} \circ\mathbf{x}^{\mathbf{\ast p}} (\Sigma_{a}), \mathbf{s}^{\mathbf{j}} \rangle \) for all \(\mathbf{x} \in\Sigma_{a}\), \(j=1,2, \ldots,(n-1)\).
Now we prove that for each \(\mathbf{x}\in\Sigma_{a}\) and every \(k=1,2, \ldots,(n-1)\) we have
Indeed, if \(\frac{a}{\sum_{i=1}^{n} p_{i}} \sum_{i=1}^{k} p_{i} > \sum_{i=1}^{k}p_{i} x_{i}\), then
and rearranging the terms
Thus
and consequently \(x_{1} \ge x_{2} \ge\cdots\ge x_{k+1} > \frac{a}{\sum_{i=1}^{n} p_{i}}\). But this implies (1), a contradiction. Thus condition (1) holds, and it simply implies
for all \(\mathbf{x} \in\Sigma_{a}\), \(j=1,2, \ldots,(n-1)\).
We finally recall the notion of p-Schur-convex functions (see [23]). Let π be a permutation of \(\{1, \ldots n\}\) and \(\mathbf {x}^{\boldsymbol {\pi}}\) be the vector obtained exchanging the components of x according to π.
Given a fixed vector of positive components p, a function \(\phi(\cdot, \mathbf{p}): \mathbb{R}^{n} \longrightarrow\mathbb{R}\), is said to be p-Schur-convex if it preserves the p-majorization order, that is, if
The following result gives an important characterization of differentiable p-Schur-convex functions.
Theorem 2
(see [23])
Let \(\mathbf{p}>\mathbf{0}\) be fixed and \(\phi:\mathbb {R}^{n}\longrightarrow\mathbb{R}\) be a differentiable function satisfying (2). Then the function Ï• is p-Schur-convex if and only if, for all x,
Note that for \(\mathbf{p}=\mathbf{s}^{\mathbf{n}}\) we recover the classical notion of Schur-convex function (see [24]).
3 Some results on p-majorization
Now let us consider the subset of \(\Sigma_{a}\) given by
where \(\mathbf{m}= [ m_{1},m_{2},\ldots,m_{n} ] ^{T}\) and \(\mathbf {M}= [ M_{1},M_{2},\ldots,M_{n} ] ^{T}\) are two assigned vectors arranged in nonincreasing order with \(0\leq m_{i}\leq M_{i}\), for all \(i=1,\ldots,n\), and a is a positive real number such that
The existence of maximal and minimal elements of \(S_{a}\) with respect to the p-majorization are ensured by the compactness of the set \(S_{a}\) and by the closure of the upper and lower level sets:
For the sequel we are interested in computing the maximal element, with respect to the p-majorization order, of the set \(S_{a}\).
Theorem 3
Let \(k\geq0\) be the smallest integer such that
and \(\theta=\frac{a- \langle\mathbf{p} \circ \mathbf{M},\mathbf {s}^{\mathbf{k}} \rangle - \langle\mathbf{p} \circ \mathbf{m},\mathbf{v}^{\mathbf{k}+\mathbf{1}} \rangle }{p_{k+1}}\). Then
Proof
First of all we verify that \(\mathbf{x}^{\mathbf{\ast p}}(S_{a}) \in S_{a}\).
It easy to see that \(\langle \mathbf{p} \circ\mathbf{x}^{\mathbf{\ast p} }(S_{a}),\mathbf{s}^{\mathbf{n}} \rangle=a\) and that \(m_{i} \leq[\mathbf{x}^{\mathbf{\ast p}}(S_{a})]_{i} \leq M_{i}\) for \(i\neq k+1\). To prove that \(m_{k+1}\leq\mathbf{x}_{k+1}^{\mathbf{\ast p} }(S_{a}) \le M_{k+1}\), notice that from (6)
Now we show that \(\mathbf{x}\trianglelefteq_{p} \mathbf{x}^{\mathbf{\ast p} }(S_{a})\) for all \(\mathbf{x}\in S_{a}\). By property (i) it follows that
and by (iii) and (iv)
Thus, given a vector \(\mathbf{x}\in S_{a}\), for \(1\leq j\leq k\) we obtain
while for \((k+1)\leq j\leq(n-1)\), by (iii),
and the result follows. □
From this general result, the maximal element of particular subsets of \(S_{a}\) can be deduced.
Corollary 4
Let \(0\leq m< M\) and \(m\leq\frac{a}{\sum_{i=1}^{n}p_{i}}\leq M\). Given the set
we have
where k is the first integer such that
and \(\theta=\frac{a-M\sum_{i=1}^{k}p_{i} -m \sum_{i=k+2}^{n} p_{i} }{ p_{k+1}} \).
Remark 5
4 Effective resistance in general electric networks
Let \(G=(V,E)\) denote a simple connected network with n vertices and m edges. To each edge \((i,j) \in E\) we associate the resistance \(r_{ij}\) and the effective resistance \(R_{ij}\), which can be computed using Ohm’s law.
If we deal with electric network with \(r_{ij}=1\) the following relations are well known:
-
(1)
\(\sum_{(i,j) \in E} R_{ij} = n-1\) (Foster’s first formula);
-
(2)
\(\frac{2}{n} \le R_{ij} \le1\).
The inequality on the left hand side of (2) follows taking \(d_{i}=d_{j}=n-1\) in the general bound proved in [26]
where \((i,j) \in E\) and \(d_{i}\) denotes the degree of vertex i. The inequality on the right hand side follows noting that the effective resistance \(R_{ij}\) between two adjacent vertices i and j is equal to one if there is only one path connecting them, otherwise it is strictly less than one.
For a general electric network, assuming \(k \le r_{ij} \le K\), the previous relations generalize as follows:
- (1′):
-
\(\sum_{(i,j) \in E} \frac{R_{ij}}{r_{ij}} = n-1\) (generalized Foster’s first formula);
- (2′):
-
\(\frac{2k}{n} \le R_{ij}\le K\).
Relation (2′) can be obtained via electric arguments as we will show below. Indeed, we can prove a more general result that extends the lower bound (8).
Proposition 6
If \((i,j)\in E\) then
Proof
The monotonicity principle states that if the resistance of an individual resistor anywhere in the graph is increased (decreased) then the effective resistance between any two vertices in the graph can only increase (decrease) (see Doyle and Snell [19], p.67). Thus \(R_{ij}\) is greater than or equal to the effective resistance between i and j when the resistance of all the edges is reduced to k, and so we may assume that \(r_{st}=k\) for all \((s,t)\in E\).
Let us consider \((i,j)\in E\). If either \(d_{i}=1\) or \(d_{j}=1\) then \(R_{ij}=r_{ij} = k\) and (9) holds. So we take \(d_{i}\ge2\) and \(d_{j} \ge2\). Consider now all the endpoints of all the other \(d_{i}-1\) edges stemming out of i and all the \(d_{j}-1\) edges stemming out of j. Short all these. Then we get two edges in parallel between i and j: one with resistance k and the other with resistance \(\frac{k}{d_{i}-1} + \frac{k}{d_{j}-1}\). Solving this into a single resistor finishes the proof. □
Corollary 7
If \(d_{i}\le d\) for all \(i\in V\) then
for all \((i,j)\in E\).
Proof
By differentiating the functions \(F(x)=\frac{k(x+d_{j}-2)}{xd_{j}-1}\) and \(G(x)=\frac{k(d+x-2)}{dx-1}\), they are easily seen to be decreasing and thus
 □
Note that the bound (10) holds in particular if the graph is d-regular. Finally, since \(d_{i}\le n-1\) for all \(i\in V\), it follows that
5 Bounds for the global cyclicity index
In [10], by means of the concept of effective resistances, the global cyclicity index has been proposed:
Yang in [18] continued the study of this new cyclicity measure for connected graphs. Following Bianchi et al. [16, 25] and computing the extremal values of the Schur-convex function \(f(R_{ij})=\sum_{(i,j)\in E}\frac{1}{R_{ij}}\) on the set \(S= \{ R_{ij}\in \mathbb{R}^{m}:\sum_{(i,j)\in E}R_{ij}=n-1,\frac {2}{n}\leq R_{ij}\leq1 \} \), he obtained the following bounds for \(C(G)\):
where \((m-n+1)\) is the well-known cyclomatic number of a graph (see Theorems 3.13, 3.15 and Corollary 3.14 in [18]).
The aim of this section is to extend bounds (12) to the case of general networks where a resistance \(r_{ij}\), \(k \le r_{ij}\le K\), is associated to any edge. We show next how the weighted majorization technique proposed in Section 2 can be a fruitful tool to bound the weighted global cyclicity index, throughout the p-Schur-convex functions.
First of all, let us define the weighted global cyclicity index as a natural extension of the global cyclicity index (11) which can be recovered when \(r_{ij}=1\) for all \((i,j) \in E\):
If we define the variables \(x_{ij}=\frac{R_{ij}}{\sqrt{r_{ij}}}\) and the weights \(p_{ij}= \frac{1}{\sqrt{r_{ij}}}\), the weighted global cyclicity index can be written as a function of \(x_{ij}\) and \(p_{ij}\) as follows:
The choice of the variables and of the weights ensures that the function f is p-Schur-convex. Indeed, applying Theorem 2 we get
for all \((i,j), (i',j') \in E\).
Remark 8
Note that other possible choices of the variables and of the weights are not fruitful:
-
(1)
if we use as variables \(x_{ij}=R_{ij}\) and as weights \(p_{ij}= \frac{1}{r_{ij}}\) the function \(CW(G)\) is not p-Schur-convex;
-
(2)
if we use as variables \(x_{ij}=\frac{R_{ij}}{r_{ij}}\) and as weights \(p_{ij}=1\) the function \(CW(G)\) is not Schur-convex.
We can now state our main result.
Theorem 9
Let \(G=(V,E)\) a connected network with n vertices and m edges. Let \(r_{ij}\), \(k \le r_{ij} \le K\), be the resistances associated to any edge \((i,j) \in E\) and let
Then
Proof
Let \(e_{1}, e_{2}, \ldots,e_{m}\) be the edges of G. For simplicity denote the resistances and the effective resistances between the end vertices of the edge \(e_{i}\), as \(r_{i}\), and \(R_{i}\), respectively and let \(p_{i}= \frac{1}{\sqrt{r_{i}}} \). Moreover, let us assume, without loss of generality, that the variables \(x_{i}= \frac{R_{i}}{\sqrt{r_{i}}}\) are arranged in nonincreasing order: \(x_{1} \ge x_{2} \ge\cdots\ge x_{m}\).
Recalling that by Foster’s first formula
and that
let us now consider the set
The function \(CW(G)=f(x_{i},p_{i})\) is p-Schur-convex and thus its lower and upper bounds on S are attained at the minimum and maximum element of S with respect to the p-majorization order, respectively.
From Remark 5 we know that the minimal element of S is \(\mathbf{x}_{\mathbf{\ast p}}(S)= [(\frac{n-1}{\sum_{i=1}^{m} p_{i}} )]^{m}\). Thus the lower bound is
The maximal element \(\mathbf{x}^{\mathbf{\ast p}}\) of the set S can be computed with Corollary 4, yielding
where l is the first integer such that
and \(\theta= p_{l+1} \cdot (n-1 -\frac{K}{\sqrt{k}} \sum_{i=1}^{l} p_{i} - \frac{2k}{n \sqrt{K}} \sum_{i=l+2}^{m} p_{i} )\). Let \(D=\sum_{i=1}^{l} p_{i} \) and
From (14) easy computations show that
Moreover,
where
Let \(y=H-D\) and consider the function
The first derivative is
and the only nonnegative stationary point is
Assuming, without loss of generality that \(k \le1 \le K\), we can also be assured that \(\widehat{y} < p_{l+1}\). The stationary point \(\widehat {y}\) turns out to be a minimum. Thus the maximum value of the function h is attained at the extremum of the interval \([0, p_{l+1}]\). We have
We can get rid of \(p_{l+1}\) by using the bounds on the resistances. We obtain
The assertion easily follows from the bound
 □
Noting that \(\frac{m}{\sqrt{K}} \le C' \le\frac{m}{\sqrt{k}} \) and \(\frac{m}{K} \le C \le\frac{m}{k} \), we get the following corollary.
Corollary 10
Let \(G=(V,E)\) a connected network with n vertices and m edges. Let \(r_{ij}\), \(k \le r_{ij} \le K\), be the resistances associated to any edge. Then
where \(C'' = \max \{\frac{nK}{2k}, \frac{\sqrt{k}}{\sqrt{K}} + \frac{n \sqrt{K}}{2k\sqrt{k}} - \frac{1}{K} \}\).
If in inequality (15) we set \(k=K=1\), that is, \(r_{ij}= 1\) for all \((i,j) \in E\), we get
i.e. the bounds provided by Yang in [18], Theorem 3.13 and Corollary 3.14 for the global cyclicity index.
6 Summary and conclusion
In this article we defined the new weighted global cyclicity index that applies to graphs whose edges are endowed with arbitrary resistances and generalizes the global cyclicity index, introduced by Klein and Ivanciuc, which applies only to graphs whose edges are endowed with unit resistances. Through the use of p-majorization we provided upper and lower bounds for the new index that coincide with those given by Yang in the particular case of unit resistances. The maximal results obtained through p-majorization are of interest in themselves and may be applicable in other contexts.
References
Dehmer, M, Emmert-Streib, F: Networks for systems biology: conceptual connection of data and function. IET Syst. Biol. 5(3), 185-207 (2011)
Todeschini, R, Consonni, V: Handbook of Molecular Descriptor. Wiley, Weinheim (2000)
Gutman, I, Mohar, B: The quasi-Wiener and the Kirchhoff indices coincide. J. Chem. Inf. Comput. Sci. 36, 982-985 (1996)
Klein, DJ, Randić, M: Resistance distance. J. Math. Chem. 12, 81 (1993)
Palacios, JL, Renom, JM: Bounds for the Kirchhoff index of regular graphs via the spectra of their random walks. Int. J. Quant. Chem. 110, 1637-1641 (2010)
Palacios, JL, Renom, JM: Broder and Karlin’s formula for hitting times and the Kirchhoff index. Int. J. Quant. Chem. 111, 35-39 (2011)
Zhou, B, Trinajstić, N: A note on Kirchhoff index. Chem. Phys. Lett. 455, 120-123 (2008)
Zhou, B, Trinajstić, N: On resistance-distance and Kirchhoff index. J. Math. Chem. 46, 283-289 (2009)
Zhu, HY, Klein, DJ, Lukovits, I: Extensions of the Wiener number. J. Chem. Inf. Comput. Sci. 36, 420-428 (1996)
Klein, DJ, Ivanciuc, O: Graph cyclicity, excess conductance, and resistance deficit. J. Math. Chem. 30, 271-287 (2001)
Dehmer, M, Emmert-Streib, F: Information indices with high discriminative power for graphs. PLoS ONE 7(2), e31214 (2011)
Gutman, I: Degree-based topological indices. Croat. Chem. Acta 86, 351-361 (2013)
Tutte, W: Connectivity in Graphs. University of Toronto Press, Toronto (1966)
Bianchi, M, Cornaro, A, Palacios, JL, Torriero, A: Bounds for the Kirchhoff index via majorization techniques. J. Math. Chem. 51(2), 569-587 (2013)
Bianchi, M, Cornaro, A, Palacios, JL, Torriero, A: New upper and lower bounds for the additive degree-Kirchhoff index. Croat. Chem. Acta 86(4), 363-370 (2013)
Bianchi, M, Cornaro, A, Torriero, A: A majorization method for localizing graph topological indices. Discrete Appl. Math. 161, 2731-2739 (2013)
Bianchi, M, Cornaro, A, Palacios, JL, Torriero, A: Bounding the sum of powers of normalized Laplacian eigenvalues of graphs through majorization methods. MATCH Commun. Math. Comput. Chem. 70(2), 707-716 (2013)
Yang, Y: On a new cyclicity measure of graphs - the global cyclicity index. Discrete Appl. Math. 172, 88-97 (2014)
Doyle, GP, Snell, JL: Random Walks and Electrical Networks. The Mathematical Association of America, Washington (1984)
Ghosh, A, Boyd, S, Saberi, A: Minimizing effective resistances of a graph. SIAM Rev. 50, 37-66 (2008)
Arauz, C: The Kirchhoff indexes of some composite networks. Discrete Appl. Math. 160, 1429-1440 (2012)
Bendito, E, Carmona, A, Encinas, AM, Gesto, JM, Mitjana, M: Kirchhoff indexes of a network. Linear Algebra Appl. 1432, 2278-2292 (2010)
Cheng, KW: Majorization: its extensions and the preservations theorems. Technical report, Department of Statistics, Stanford University, California (1977)
Marshall, AW, Olkin, I, Arnold, B: Inequalities: Theory of Majorization and Its Applications. Springer, Berlin (2011)
Bianchi, M, Cornaro, A, Torriero, A: Majorization under constraints and bounds of the second Zagreb index. Math. Inequal. Appl. 16(2), 329-347 (2013)
Palacios, JL, Renom, JM: Another look at the degree-Kirchhoff index. Int. J. Quant. Chem. 111, 3453-3455 (2011)
Author information
Authors and Affiliations
Corresponding author
Additional information
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.
Rights and permissions
Open Access This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly credited.
About this article
Cite this article
Bianchi, M., Cornaro, A., Palacios, J.L. et al. Bounds for the global cyclicity index of a general network via weighted majorization. J Inequal Appl 2015, 113 (2015). https://doi.org/10.1186/s13660-015-0624-5
Received:
Accepted:
Published:
DOI: https://doi.org/10.1186/s13660-015-0624-5
Comments
View archived comments (1)