The characteristic polynomial as a structure discriminator (CROSBI ID 77490)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Randić, Milan ; Muller, Wolfgang R. ; Knop, Jan V. ; Trinajstić, Nenad
engleski
The characteristic polynomial as a structure discriminator
We investigate use of the characteristic polynomial for discrimination of graphs. Here we consider acyclic graphs (trees) only, and in particular we consider trees without bridging vertices because no isospectral trees in which both graphs are without bridging vertices have been hitherto reported. However, we found the smallest such isospectral frees when n = 15. When the maximal valence is limited to four, so that graphs correspond to molecules of organic chemistry, the smallest isospectral (nonbridging) trees have n = 19 vertices. The smallest pair of isospectral binary trees were found among trees having n = 26 vertices. By combining contraction of trees to proper trees (i.e., trees without bridging vertices) and subsequent pruning of proper trees one can in many cases determine if two trees are isomorphic or not from comparison of their characteristic polynomials.
molecules; enumeration; spectra; graphs; trees
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano