{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:20:25Z","timestamp":1760239225033,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2020,10,7]],"date-time":"2020-10-07T00:00:00Z","timestamp":1602028800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The orbit polynomial is a new graph counting polynomial which is defined as OG(x)=\u2211i=1rx|Oi|, where O1, \u2026, Or are all vertex orbits of the graph G. In this article, we investigate the structural properties of the automorphism group of a graph by using several novel counting polynomials. Besides, we explore the orbit polynomial of a graph operation. Indeed, we compare the degeneracy of the orbit polynomial with a new graph polynomial based on both eigenvalues of a graph and the size of orbits.<\/jats:p>","DOI":"10.3390\/sym12101643","type":"journal-article","created":{"date-parts":[[2020,10,7]],"date-time":"2020-10-07T09:12:58Z","timestamp":1602061978000},"page":"1643","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On the Degeneracy of the Orbit Polynomial and Related Graph Polynomials"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5623-9932","authenticated-orcid":false,"given":"Modjtaba","family":"Ghorbani","sequence":"first","affiliation":[{"name":"Department of Mathematics, Faculty of Science, Shahid Rajaee Teacher Training University, Tehran 16785-136, Iran"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8454-5857","authenticated-orcid":false,"given":"Matthias","family":"Dehmer","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Swiss Distance University of Applied Sciences, 3900 Brig, Switzerland"},{"name":"Department of Biomedical Computer Science and Mechatronics, UMIT, Hall in Tyrol A-6060, Austria"},{"name":"College of Artficial Intelligence, Nankai University, Tianjin 300071, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0745-5641","authenticated-orcid":false,"given":"Frank","family":"Emmert-Streib","sequence":"additional","affiliation":[{"name":"Predictive Medicine and Analytics Lab, Department of Signal Processing, Tampere University of Technology, 33720 Tampere, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,10,7]]},"reference":[{"key":"ref_1","unstructured":"Cvetkovi\u0107, D., Doob, M., and Sachs, H. (1995). Spectra of Graphs Theory and Applications, Academic Press."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0166-218X(88)90017-0","article-title":"On some counting polynomials in chemistry. Applications of graphs in chemistry and physics","volume":"19","author":"Hosoya","year":"1988","journal-title":"Discret. Appl. Math."},{"key":"ref_3","first-page":"97","article-title":"Generalizations of the matching polynomial","volume":"24","author":"Gutman","year":"1983","journal-title":"Util. Math."},{"key":"ref_4","unstructured":"Gutman, I., Bonchev, D., and Rouvray, D.H. (1991). Polynomials in Graph Theory. Chemical Graph Theory, Introduction and Fundamentals, Abacus Press."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/j.akcej.2017.09.006","article-title":"Randi\u0107 index and information","volume":"15","author":"Gutman","year":"2018","journal-title":"AKCE Int. J. Graphs Comb."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2332","DOI":"10.1246\/bcsj.44.2332","article-title":"Topological index, A newly proposed quantity characterizing the topological nautre of structural isomers of saturated hydrocarbons","volume":"44","author":"Hosoya","year":"1971","journal-title":"Bull. Chem. Soc. Jpn."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/3-540-51505-4_27","article-title":"Clar\u2019s aromatic sextet and sextet polynomial","volume":"153","author":"Hosoya","year":"1990","journal-title":"Top. Curr. Chem."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0095-8956(79)90070-4","article-title":"An introduction to matching polynomials","volume":"27","author":"Farrell","year":"1979","journal-title":"J. Comb. Theory"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1515\/zna-1990-0509","article-title":"Molecular graphs with equal Zcounting and independence polynomials","volume":"45","author":"Gutman","year":"1990","journal-title":"Z. Naturforsch."},{"key":"ref_10","first-page":"139","article-title":"Some analytical properties of the independence and matching polynomials","volume":"28","author":"Gutman","year":"1992","journal-title":"Match Commun. Math. Comput. Chem."},{"key":"ref_11","first-page":"31","article-title":"King and domino polynomials for polyomino graphs, Graph Theory Notes","volume":"34","author":"Motoyama","year":"1977","journal-title":"J. Math. Phys."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1002\/jcc.540060513","article-title":"Computer generation of king and color polynomials of graphs and lattices and their applications to statistical mechanics","volume":"6","author":"Balasubramanian","year":"1985","journal-title":"J. Comput. Chem."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/BF02386118","article-title":"On star polynomials of complements of graphs","volume":"26","author":"Farrell","year":"1988","journal-title":"Ark. Mat."},{"key":"ref_14","first-page":"33","article-title":"Star polynomials of some families of graphs with small cyclomatic numbers","volume":"33","author":"Farrell","year":"1988","journal-title":"Util. Math."},{"key":"ref_15","unstructured":"Trinastic, N. (1986). On Graph Theoretical Polynomials in Chemistry. Mathematical and Computational Concepts in Chemistry, Ellis Horwood Ltd."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"36100","DOI":"10.1109\/ACCESS.2020.2970059","article-title":"The orbit-polynomial: A novel measure of symmetry in graphs","volume":"8","author":"Dehmer","year":"2020","journal-title":"IEEE Access"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/j.ins.2018.07.072","article-title":"Graph measures with high discrimination power revisited: A random polynomial approach","volume":"467","author":"Dehmer","year":"2018","journal-title":"Inform. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1021\/ci970052g","article-title":"Characterization of isospectral graphs using Ggraph invariants and derived orthogonal parameters","volume":"38","author":"Balasubramanian","year":"1998","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Dixon, J.D., and Mortimer, B. (1996). Permutation Groups, Springer.","DOI":"10.1007\/978-1-4612-0731-3"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Harary, F. (1969). Graph Theory, Addison-Wesley Publishing Company.","DOI":"10.21236\/AD0705364"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Dehmer, M., Mowshowitz, A., and Shi, Y. (2014). Structural differentiation of graphs using Hosoya-based indices. PLoS ONE, 7.","DOI":"10.1371\/journal.pone.0102459"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1016\/j.amc.2015.05.072","article-title":"Graph distance measures based on topological indices revisited","volume":"266","author":"Dehmer","year":"2015","journal-title":"Appl. Math. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.3390\/e17031054","article-title":"The Hosoya entropy of a graph","volume":"17","author":"Mowshowitz","year":"2015","journal-title":"Entropy"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.amc.2019.01.024","article-title":"Hosoya entropy of fullerene graph","volume":"352","author":"Ghorbani","year":"2019","journal-title":"Appl. Math. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Ghorbani, M., Mowshowitz, A., and Emmert-Streib, F. (2019). The Hosoya entropy of graphs revisited. Symmetry, 11.","DOI":"10.3390\/sym11081013"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/j.ins.2020.03.011","article-title":"On the zeros of the partial Hosoya polynomial of graphs","volume":"524","author":"Ghorbani","year":"2020","journal-title":"Inf. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1359","DOI":"10.1090\/S0002-9939-07-09110-1","article-title":"The contraction principle for mappings on a metric space with a graph","volume":"136","author":"Jachiymski","year":"2008","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"467","DOI":"10.3390\/sym12030467","article-title":"Hybrid \u0106iri\u0107 type graphic (\u03a5,\u039b)-contraction mappings with applications to electric circuit and fractional differential equations","volume":"12","author":"Eskandar","year":"2020","journal-title":"Symmetry"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1515\/gmj-2017-0063","article-title":"On generalized \u03b1-\u03c8-Geraghty contractions on b-metric spaces","volume":"27","author":"Afshari","year":"2020","journal-title":"Georg. J. Math."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Karapinar, E., Czerwik, S., and Aydi, H. (2018). (\u03b1,\u03c8)-Meir-Keeler contraction mappings in generalized b-metric spaces. J. Funct. Spaces.","DOI":"10.1155\/2018\/3264620"},{"key":"ref_31","unstructured":"Bollob\u00e1s, B. (2001). Random Graphs, Cambridge University Press. [2nd ed.]. Cambridge Studies in Advanced Mathematics."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"4517","DOI":"10.1063\/1.434593","article-title":"Information theory, distance matrix and molecular branching","volume":"67","author":"Bonchev","year":"1977","journal-title":"J. Chem. Phys."},{"key":"ref_33","unstructured":"Bonchev, D., and Rouvray, D.H. (1991). Introduction and Fundamentals. Chemical Graph Theory, Abacus Press."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.amc.2007.12.010","article-title":"Information processing in complex networks: Graph entropy and information functionals","volume":"201","author":"Dehmer","year":"2008","journal-title":"Appl. Math. Comput."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02477860","article-title":"Life, information theory, and topology","volume":"17","author":"Rashevsky","year":"1955","journal-title":"Bull. Math. Biophys."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF02476948","article-title":"Entropy and the complexity of graphs: I. An index of the relative complexity of a graph","volume":"30","author":"Mowshowitz","year":"1968","journal-title":"Bull. Math. Biophys."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Betten, A., Kohnert, A., Laue, R., and Wassermann, A. (2001). The Energy of a Graph: Old and New Results. Algebraic Combinatorics and Applications, Springer.","DOI":"10.1007\/978-3-642-59448-9"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/10\/1643\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:17:01Z","timestamp":1760177821000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/10\/1643"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,7]]},"references-count":37,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2020,10]]}},"alternative-id":["sym12101643"],"URL":"https:\/\/doi.org\/10.3390\/sym12101643","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2020,10,7]]}}}