Open Journal of Discrete Applied Mathematics

Vol. 2 (2019), Issue 3, pp. 1 – 6
ISSN: 2617-9687 (Online) 2617-9679 (Print)
DOI: 10.30538/psrp-odam2019.0017

A note on the Kirchhoff index of graphs

Marjan M. Matejić, Emina I. Milovanović, Predrag D. Milošević, Igor Ž. Milovanović$^1$
Faculty of Electronic Engineering, Beogradska 14, P. O. Box 73, 18000 Niš, Serbia.; (M.M.M & E.I.M & P.D.M & I.Ž.M)
$^{1}$Corresponding Author: igor@elfak.ni.ac.rs; Tel.: +381529603

Copyright © 2019 Marjan M. Matejić, Emina I. Milovanović, Predrag D. Milošević, Igor Ž. Milovanović. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Received: July 19, 2019 – Accepted: August 22, 2019 – Published: October 6, 2019

Abstract

Let $G$ be a simple connected graph with $n$ vertices, $m$ edges, and a sequence of vertex degrees $\Delta=d_1\geq d_2\geq\cdots\geq d_n=\delta >0$. Denote by $\mu_1\geq \mu_2\geq\cdots\geq \mu_{n-1}>\mu_n=0$ the Laplacian eigenvalues of $G$. The Kirchhoff index of $G$ is defined as $Kf(G)=n\sum_{i=1}^{n-1} \frac{1}{\mu_i}$. A couple of new lower bounds for $Kf(G)$ that depend on $n$, $m$, $\Delta$ and some other graph invariants are obtained.

Keywords:

Kirchhoff index, Zagreb indices, forgotten index.

1. Introduction

Let $G=(V,E)$, $V=\{v_1,v_2,\ldots,v_n\}$, be a simple connected graph with $n$ vertices, $m$ edges and let $\Delta=d_1\geq d_2\geq\cdots\geq d_n=\delta >0$, $d_i=d(v_i)$, be a sequence of vertex degrees of $G$. If vertices $v_i$ and $v_j$ are adjacent we write $v_i\sim v_j$ or, for brevity, $i\sim j$.

In graph theory, an invariant is a property of graphs that depends only on their abstract structure, not on the labeling of vertices or edges. Such quantities are also referred to as topological indices. The topological indices are an important class of molecular structure descriptors used for quantifying information on molecules. Many of them are defined as simple functions of the degrees of the vertices of (molecular) graph (see e.g. [1, 2, 3]). Historically, the first vertex-degree-based (VDB) structure descriptors were the graph invariants that are nowadays called Zagreb indices. The first and the second Zagreb index, $M_1$ and $M_2$, are defined as $$ M_1(G)=\sum_{i=1}^n d_i^2\,, $$ and $$ M_2(G)=\sum_{i\sim j} d_id_j\,. $$ The quantity $M_1$ was first time considered in 1972 [4], whereas $M_2$ in 1975 [5]. These were named Zagreb group indices [6] (in view of the fact that the authors of [4, 5] were members of the "Rudjer Bov sković" Institute in Zagreb, Croatia). Eventually, the name was shortened into first Zagreb index and second Zagreb index [7]. In [4] another topological index defined as sum of cubes of vertex degrees, that is $$ F(G)=\sum_{i=1}^n d_i^3\,, $$ was encountered. However, for the unknown reasons, it did not attracted any attention until 2015 when it was reinvented in [8] and named the {\it forgotten topological index}. % Details of the theory and applications of these topological indices can be found, for example, in [9, 10]. In [11] Fajtlowicz defined a topological index called the inverse degree, $ID(G)$, as $$ ID(G)=\sum_{i=1}^n \frac{1}{d_i}. $$ Here we are interested in a graph invariant called the Kirchhoff index, which was introduced by Klein and Randić in [12]. It is defined as $$ Kf(G)=\sum_{i< j}r_{ij}, $$ where $r_{ij}$ is the resistance distance between the vertices $v_i$ and $v_j$, i.e. $r_{ij}$ is equal to the resistance between equivalent points on an associated electrical network obtained by replacing each edge of $G$ by a unit (1 ohm) resistor. The Kirchhoff index has a very nice purely mathematical interpretation. Namely, in [13] and [14] it was demonstrated that the Kirchhoff index of a connected graph can also be represented as $$ Kf(G)=n\sum_{i=1}^{n-1} \frac{1}{\mu_i}, $$ where $\mu_1\geq \mu_2\geq\cdots\geq\mu_{n-1}>\mu_n=0$ are the Laplacian eigenvalues of $G$. In this paper we obtain new lower bounds for $Kf(G)$ which depend on some of the graph structural parameters and above mentioned topological indices. Before we proceed, let us define one special class of $d$-regular graphs $\Gamma_d$ [15]. Let $N(i)$ be a set of all neighbors of vertex $i$, i.e. $N(i)=\{k\, |\, k\in V,\, k\sim i\}$, and $d(i,j)$ the distance between vertices $i$ and $j$. Denote by $\Gamma_d$ a set of all $d$-regular graphs, $1\leq d\leq n-1$, with diameter $D=2$ and $|N(i)\cap N(j)|=d$ for $i\nsim j$.

