THE CHARACTERISTICS 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 parti cular we consider trees without bridging vertices because no isospectr al trees in which both graphs are without bridging vertices have been hitherto reported. However, we found the smallest such isospectral fre es when n = 15. When the maximal valence is limited to four, so that g raphs correspond to molecules of organic chemistry, the smallest isosp ectral (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 witho ut bridging vertices) and subsequent pruning of proper trees one can i n many cases determine if two trees are isomorphic or not from compari son of their characteristic polynomials.