×

Encoding structural information uniquely with polynomial-based descriptors by employing the Randić matrix. (English) Zbl 1410.05093

Summary: In this paper we define novel graph measures based on the zeros of the characteristic polynomial by using the Randić matrix. We compute the novel graph descriptors on exhaustively generated graphs and trees and demonstrate that the measures encode their structural information uniquely. These results are compared with the same graph measures but based on the eigenvalues of the classical characteristic polynomial of a graph. Finally we interpret our findings that are evidenced by numerical results.

MSC:

05C31 Graph polynomials
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15B99 Special matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs. Theory and Application (1980), Deutscher Verlag der Wissenschaften: Deutscher Verlag der Wissenschaften Berlin, Germany · Zbl 0458.05042
[2] Hosoya, H., On some counting polynomials, Discrete Appl. Math., 19, 239-257 (1988) · Zbl 0633.05006
[3] Gutman, I., Polynomials in graph theory, (Bonchev, D.; Rouvray, D. H., Chemical Graph Theory. Introduction and Fundamentals (1991), Abacus Press: Abacus Press New York, NY, USA), 133-176 · Zbl 0746.05063
[4] Dehmer, M.; Shi, Y.; Mowshowitz, A., Discrimination power of graph measures based on complex zeros of the partial hosoya polynomial, Appl. Math. Comput., 250, 352-355 (2015) · Zbl 1328.05095
[5] Ellis-Monaghan, J. A.; Merino, C., Graph polynomials and their applications I: The Tutte polynomial, (Dehmer, M., Structural Analysis of Complex Networks (2010), Birkhäuser: Birkhäuser Boston/Basel), 219-255 · Zbl 1221.05002
[6] Chou, C.; Witek, H., Determination of Zhang-Zhang polynomials for various classes of benzenoid systems: bon-heuristic approach, MATCH Commun. Math. Comput. Chem., 72, 75-104 (2014) · Zbl 1464.05007
[7] 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
[8] Alikhani, S.; Iranmanesh, M., Hosoya polynomial of dendrimer nanostar \(D_3[n]\), MATCH Commun. Math. Comput. Chem., 71, 395-405 (2014) · Zbl 1464.05196
[9] He, Q.; Gu, J.; Xu, S.; Chan, W., Hosoya polynomials of hexagonal triangles and trapeziums, MATCH Commun. Math. Comput. Chem., 72, 835-843 (2014) · Zbl 1464.05200
[10] Lin, X.; Xu, S.; Yeh, Y., Hosoya polynomials of circumcoronene series, MATCH Commun. Math. Comput. Chem., 69, 3, 755-763 (2013) · Zbl 1299.05177
[11] Holzinger, A.; Dehmer, M.; Jurisica, I., Knowledge discovery and interactive data mining in bioinformatics-state-of-the-art, future challenges and research directions, BMC Bioinformatics, 15, Suppl. 6: I1, 1-9 (2014)
[12] Hosoya, H., Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn., 44, 2332-2339 (1971)
[13] Liu, Z. L.Y.; Zhuang, W., Largest Hosoya index and smallest Merrifield-Simmons index in tricyclic graphs, MATCH Commun. Math. Comput. Chem., 73, 1, 195-224 (2015) · Zbl 1462.05092
[14] Randić, M.; Vracko, M.; Novic, M., Eigenvalues as molecular descriptors, (Diudea, M. V., QSPR/QSAR Studies by Molecular Descriptors (2001), Nova Publishing: Nova Publishing Huntington, NY, USA), 93-120
[15] Todeschini, R.; Consonni, V.; Mannhold, R., Handbook of Molecular Descriptors (2002), Wiley-VCH: Wiley-VCH Weinheim, Germany
[16] Dehmer, M.; Müller, L.; Graber, A., New polynomial-based molecular descriptors with low degeneracy, PLoS ONE, 5, 7 (2010)
[17] Brešar, B.; Klavžar, S.; Škrekovski, R., Roots of cube polynomials of median graphs, J. Graph Theory, 52, 37-50 (2006) · Zbl 1117.05105
[18] Woodall, D., A zero-free interval for chromatic polynomials, Discrete Math., 101, 333-341 (1992) · Zbl 0766.05030
[19] Dehmer, M.; Ilić, A., Location of zeros of Wiener and distance polynomials, PLoS ONE, 7, e28328 (2012)
[20] Lovász, L.; Pelikán, J., On the eigenvalues of trees, Periodica Mathematica Hungarica, 3, 1-2, 175-182 (1973) · Zbl 0247.05108
[21] Bonchev, D., Topological order in molecules 1. Molecular branching revisited, J. Mol. Struct.: THEOCHEM, 336, 2-3, 137-156 (1995)
[22] Schutte, M.; Dehmer, M., Large-scale analysis of structural branching measures, J. Math. Chem., 52, 3, 805-819 (2013) · Zbl 1296.92246
[23] Randić, M., On characterization of molecular branching, J. Amer. Chem. Soc., 97, 6609-6615 (1975)
[24] Li, X.; Shi, Y., A survey on the Randić index, MATCH Commun. Math. Comput. Chem., 59, 1, 127-156 (2008) · Zbl 1249.05198
[25] Bozkurt, S. B.; Güngör, A. D.; Gutman, I.; Cevik, A. S., Randić matrix and randić energy, MATCH Commun. Math. Comput. Chem., 64, 239-250 (2010) · Zbl 1265.05113
[26] Gu, R.; Huang, F.; Li, X., General Randić matrix and general Randi’c energy, Trans. Comb., 3, 21-33 (2014) · Zbl 1463.05330
[27] Furtula, B.; Bozkurt, S. B.; Gutman, I., On Randić energy, Linear Algebra Appl., 442, 1, 50-57 (2014) · Zbl 1282.05118
[28] Das, K.; Sorgun, S.; Gutman, I., On Randić energy, MATCH Commun. Math. Comput. Chem., 73, 1, 81-92 (2015) · Zbl 1464.05233
[29] Gutman, I., The energy of a graph: Old and new results, (Betten, A.; Kohnert, A.; Laue, R.; Wassermann, A., Algebraic Combinatorics and Applications (2001), Springer Verlag: Springer Verlag Berlin), 196-211 · Zbl 0974.05054
[30] Li, X.; Shi, Y.; Gutman, I., Graph Energy (2012), Springer · Zbl 1262.05100
[31] Gomes, H.; Gutman, I.; Martins, E.; Robbiano, M.; Martin, B. S., On Randić spread, MATCH Commun. Math. Comput. Chem., 72, 249-266 (2014) · Zbl 1464.05070
[32] Gomes, H.; Martins, E.; Robbiano, M.; Martin, B. S., Upper bounds for Randić spread, MATCH Commun. Math. Comput. Chem., 72, 267-278 (2014) · Zbl 1464.05236
[33] Das, K.; Sorgun, S., On Randić energy of graphs, MATCH Commun. Math. Comput. Chem., 72, 227-238 (2014) · Zbl 1464.05232
[34] Bozkurt, S. B.; Bozkurt, D., On incidence energy, MATCH Commun. Math. Comput. Chem., 72, 215-225 (2014) · Zbl 1464.05228
[35] Ji, S.; Li, X.; Shi, Y., The extremal matching energy of bicyclic graphs, MATCH Commun. Math. Comput. Chem., 70, 697-706 (2013) · Zbl 1299.05220
[36] Li, J.; Guo, J.; Shiu, W., A note on Randić Energy, MATCH Commun. Math. Comput. Chem., 74, 2, 389-398 (2015) · Zbl 1462.05089
[37] Bonchev, D.; Mekenyan, O.; Trinajstić, N., Isomer discrimination by topological information approach, J. Comput. Chem., 2, 2, 127-148 (1981)
[38] Konstantinova, E. V., The discrimination ability of some topological and information distance indices for graphs of unbranched hexagonal systems, J. Chem. Inf. Comput. Sci., 36, 54-57 (1996)
[39] Dehmer, M.; Grabner, M.; Varmuza, K., Information indices with high discriminative power for graphs, PLoS ONE, 7, e31214 (2012)
[40] Dehmer, M.; Barbarini, N.; Varmuza, K.; Graber, A., Novel topological descriptors for analyzing biological networks, BMC Struct. Biol., 10, 18 (2010)
[41] Horváth, T., Cyclic pattern kernels revisited, Proceedings of the 9-th Pacific-Asia Conference, PAKDD 2005, 791-801 (2005)
[42] Mehler, A.; Gleim, R.; Dehmer, M., Towards structure-sensitive hypertext categorization, (Spiliopoulou, M.; Kruse, R.; Borgelt, C.; Nrnberger, A.; Gaul, W., Proceedings of the 29th Annual Conference of the German Classification Society, Universität Magdeburg, March 9-11. Proceedings of the 29th Annual Conference of the German Classification Society, Universität Magdeburg, March 9-11, LNCS (2005), Springer: Springer Berlin/New York), 406-413
[43] Harary, F., Graph Theory (1969), Addison Wesley Publishing Company: Addison Wesley Publishing Company Reading, MA, USA · Zbl 0182.57702
[44] Liu, B.; Huang, Y.; Feng, J., A note on the Randić spectral radius, MATCH Commun. Math. Comput. Chem., 68, 913-916 (2012) · Zbl 1289.05133
[45] McKay, B. D., Graph isomorphisms, Congressus Numerantium, 730, 45-87 (1981)
[46] Konstantinova, E. V.; Skorobogatov, V. A.; Vidyuk, M. V., Applications of information theory in chemical graph theory, Indian J. Chem., 42, 1227-1240 (2002)
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.