2. Preliminaries

In this section we recall some results from the literature which are needed for the subsequent considerations.

Lemma 1. [16] Let $p=(p_i)$, $i=1,2,\ldots,n$, be a nonnegative real number sequence and $a=(a_i)$, $i=1,2,\ldots,n$, a positive real number sequence. Then for any real $r$, such that $r\geq 1$ or $r\leq 0$, holds

\begin{equation} \label{2.1} \left(\sum_{i=1}^n p_i\right)^{r-1}\sum_{i=1}^n p_ia_i^{r} \ge \left(\sum_{i=1}^n p_ia_i\right)^{r}. \end{equation}

(1)

If $0\le r\le 1$, then the sense of (1) reverses. Equality holds if and only if either $r=0$, or $r=1$, or $a_1=a_2=\cdots=a_n$, or $p_1=p_2=\cdots=p_t=0$ and $a_{t+1}=a_{t+2}=\cdots=a_n$, for some $t$, $1\leq t\leq n-1$.

Lemma 2. [17] Let $G$ be a simple connected graph with $n\ge 2$ vertices. Then

\begin{equation} \label{2.2} Kf(G)\geq -1+(n-1)ID(G). \end{equation}

(2)

Equality holds if and only if either $G\cong K_n$, or $G\cong K_{t,n-t}$, $1\leq t\leq\lfloor\frac{n}{2}\rfloor$, or $G\in \Gamma_d$.

3. Main results

In the next theorem we determine a new lower bound for $Kf(G)$ in terms of the invariant $M_1(G)$ and graph parameters $n$, $m$ and $\Delta$.

Theorem 3. Let $G$ be a simple connected graph with $n\ge 2$ vertices and $m$ edges. If $G$ is $d$-regular graph, $1\le d\le n-1$, then

\begin{equation} \label{3.1} Kf(G)\geq \frac{n(n-1)-d}{d}. \end{equation}

(3)

Otherwise

\begin{equation} \label{3.2} Kf(G)\geq \frac{n(n-1)-\Delta}{\Delta}+\frac{(n-1)(n\Delta-2m)^2}{\Delta(2m\Delta-M_1(G))}. \end{equation}

(4)

Equality in (3) holds if and only if $G\cong K_n$, or $G\in \Gamma_d$. Equality in (4) holds if and only if $G\cong K_{\Delta,n-\Delta}$.

