Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-26T20:57:04.971Z Has data issue: false hasContentIssue false
  • English
  • Français

SOME NEW LOWER BOUNDS FOR THE KIRCHHOFF INDEX OF A GRAPH

Part of: Graph theory

Published online by Cambridge University Press:  04 October 2017

I. MILOVANOVIĆ Open the ORCID record for I. MILOVANOVIĆ [Opens in a new window] ,
M. MATEJIĆ ,
E. GLOGIĆ  and
E. MILOVANOVIĆ
I. MILOVANOVIĆ*
Affiliation:
Faculty of Electronic Engineering, Niš, Serbia email [email protected]
M. MATEJIĆ
Affiliation:
Faculty of Electronic Engineering, Niš, Serbia email [email protected]
E. GLOGIĆ
Affiliation:
State University of Novi Pazar, Novi Pazar, Serbia email [email protected]
E. MILOVANOVIĆ
Affiliation:
Faculty of Electronic Engineering, Niš, Serbia email [email protected]
*
✉[email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let $G$ be a simple connected graph with $n$ vertices and $m$ edges and $d_{1}\geq d_{2}\geq \cdots \geq d_{n}>0$ its sequence of vertex degrees. If $\unicode[STIX]{x1D707}_{1}\geq \unicode[STIX]{x1D707}_{2}\geq \cdots \geq \unicode[STIX]{x1D707}_{n-1}>\unicode[STIX]{x1D707}_{n}=0$ are the Laplacian eigenvalues of $G$, then the Kirchhoff index of $G$ is $\mathit{Kf}(G)=n\sum _{i=1}^{n-1}\unicode[STIX]{x1D707}_{i}^{-1}$. We prove some new lower bounds for $\mathit{Kf}(G)$ in terms of some of the parameters $\unicode[STIX]{x1D6E5}=d_{1}$, $\unicode[STIX]{x1D6E5}_{2}=d_{2}$, $\unicode[STIX]{x1D6E5}_{3}=d_{3}$, $\unicode[STIX]{x1D6FF}=d_{n}$, $\unicode[STIX]{x1D6FF}_{2}=d_{n-1}$ and the topological index $\mathit{NK}=\prod _{i=1}^{n}d_{i}$.

Keywords

Kirchhoff indexLaplacian eigenvalues (of a graph)vertex degree

MSC classification

Primary: 05C12: Distance in graphs
Secondary: 05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 97 , Issue 1 , February 2018 , pp. 1 - 10
Copyright
© 2017 Australian Mathematical Publishing Association Inc. 

Footnotes

This work was supported by the Serbian Ministry for Education, Science and Technological Development.

References

Bianchi, M., Cornaro, A. and Torriero, A., ‘A majorization method for localizing graph topological indices’, Discrete Appl. Math. 161 (2013), 2731–2739.Google Scholar
Chen, X. and Das, K. C., ‘Characterization of extremal graphs from Laplacian eigenvalues and the sum of powers of the Laplacian eigenvalues of graphs’, Discrete Math. 338 (2015), 1252–1263.Google Scholar
Das, K. C., ‘On the Kirchhoff index of graphs’, Z. Naturforsch. 68a (2013), 531–538.Google Scholar
Das, K. C., Güngör, A. D. and Çevik, A. S., ‘On Kirchhoff index and resistance-distance energy of a graph’, MATCH Commun. Math. Comput. Chem. 67 (2012), 541–556.Google Scholar
Gutman, I. and Ghorbani, M., ‘Some properties of the Narumi–Katayama index’, Appl. Math. Lett. 25 (2012), 1435–1438.CrossRefGoogle Scholar
Gutman, I. and Mohar, B., ‘The quasi-Wiener and the Kirchhoff indices coincide’, J. Chem. Inf. Comput. Sci. 36 (1996), 982–985.Google Scholar
Hayashi, T., ‘On some inequalities’, Rend. Circ. Mat. Palermo 44 (1920), 336–340.CrossRefGoogle Scholar
Klein, D. J. and Randić, M., ‘Resistance distance’, J. Math. Chem. 12 (1993), 81–95.Google Scholar
Klein, D. J. and Rosenfeld, V. R., ‘The degree-product index of Narumi and Katayama’, MATCH Commun. Math. Comput. Chem. 64 (2010), 607–618.Google Scholar
Kober, H., ‘On the arithmetic and geometric means and on Hölder’s inequality’, Proc. Amer. Math. Soc. 9 (1958), 452–459.Google Scholar
Liu, J. B., Pan, X. F., Cao, J. and Hu, F. T., ‘The Kirchhoff index of some combinatorial networks’, Discrete Dyn. Nat. Sci. (2015), Article ID 340793.Google Scholar
Milovanović, I. Ž. and Milovanović, E. I., ‘On some lower bounds of the Kirchhoff index’, MATCH Commun. Math. Comput. Chem. 78 (2017), 169–180.Google Scholar
Milovanović, I. Ž. and Milovanović, E. I., ‘Bounds of Kirchhoff and degree Kirchhoff indices’, in: Bounds in Chemical Graph Theory—Mainstreams, Mathematical Chemistry Monographs, MCM 20 (eds. Gutman, I., Furtula, B., Das, K. C., Milovanović, E. and Milovanović, I.) (University of Kragujevac, Kragujevac, 2017), 93–119.Google Scholar
Mitrinović, D. S. and Vasić, P. M., ‘History, variations and generalisations of the Čebyšev inequality and the question of some priorities’, Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. Fiz. 461–497 (1974), 1–30.Google Scholar
Narumi, H. and Katayama, M., ‘Simple topological index. A newly devised index characterizing the topological nature of structural isomers of saturated hydrocarbons’, Mem. Fac. Eng. Hokkaido Univ. 16 (1984), 209–214.Google Scholar
Palacios, J. L., ‘Some additional bounds for the Kirchhoff index’, MATCH Commun. Math. Comput. Chem. 75 (2016), 365–372.Google Scholar
Palacios, J. L. and Renom, J. M., ‘Broder and Karlin’s formula for hitting times and the Kirchhoff index’, Int. J. Quantum Chem. 111 (2011), 35–39.Google Scholar
Reti, T. and Gutman, I., ‘Relations between ordinary and multiplicative Zagreb indices’, Bull. Int. Math. Virtual Inst. 2 (2012), 133–140.Google Scholar
Szőkefalvi Nagy, J., ‘Über algebraische Gleichungen mit lauter reellen Wurzeln’, Jahresber. Deutsch. Math.-Verein. 27 (1918), 37–43.Google Scholar
Wiener, H., ‘Structural determination of paraffin boiling points’, J. Amer. Chem. Soc. 69 (1947), 17–20.Google Scholar
Zhou, B., Gutman, I. and Aleksić, T., ‘A note on the Laplacian energy of graphs’, MATCH Commun. Math. Comput. Chem. 60 (2008), 441–446.Google Scholar
Zhou, B. and Trinajstić, N., ‘A note on Kirchhoff index’, Chem. Phys. Lett. 455 (2008), 120–123.Google Scholar
Zhou, B. and Trinajstić, N., ‘Mathematical properties of molecular descriptors based on distances’, Croat. Chem. Acta 83 (2010), 227–242.Google Scholar