Czechoslovak Mathematical Journal

Czechoslovak Mathematical Journal, first online, pp. 1-17

On the Kirchhoff index of hypergraphs

Shib Sankar Saha, Swarup Kumar Panda

Received July 23, 2024. Published online March 4, 2025.

Abstract: Let $\mathcal{H}$ be a connected $k$-uniform hypergraph on $n$ vertices and $m$ hyperedges. K. Feng, W. Li (1996) introduced an adjacency matrix $\mathcal{A}(\mathcal{H})$ for hypergraphs. We consider the corresponding Laplacian matrix. We extend the concept of the Kirchhoff index to connected hypergraphs. We compute the Kirchhoff index for uniform complete, uniform complete bipartite, hypertriangle, and uniform Fano plane. A hypergraph is the Laplacian integral if the spectrum of its Laplacian matrix consists entirely of integers. In the process, three different classes of hypergraphs with Laplacian integral are provided. We show that the Kirchhoff index of any connected $k$-uniform hypergraph $\mathcal{H}$ is at least $(n-1)/\binom{n-2}{k-2}$ and the equality holds if and only if $\mathcal{H}$ is a $k$-uniform complete hypergraph. We also obtain some bounds for the Kirchhoff index in terms of hypergraph invariants such as the number of vertices, number of hyperedges, and first Zagreb index.

Keywords: Laplacian matrix; Kirchhoff index; hypertriangle; uniform Fano plane; first Zagreb index

Classification MSC: 05C65, 15A18

DOI: 10.21136/CMJ.2025.0308-24

PDF available at: Springer Institute of Mathematics CAS

References:
[1] B. Alspach, P. J. Schellenberg, D. R. Stinson, D. Wagner: The Oberwolfach problem and factors of uniform odd length cycles. J. Comb. Theory, Ser. A 52 (1989), 20-43. DOI 10.1016/0097-3165(89)90059-9 | MR 1008157 | Zbl 0684.05035
[2] E. Bendito, A. Carmona, A. M. Encinas, J. M. Gesto, M. Mitjana: Kirchhoff indexes of a network. Linear Algebra Appl. 432 (2010), 2278-2292. DOI 10.1016/j.laa.2009.05.032 | MR 2599860 | Zbl 1195.94100
[3] A. Bretto: Hypergraph Theory: An Introduction. Mathematical Engineering. Springer, Cham (2013). DOI 10.1007/978-3-319-00080-0 | MR 3077516 | Zbl 1269.05082
[4] A. E. Brouwer, W. H. Haemers: Spectra of Graphs. Universitext. Springer, New York (2012). DOI 10.1007/978-1-4614-1939-6 | MR 2882891 | Zbl 1231.05001
[5] K. Cardoso, R. Del-Vecchio, L. Portugal, V. Trevisan: Adjacency energy of hypergraphs. Linear Algebra Appl. 648 (2022), 181-204. DOI 10.1016/j.laa.2022.04.018 | MR 4419002 | Zbl 1490.05156
[6] K. Cardoso, C. Hoppen, V. Trevisan: The spectrum of a class of uniform hypergraphs. Linear Algebra Appl. 590 (2020), 243-257. DOI 10.1016/j.laa.2019.12.042 | MR 4051878 | Zbl 1437.05169
[7] F. R. K. Chung: The Laplacian of a hypergraph. Expanding Graphs. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 10. AMS, Providence (1993), 21-36. DOI 10.1090/dimacs/010 | MR 1235565 | Zbl 0790.05061
[8] J. Cooper, A. Dutle: Spectra of uniform hypergraphs. Linear Algebra Appl. 436 (2012), 3268-3292. DOI 10.1016/j.laa.2011.11.018 | MR 2900714 | Zbl 1238.05183
[9] K. C. Das, I. Gutman: On Laplacian energy, Laplacian-energy-like invariant and Kirchhoff index of graphs. Linear Algebra Appl. 554 (2018), 170-184. DOI 10.1016/j.laa.2018.05.030 | MR 3828814 | Zbl 1392.05072
[10] K. C. Das, K. Xu, I. Gutman: Comparison between Kirchhoff index and the Laplacian-energy-like invariant. Linear Algebra Appl. 436 (2012), 3661-3671. DOI 10.1016/j.laa.2012.01.002 | MR 2900743 | Zbl 1241.05072
[11] Q. Deng, H. Chen: On the Kirchhoff index of the complement of a bipartite graph. Linear Algebra Appl. 439 (2013), 167-173. DOI 10.1016/j.laa.2013.03.009 | MR 3045228 | Zbl 1282.05074
[12] C. Duan, E. R. van Dam, L. Wang: The characteristic polynomials of uniform double hyperstars and uniform hypertriangles. Linear Algebra Appl. 678 (2023), 16-32. DOI 10.1016/j.laa.2023.08.011 | MR 4637262 | Zbl 1525.05092
[13] K. Feng, W.-C. W. Li: Spectra of hypergraphs and applications. J. Number Theory 60 (1996), 1-22. DOI 10.1006/jnth.1996.0109 | MR 1405722 | Zbl 0874.05041
[14] J. Friedman, A. Wigderson: On the second eigenvalue of hypergraphs. Combinatorica 15 (1995), 43-65. DOI 10.1007/BF01294459 | MR 1325271 | Zbl 0843.05075
[15] R. A. Horn, C. R. Johnson: Matrix Analysis. Cambridge University Press, Cambridge (2013). DOI 10.1017/CBO9780511810817 | MR 2978290 | Zbl 1267.15001
[16] M.-ul-I. Khan, Y.-Z. Fan: On the spectral radius of a class of non-odd-bipartite even uniform hypergraphs. Linear Algebra Appl. 480 (2015), 93-106. DOI 10.1016/j.laa.2015.04.005 | MR 3348514 | Zbl 1320.05076
[17] D. J. Klein, M. Randić: Resistance distance. J. Math. Chem. 12 (1993), 81-95. DOI 10.1007/BF01164627 | MR 1219566
[18] J. Rodríguez: On the Laplacian eigenvalues and metric parameters of hypergraphs. Linear Multilinear Algebra 50 (2002), 1-14. DOI 10.1080/03081080290011692 | MR 1890984 | Zbl 1008.05102
[19] S. S. Saha, K. Sharma, S. K. Panda: On the Laplacian spectrum of $k$-uniform hypergraphs. Linear Algebra Appl. 655 (2022), 1-27. DOI 10.1016/j.laa.2022.09.004 | MR 4484845 | Zbl 1500.05039
[20] V. I. Voloshin: Introduction to Graph and Hypergraph Theory. Nova Science, New York (2009). MR 2514872 | Zbl 1209.05002

Affiliations: Shib Sankar Saha, Swarup Kumar Panda (corresponding author), Department of Mathematics, Indian Institute of Technology Kharagpur, Kharagpur-721302, India, e-mail: shibkol2019@gmail.com, spanda@maths.iitkgp.ac.in

Springer subscribers can access the papers on Springer website.

[List of online first articles] [Contents of Czechoslovak Mathematical Journal] [Full text of the older issues of Czechoslovak Mathematical Journal at DML-CZ]

PDF available at:

Springer
for subscribers

···

Institute of Mathematics CAS
fulltext not available