Proof. If $G$ is $d$-regular graph, $1\le d\le n-1$, then $$ ID(G)=\frac{n}{d}. $$ From the above and (2) we arrive at (3). For $r=2$, $p_i:=\frac{\Delta}{d_i}-1$, $a_i:=d_i$, $i=1,2,\ldots,n$, the inequality (1) becomes $$ \sum_{i=1}^{n} \left(\frac{\Delta}{d_i}-1 \right)\sum_{i=1}^{n} (\Delta-d_i)d_i\geq \left(\sum_{i=1}^{n} (\Delta-d_i)\right)^{2}, $$ that is

\begin{equation} \label{3.3} (\Delta ID(G)-n)(2m\Delta-M_1(G))\geq (n\Delta-2m)^2. \end{equation}

(5)

If $G$ is $d$-regular graph, $1\le d\le n-1$, then $2m\Delta-M_1(G)=0$. Therefore, we assume that $G$ is not $d$-regular graph, $1\le d\le n-1$. Then, according to (5) we have $$ ID(G)\ge \frac{n}{\Delta}+\frac{(n\Delta-2m)^2}{\Delta(2m\Delta-M_1(G))}. $$ The inequality (4) is obtained from the above and (2). The inequality (3) was proven in [18] with equality holding if and only if $G\cong K_n$ or $G\in \Gamma_d$. Since $G$ is not $d$-regular graph, $1\le d\le n-1$, then equality in (5) is attained if and only if $\Delta=d_1=d_2=\cdots=d_t>d_{t+1}=\cdots=d_n$, for some $t$, $2\leq t\leq n-1$, which implies that equality in (4) holds if and only if $G\cong K_{\Delta,n-\Delta}$.

Remark 1. According to (4) follows $$ Kf(G)\geq \dfrac{n(n-1)-\Delta}{\Delta}, $$ which was proven in [15].

Corollary 4. Let $G$ be a simple connected graph with $n\ge 2$ vertices and $m$ edges. If $G\cong K_n$, then $$ Kf(G)=n-1. $$ Otherwise

\begin{equation} \label{3.4} Kf(G)\geq n-1+\frac{(n(n-1)-2m)^2}{2m(n-1)-M_1(G)}. \end{equation}

(6)

Equality holds if and only if $G\cong K_{1,n-1}$, or $G\in \Gamma_d$.

Proof. For $r=2$, $p_i:=\frac{n-1}{d_i}-1$, $a_i:=d_i$, $i=1,2,\ldots,n$, the inequality (1) transforms into $$ \sum_{i=1}^{n} \left(\frac{n-1}{d_i}-1 \right)\sum_{i=1}^{n} (n-1-d_i)d_i\geq \left(\sum_{i=1}^{n} (n-1-d_i)\right)^{2}, $$ that is

\begin{equation} \label{3.5} ((n-1) ID(G)-n)(2m(n-1)-M_1(G))\geq (n(n-1)-2m)^2. \end{equation}

(7)

If $G\cong K_n$, then $Kf(G)=n-1$ and $2m(n-1)-M_1(G)=0$. If $G\ncong K_n$, from (7) we obtain $$ (n-1)ID(G)\ge n+\frac{(n(n-1)-2m)^2}{2m(n-1)-M_1(G)}. $$ The inequality (6) follows from the above and (2). Equality in (7), $G\ncong K_n$, is attained if and only if $\Delta=d_1=d_2=\cdots=d_n\ne n-1$, or $n-1=\Delta=d_1=d_2=\cdots=d_t>d_{t+1}=\cdots=d_n$, for some $t$, $1\leq t\leq n-1$. This implies that equality in (6) holds if and only if $G\cong K_{1,n-1}$, or $G\in \Gamma_d$.

Remark 2. In [19] the following was proven

\begin{equation} \label{3.5a} Kf(G)\geq \frac{2mn(n-1)(n-2)}{4m^2-M_1(G)-2m}, \end{equation}

(8)

with equality holding if and only if $G\cong K_n$. We have performed testing on a large number of connected graphs, but could not find any graph for which the inequality (8) is stronger than (6).

Corollary 5. Let $G$ be a simple connected graph with $n\ge 2$ vertices and $m$ edges. Then

