Abstract

This paper introduces the minimum hop hub distance matrix of a connected graph and the associated graph energy, denoted Ehd(G). The matrix is obtained from the distance matrix by placing the value 1 in every diagonal position indexed by a vertex of a prescribed minimum hop hub set, so that the new invariant couples the metric structure of the graph with the hop hub number hh(G). Exact closed forms of the characteristic polynomial, the spectrum and the energy are established for complete graphs, complete bipartite graphs Kp,p and double stars Sp,p, each derived by an explicit eigenvector decomposition rather than by inspection. Two coefficient identities that had been stated in terms of the size q are shown to depend instead on the second distance moment W2(G) = P i<j d(vi, vj)2, equivalently on the Wiener and hyper-Wiener indices; corrected statements and proofs are supplied. A structural decomposition AH hd(G) = D(G) + diag(χH) is exploited to obtain Weyl-type eigenvalue interlacing with the distance matrix, the perturbation bound |Ehd(G) − ED(G)| ≤ hh(G), bounds of McClelland and Koolen–Moulton type, and the sharp lower bound Ehd(G) ≥ p for every connected graph of order p, with equality precisely for the complete graph. Since the energy depends on the choice of minimum hop hub set, the genuine invariants E− hd(G), E+ hd(G) and the spread σ(G) = E+ hd(G) − E− hd(G) are introduced and bounded by 2hh(G). All theoretical claims are supported by an exhaustive computational evaluation over 45 named graphs, 448 minimum hop hub sets and 2074 random connected graphs, reported through six tables and four figures.

References

• C. Adiga, A. Bayad, I. Gutman, S. A. Srinivas, The minimum covering energy of a graph, Kragujevac Journal of Science. 34, 39–56, 2012.
• U. Alper, G. Arif, K. Necla, I. Gutman, Relating graph energy and Sombor index, Discrete Mathematics Letters. 8, 6–9, 2021.
• S. K. Ayyaswamy, C. Natarajan, Hop domination in graphs, Analele S¸ tiint¸ifice ale Universit˘at¸ii Ovidius Constant¸a, Seria Matematic˘a. 23, 187–199, 2015.
• R. B. Bapat, Graphs and Matrices, Hindustan Book Agency, New Delhi, 2011.
• R. B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bulletin of the Kerala Mathematics Association. 1, 129–132, 2004.
• R. Bhatia, Matrix Analysis, Graduate Texts in Mathematics 169, Springer, New York, 1997.
• S. B. Bozkurt, A. D. G¨ung¨or, B. Zhou, Note on the distance energy of graphs, MATCH Communications in Mathematical and in Computer Chemistry. 64, 129–134, 2010.
• G. Caporossi, E. Chasset, B. Furtula, Some conjectures and properties on distance energy, Les Cahiers du GERAD. 64, 1–7, 2009.
• X. G. Chen, Y. F. Wang, On total domination and hop domination in diamond-free graphs, Bulletin of the Malaysian Mathematical Sciences Society. 43, 1885–1891, 2020.
• C. A. Coulson, On the calculation of the energy in unsaturated hydrocarbon molecules, Proceedings of the Cambridge Philosophical Society. 36, 201–203, 1940.
• A. Graovac, I. Gutman, N. Trinajsti´c, Topological Approach to the Chemistry of Conjugated Molecules, Springer, Berlin, 1977.
• T. Grauman, S. Hartke, A. Jobson, B. Kinnersley, D. West, L. Wiglesworth, P. Worah, H. Wu, The hub number of a graph, Information Processing Letters. 108, 226–228, 2008.
• J. W. Grossman, F. Harary, M. Klawe, Generalized Ramsey theory for graphs, X: Double stars, Discrete Mathematics. 28, 247–254, 1979.
• I. Gutman, The energy of a graph, Berichte der Mathematisch-Statistischen Sektion im Forschungszentrum Graz. 103, 1–22, 1978.
• I. Gutman, X. Li, J. Zhang, Graph energy, in: Analysis of Complex Networks: From Biology to Linguistics, Wiley-VCH, Weinheim, 145–174, 2009.
• I. Gutman, O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer, Berlin, 1986.
• A. D. G¨ung¨or, S. B. Bozkurt, On the distance spectral radius and distance energy of graphs, Linear and Multilinear Algebra. 59, 365–370, 2011.
• F. Harary, Graph Theory, Addison-Wesley, Massachusetts, 1969.
• T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
• G. Indulal, I. Gutman, A. Vijayakumar, On distance energy of graphs, MATCH Communications in Mathematical and in Computer Chemistry. 60, 461–472, 2008.
• D. J. Klein, I. Lukovits, I. Gutman, On the definition of the hyper-Wiener index for cycle-containing structures, Journal of Chemical Information and Computer Sciences. 35, 50–52, 1995.
• J. H. Koolen, V. Moulton, Maximal energy graphs, Advances in Applied Mathematics. 26, 47–52, 2001.
• X. Li, Y. Shi, I. Gutman, Graph Energy, Springer, New York, 2012.
• S. S. Mahde, A. S. Sand, Hop hub-integrity of graphs, International Journal of Mathematics and its Applications. 4, 91–100, 2021.
• V. Mathad, S. S. Mahde, The minimum hub energy of a graph, Palestine Journal of Mathematics. 6, 247–256, 2017.
• B. J. McClelland, Properties of the latent roots of a matrix: the estimation of π-electron energies, The Journal of Chemical Physics. 54, 640–643, 1971.
• K. Palani, M. Lalitha Kumari, Minimum hop dominating energy of a graph, Advances and Applications in Mathematical Sciences. 21, 3–12, 2022.
• H. S. Ramane, D. S. Revankar, I. Gutman, S. B. Rao, B. D. Acharya, H. B. Walikar, Bounds for the distance energy of a graph, Kragujevac Journal of Mathematics. 31, 59–68, 2008.
• M. Randi´c, Novel molecular descriptor for structure-property studies, Chemical Physics Letters. 211, 478–483, 1993.
• A. M. Sahal, A. S. Sand, S. S. Mahde, Hop hub number in graphs, Bulletin of the Korean Mathematical Society. 33, 319–329, 2023.
• A. S. Sanad, S. S. Mahde, Hop hubtic number and hop hub polynomial of graphs, International Journal of Computer Applications. 183, 1–5, 2022.
• A. Sanad, C. Li, Partial total domination in hypergraphs, Mathematics. 13(6), 910, 2025.
• M. Walsh, The hub number of graphs, International Journal of Mathematics and Computer Science. 1, 117–124, 2006.
• H.Wiener, Structural determination of paraffin boiling points, Journal of the American Chemical Society. 69, 17–20, 1947.