×

New inequalities for network distance measures by using graph spectra. (English) Zbl 1401.05275

Summary: Eigenvalues of graph-theoretical matrices often reflect structure properties of networks (graphs) meaningfully. In this paper, we explore inequalities for graph distance measures which are based on topological indices. Some of these indices are based on eigenvalues of graph-theoretical matrices. We here consider the adjacency matrix, the Laplacian matrix and signless Laplacian matrix. Besides proving the inequalities, we discuss the usefulness of these measures and state some conjectures.

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdo, H.; Dimitrov, D.; Reti, T.; Stevanovic, D., Estimating the spectral radius of a graph by the second zagreb index, MATCH Commun. Math. Comput. Chem., 72, 741-751, (2014) · Zbl 1464.05049
[2] Azami, S., On Laplacian and signless Laplacian Estrada indices of graphs, MATCH Commun. Math. Comput. Chem., 74, 411-418, (2015) · Zbl 1462.05064
[3] Bozkurt, S. B.; Bozkurt, D., On incidence energy, MATCH Commun. Math. Comput. Chem., 72, 215-225, (2014) · Zbl 1464.05228
[4] Bunke, H., What is the distance between graphs?, Bull. EATCS, 20, 35-39, (1983)
[5] Bunke, H., Graph matching: Theoretical foundations, algorithms, and applications, (Proceedings of Vision Interface 2000, (2000)), 82-88
[6] Cao, S.; Dehmer, M.; Shi, Y., Extremality of degree-based graph entropies, Inform. Sci., 278, 22-33, (2014) · Zbl 1354.94018
[7] Nascimento, M. C.; de Carvalho, A. C., Spectral methods for graph clustering. a survey, European J. Oper. Res., 211, 2, 221-231, (2011) · Zbl 1250.68228
[8] Chen, Z.; Dehmer, M.; Shi, Y., A note on distance-based graph entropies, Entropy, 16, 5416-5427, (2014)
[9] Chen, X.; Hou, Y., Some results on Laplacian Estrada index of graphs, MATCH Commun. Math. Comput. Chem., 73, 149-162, (2015) · Zbl 1464.05057
[10] Chen, L.; Shi, Y., Maximal matching energy of tricyclic graphs, MATCH Commun. Math. Comput. Chem., 73, 105-119, (2015) · Zbl 1464.05230
[11] Clausen, J.; Krarup, J., A family of bipartite cardinality matching problems solvable in \(O(n^2)\) time, Nordic J. Comput., 2, 4, 496-501, (1995) · Zbl 0841.68103
[12] Cvetković, D.; Gutman, I., The algebraic multiplicity of the number zero in the spectrum of a bipartite graph, Mat. Vesnik, 9, 141-150, (1972) · Zbl 0263.05125
[13] Cvetković, D.; Roelinson, P.; Simić, S. K., Eigenvalue bounds for the signless Laplacian, Publ. l’Inst. Math., 81, 11-27, (2007) · Zbl 1164.05038
[14] Cvetković, D.; Simić, S. K., Towards a spectral theory of graphs based on the signless Laplacian, ii, Linear Algebra Appl., 431, 2257-2272, (2010) · Zbl 1218.05089
[15] Daròczy, Z.; Jarai, A., On the measurable solutions of functional equation arising in information theory, Acta Math. Acad. Sci. Hungar., 34, 105-116, (1979) · Zbl 0424.39002
[16] Das, K.; Mojallal, S., Relation between energy and (signless) Laplacian energy of graphs, MATCH Commun. Math. Comput. Chem., 74, 359-366, (2015) · Zbl 1462.05217
[17] Das, K.; Sorgun, S., On Randić energy of graphs, MATCH Commun. Math. Comput. Chem., 72, 227-238, (2014) · Zbl 1464.05232
[18] Dehmer, M., Strukturelle analyse web-basierter dokumente, (Multimedia und Telekooperation, (2006), Deutscher Universitäts Verlag: Deutscher Universitäts Verlag Wiesbaden)
[19] Dehmer, M.; Emmert-Streib, F.; Shi, Y., Interrelations of graph distance measures based on topological indices, PLoS ONE, 9, e94985, (2014)
[20] Dehmer, M.; Emmert-Streib, F.; Shi, Y., Graph distance measures based on topological indices revisited, Appl. Math. Comput., 266, 623-633, (2015)
[21] Dehmer, M.; Mehler, A., A new method of measuring similarity for a special class of directed graphs, Tatra Mt. Math. Publ., 36, 39-59, (2007) · Zbl 1142.05069
[22] Dehmer, M.; Mowshowitz, A., Generalized graph entropies, Complexity, 17, 45-50, (2011)
[23] Demange, M.; Ekim, T.; Ries, B.; Tanasescu, C., On some applications of the selective graph coloring problem, European J. Oper. Res., 240, 2, 307-314, (2015) · Zbl 1357.05041
[24] Doob, M.; Sachs, H., Spectra of graphs, Theory and Application, (1995), Johann Ambrosius Barth Verlag · Zbl 0824.05046
[25] Emmert-Streib, F.; Dehmer, M., Networks for systems biology: Conceptual connection of data and function, IET Syst. Biol., 5, 185-207, (2011)
[26] Emmert-Streib, F.; Dehmer, M.; Shi, Y., Fifty years of graph matching, network alignment and comparison, Inform. Sci., 346-347, 180-197, (2016) · Zbl 1398.68393
[27] Evans, T. P.O.; Bishop, S. R., Static search games played over graphs and general metric spaces, European J. Oper. Res., 231, 3, 667-689, (2013) · Zbl 1317.91006
[28] Feng, L.; Cao, J.; Liu, W.; Ding, S.; Liu, H., The spectral radius of edge chromatic critical graphs, Linear Algebra Appl., 492, 78-88, (2016) · Zbl 1330.05066
[29] Gregory, D. A.; Heyink, B.; Meulen, K. N.V., Inertia and biclique decompositions of joins of graphs, J. Combin. Theory Ser. B, 88, 135-151, (2003) · Zbl 1025.05042
[30] Gutman, I.; Furtula, B.; Vukicevic, Z. K.; Popivoda, G., On zagreb indices and coindices, MATCH Commun. Math. Comput. Chem., 74, 5-16, (2015) · Zbl 1462.05083
[31] Hager, W. W.; Hungerford, J. T., Continuous quadratic programming formulations of optimization problems on graphs, European J. Oper. Res., 240, 2, 328-337, (2015) · Zbl 1357.90166
[32] Horn, R. A.; Johnson, C. R., Matrix Analysis, (2012), Cambridge University Press
[33] Huang, F.; Li, X.; Wang, S., On maximum laplacian Estrada indices of trees with some given parameters, MATCH Commun. Math. Comput. Chem., 74, 419-429, (2015) · Zbl 1462.05086
[34] Jiang, B.; Claramunt, C., A structural approach to the model generalization of an urban street network, Geoinformatica, 8, 2, 157-171, (2004)
[35] Joachims, T., Learning to Classify Text Using Support Vector Machines, (2002), Kluwer: Kluwer Boston
[36] Kaden, F., Graphmetriken und Distanzgraphen, ZKI-Informationen, Akad. Wiss. DDR, 2, 82, 1-63, (1982)
[37] Krarup, J.; Malene, N. R., LP formulations of the shortest path tree problem, 4OR, 2, 259-274, (2005) · Zbl 1112.90048
[38] Li, X.; Li, Y.; Shi, Y.; Gutman, I., Note on the HOMO-LUMO index of graphs, MATCH Commun. Math. Comput. Chem., 70, 85-96, (2013) · Zbl 1299.05225
[39] Lin, H.; Feng, L., The distance spectral radius of graphs with given independence number, ARS Comb., 121, 113-123, (2015) · Zbl 1363.05161
[40] Li, X.; Shi, Y., A survey on the Randić index, MATCH Commun. Math. Comput. Chem., 59, 1, 127-156, (2008) · Zbl 1249.05198
[41] Li, X.; Shi, Y.; Gutman, I., Graph Energy, (2012), Springer
[42] Li, X.; Shi, Y.; Wei, M.; Li, J., On a conjecture about tricyclic graphs with maximal energy, MATCH Commun. Math. Comput. Chem., 72, 1, 183-214, (2014) · Zbl 1464.05241
[43] Lou, Z.; Huang, Q.; Yiu, D., On the characteristic polynomial and the spectrum of a hexagonal system, MATCH Commun. Math. Comput. Chem., 72, 153-164, (2014) · Zbl 1464.05202
[44] Maggiora, G. M.; Shanmugasundaram, V., Molecular similarity measures, (Chemoinformatics: Concepts, Methods, and Tools for Drug Discovery, (2004), NJ, USA: NJ, USA totowa), 1-50
[45] Ma, J.; Shi, Y.; Wang, Z.; Yue, J., On wiener polarity index of bicyclic networks, Sci. Rep., 6, 19066, (2016)
[46] Mieghem, P. V.; Omic, J.; Kooij, R. E., Virus spread in networks, IEEE/ACM Trans. Netw., 17, 1-14, (2009)
[47] Pasten, G.; Rojo, O., Laplacian spectrum, Laplacian-energy-like invariant, and Kirchhoff index of graphs constructed by adding edges on pendent vertices, MATCH Commun. Math. Comput. Chem., 73, 27-40, (2015) · Zbl 1464.05104
[48] Pasten, G.; Rojo, O., Laplacian spectrum, laplacian-energy-like invariant, and kirchhoff index of graphs constructed by adding edges on pendent vertices, MATCH Commun. Math. Comput. Chem., 73, 27-40, (2015) · Zbl 1464.05104
[49] Qu, H.; Yu, G.; Feng, L., More on minimum skew-rank of graphs, Oper. Matrices, 9, 311-324, (2015) · Zbl 1314.05119
[50] Restrepo, J. G.; Ott, E.; Hunt, B. R., Onset of synchronization in large networks of coupled oscillators, Phys. Rev. E, 71, 1-12, (2005)
[51] Robles-Kelly, A.; Hancock, R., Edit distance from graph spectra, (Proceedings of the IEEE International Conference on Computer Vision, (2003)), 234-241
[52] Schädler, C., Die ermittlung struktureller ähnlichkeit und struktureller merkmale bei komplexen objekten: Ein konnektionistischer ansatz und seine anwendungen, (1999), Technische Universität: Technische Universität Berlin, (Ph.D. thesis)
[53] Shi, Y., Note on two generalizations of the randić index, Appl. Math. Comput., 265, 1019-1025, (2015) · Zbl 1410.05026
[54] Skvortsova, M.; Baskin, I.; Stankevich, I.; Palyulin, V.; Zefirov, N., Molecular similarity. 1. analytical description of the set of graph similarity measures, J. Chem. Inf. Comput. Sci., 38, 785-790, (1998)
[55] Sobik, F., Graphmetriken und Klassifikation Strukturierter Objekte, ZKI-Informationen, Akad. Wiss. DDR, 2, 82, 63-122, (1982) · Zbl 0496.05059
[56] Sommerfeld, E.; Sobik, F., Operations on cognitive structures - their modeling on the basis of graph theory, (Albert, D., Knowledge Structures, (1994), Springer), 146-190
[57] Spielman, D. A., Spectral graph theory and its applications, (48th Annual IEEE Symposium on Foundations of Computer Science, (2007)), 29-38
[58] Todeschini, R.; Consonni, V., Handbook of Molecular Descriptors, (2002), Wiley-VCH
[59] van Dam, E. R.; Haemers, W., Which graphs are determined by their spectrum?, Linear Algebra Appl., 373, 241-272, (2003) · Zbl 1026.05079
[60] Y. Wang, D. Chakrabarti, C. Wang, Epidemic spreading in real networks: An eigenvalue viewponit, in: 22nd Symp. Reliable Distributed Computing.; Y. Wang, D. Chakrabarti, C. Wang, Epidemic spreading in real networks: An eigenvalue viewponit, in: 22nd Symp. Reliable Distributed Computing.
[61] Wilson, R. R., An Atlas of Graphs, (1998), Clarendon Press · Zbl 0908.05001
[62] Xia, C.; Meloni, S.; Perc, M.; Moreno, Y., Dynamic instability of cooperation due to diverse activity patterns in evolutionary social dilemmas, Europhys. Lett., 109, 58002, (2015)
[63] Xia, C.; Miao, Q.; Wang, J.; Ding, S., Evolution of cooperation in the traveler’s dilemma game on two coupled lattices, Appl. Math. Comput., 246, 389-398, (2015) · Zbl 1338.91026
[64] Xia, C.; Sun, S.; Rao, F.; Sun, J.; Wang, J.; Chen, Z., SIS model of epidemic spreading on dynamical networks with community, Front. Comput. Sci. China, 3, 361-365, (2009)
[65] Xia, C.; Wang, L.; Sun, S.; Wang, J., An sir model with infection delay and propagation vector in complex networks, Nonlinear Dynam., 69, 927-934, (2012)
[66] Xu, K.; Liu, M.; Das, K.; Gutman, I.; Furtula, B., A survey on graphs extremal with respect to distance-based topological indices, MATCH Commun. Math. Comput. Chem., 71, 461-508, (2014) · Zbl 1464.05140
[67] Yu, G.; Feng, L.; Ilic, A.; Stevanovic, D., The signless laplacian spectral radius of bounded degree graphs on surfaces, Appl. Anal. Discrete Math., 9, 332-346, (2015) · Zbl 1464.05258
[68] Yu, G.; Feng, L.; Wang, Q., Bicyclic graphs with small positive index of inertia, Linear Algebra Appl., 438, 2036-2045, (2013) · Zbl 1258.05080
[69] Yu, G.; Zhang, X.; Feng, L., The inertia of weighted unicyclic graphs, Linear Algebra Appl., 448, 130-152, (2014) · Zbl 1285.05084
[70] Zelinka, B., On a certain distance between isomorphism classes of graphs, Časopis pro p˘est. Mathematiky, 100, 371-373, (1975) · Zbl 0312.05121
[71] Zhang, H.; Deng, K., Spectrum of matching forcing numbers of a hexagonal system with a forcing edge, MATCH Commun. Math. Comput. Chem., 73, 457-471, (2015) · Zbl 1464.05312
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.