\begin{equation} \label{3.6} Kf(G)\geq \dfrac{n^2(n-1)-2m}{2m}. \end{equation}

(9)

Equality holds if and only if $G\cong K_n$, or $G\in \Gamma_d$.

Proof. The inequality (9) is obtained according to (6) and inequality $$ M_1(G)\ge \frac{4m^2}{n}, $$ which was proven in [20] (see also [21, 22]). The inequality (9) was proven in [23] (see also [18]).

The proof of the next theorem is fully analogous to that of the Theorem 3, hence omitted.

Theorem 6. Let $G$ be a simple connected graph with $n\ge 2$ vertices and $m$ edges. If $G$ is $d$-regular graph, $1\le d\le n-1$, then the inequality (3) holds. Otherwise

\begin{equation} \label{3.7} Kf(G)\geq \frac{n(n-1)-\Delta}{\Delta}+\frac{(n-1)(n\Delta-2m)^{3/2}}{\Delta(\Delta M_1(G)-F(G))^{1/2}}. \end{equation}

(10)

Equality in (10) holds if and only if $G\cong K_{\Delta,n-\Delta}$.

Corollary 7. Let $G$ be a simple connected graph with $n\ge 2$ vertices and $m$ edges. If $G\cong K_n$, then $$ Kf(G)=n-1. $$ If $G\ncong K_n$, then

\begin{equation} \label{3.8} Kf(G)\geq n-1+\frac{(n(n-1)-2m)^{3/2}}{((n-1)M_1(G)-F(G))^{1/2}}. \end{equation}

(11)

Equality holds if and only if $G\cong K_{1,n-1}$, or $G\in \Gamma_d$.

Corollary 12. Let $G$ be a simple connected graph with $n\ge 2$ vertices and $m$ edges. If $G\cong K_n$, then $$ Kf(G)=n-1. $$ If $G\ncong K_n$, then

\begin{equation} \label{3.9} Kf(G)\geq n-1+\frac{(n(n-1)-2m)^{3/2}}{((n-1)M_1(G)-2M_2(G))^{1/2}}. \end{equation}

(13)

Equality holds if and only if $G\in \Gamma_d$.

Proof. The inequality (12) is obtained from (11) and inequality $F(G)\ge 2M_2(G)$.

Remark 3. In [24] a vertex--degree--based topological index called the Lanzhou index, $Lz(G)$, is defined as $$ Lz(G)=\sum_{i=1}^n (n-1-d_i)d_i^2. $$ According to (11) the following relation between topological indices $Kf(G)$ and $Lz(G)$ follows $$ (Kf(G)-n+1)Lz(G)^{1/2}\geq (n(n-1)-2m)^{3/2}, $$ with equality holding if and only if $G\cong K_n$, or $G\cong K_{1,n-1}$, or $G\in \Gamma_d$.

Author Contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Conflicts of Interest:

The authors declare no conflict of interest.

References

