Milovanovic, I., Glogic, E., Matejic, M., Milovanovic, E. (2019). On relation between the Kirchhoff index and number of spanning trees of graph. Communications in Combinatorics and Optimization, (), -. doi: 10.22049/cco.2019.26270.1088

Igor Milovanovic; Edin Glogic; Marjan Matejic; Emina Milovanovic. "On relation between the Kirchhoff index and number of spanning trees of graph". Communications in Combinatorics and Optimization, , , 2019, -. doi: 10.22049/cco.2019.26270.1088

Milovanovic, I., Glogic, E., Matejic, M., Milovanovic, E. (2019). 'On relation between the Kirchhoff index and number of spanning trees of graph', Communications in Combinatorics and Optimization, (), pp. -. doi: 10.22049/cco.2019.26270.1088

Milovanovic, I., Glogic, E., Matejic, M., Milovanovic, E. On relation between the Kirchhoff index and number of spanning trees of graph. Communications in Combinatorics and Optimization, 2019; (): -. doi: 10.22049/cco.2019.26270.1088

On relation between the Kirchhoff index and number of spanning trees of graph

^{1}Faculty of Electronic Engineering, Nis, Serbia

^{2}State University of Novi Pazar, Novi Pazar, Serbia

^{3}Faculty of Electronic Engineering, Nis, Srbia

Abstract

Let $G=(V,E)$, $V={1,2,ldots,n}$, $E={e_1,e_2,ldots,e_m}$, be a simple connected graph, with sequence of vertex degrees $Delta =d_1geq d_2geqcdotsgeq d_n=delta >0$ and Laplacian eigenvalues $mu_1geq mu_2geqcdotsgeqmu_{n-1}>mu_n=0$. Denote by $Kf(G)=nsum_{i=1}^{n-1} frac{1}{mu_i}$ and $t=t(G)=frac 1n prod_{i=1}^{n-1} mu_i$ the Kirchhoff index and number of spanning trees of $G$, respectively. In this paper we determine several lower bounds for $Kf(G)$ depending on $t(G)$ and some of the graph parameters $n$, $m$, or $Delta$.