Naslov
The characteristic polynomial as a structure discriminator

Autori
Randić, Milan ; Muller, Wolfgang R. ; Knop, Jan V. ; Trinajstić, Nenad

Izvornik
Journal of chemical information and computer sciences (0095-2338) 37 (1997), 6; 1072-1077

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
molecules; enumeration; spectra; graphs; trees

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Kemija

POVEZANOST RADA