Todeschini, R., & Consonni, V. (2008). Handbook of molecular descriptors (Vol. 11). John Wiley & Sons. [Google Scholor]
Vukičević, D. (2010). Bond additive modeling 2. Mathematical properties of max-min rodeg index. Croatica chemica acta, 83(3), 261-273. [Google Scholor]
Vukičević, D., & Gašperov, M. (2010). Bond additive modeling 1. Adriatic indices. Croatica chemica acta, 83(3), 243-260. [Google Scholor]
Gutman, I., & Trinajstić, N. (1972). Graph theory and molecular orbitals. Total $\phi$-electron energy of alternant hydrocarbons. Chemical Physics Letters, 17(4), 535-538. [Google Scholor]
Gutman, I., Ruščić, B., Trinajstić, N., & Wilcox Jr, C. F. (1975). Graph theory and molecular orbitals. XII. Acyclic polyenes. The Journal of Chemical Physics, 62(9), 3399-3405. [Google Scholor]
Balaban, A. T., Motoc, I., Bonchev, D., & Mekenyan, O. (1983). Topological indices for structure-activity correlations. In Steric effects in drug design(pp. 21-55). Springer, Berlin, Heidelberg.[Google Scholor]
Gutman, I. (2014). On the origin of two degree–based topological indices. Bulletin (Académie serbe des sciences et des arts. Classe des sciences mathématiques et naturelles. Sciences mathématiques), (39), 39-52. [Google Scholor]
Furtula, B., & Gutman, I. (2015). A forgotten topological index. Journal of Mathematical Chemistry, 53(4), 1184-1190.[Google Scholor]
Borovicanin, B., Das, K. C., Furtula, B., & Gutman, I. (2017). Zagreb indices: Bounds and extremal graphs. Bounds in Chemical Graph Theory–Basics, Univ. Kragujevac, Kragujevac, 67-153. [Google Scholor]
Borovicanin, B., Das, K. C., Furtula, B., & Gutman, I. (2017). Bounds for Zagreb indices. MATCH-Communications in Mathematical and in Computer Chemistry, 78(1), 17-100. [Google Scholor]
Fajtlowicz, S. (1987). On conjectures of Graffiti-II. Congr. Numer, 60, 187-197. [Google Scholor]
Klein, D. J., & Randić, M. (1993). Resistance distance. Journal of mathematical chemistry, 12(1), 81-95. [Google Scholor]
Gutman, I., & Mohar, B. (1996). The quasi-Wiener and the Kirchhoff indices coincide. Journal of Chemical Information and Computer Sciences, 36(5), 982-985.[Google Scholor]
Zhu, H. Y., Klein, D. J., & Lukovits, I. (1996). Extensions of the Wiener number. Journal of Chemical Information and Computer Sciences, 36(3), 420-428. [Google Scholor]
Palacios, J. L. (2016). Some additional bounds for the Kirchhoff index. MATCH-Communications in Mathematical and in Computer Chemistry, 75(2), 365-372. [Google Scholor]
Mitrinovic, D. S., Pecaric, J., & Fink, A. M. (2013). Classical and new inequalities in analysis (Vol. 61). Springer Science & Business Media.[Google Scholor]
Zhou, B., & Trinajstić, N. (2008). A note on Kirchhoff index. Chemical Physics Letters, 455(1-3), 120-123. [Google Scholor]
Milovanovic, I. Z., & Milovanovic, E. I. Bounds of Kirchhoff and degree Kirchhoff indices. Bounds in Chemical Graph Theory–Mainstreams (I. Gutman, B. Furtula, KC Das, E. Milovanovic, I. Milovanovic (Eds.)) Mathematical Chemistry Monographs, MCM, 20, 93-119. [Google Scholor]
Das, K. C. (2013). On the Kirchhoff index of graphs. Zeitschrift für Naturforschung A, 68(8-9), 531-538.[Google Scholor]
Edwards, C. S. (1977). The largest vertex degree sum for a triangle in a graph. Bulletin of the London Mathematical Society, 9(2), 203-208. [Google Scholor]
Ilić, A., & Stevanović, D. (2011). On comparing Zagreb indices, MATCH-Communications in Mathematical and in Computer Chemistry 62, 681--687. [Google Scholor]
Yoon, Y. S., & Kim, J. K. (2006). A relationship between bounds on the sum of squares of degrees of a graph. Journal of Applied Mathematics and Computing, 21(1-2), 233-238.[Google Scholor]
Milovanovic, I. Z., & Milovanovic, E. I. (2017). On some lower bounds of the Kirchhoff index. MATCH-Communications in Mathematical and in Computer Chemistry, 78, 169-180. [Google Scholor]
Vukicevic, D., Li, Q., Sedlar, J., & Došlic, T. (2018). Lanzhou index. MATCH-Communications in Mathematical and in Computer Chemistry, 80, 863--876. [Google Scholor]