COLLEGE OF ARTS AND SCIENCES Department of Mathematics and Statistics
(click here for colloquia)

Algebra Seminar: Two Vertex Descriptors Based on Hosoya's Matching Descriptor Z(G).


1:10 pm, Heill Hall 106W

Matt Hudelson

abstract: In 1971, Harao Hosoya launched the study of graph-theoretical descriptors in chemical applications by demonstrating a high correlation between the number of matchings of an alkane to its boiling point. We continue his legacy by describing two distinct vertex descriptors. The first of these descriptors is defined by (G,v)=Z(G)/Z(G-v) where Z(G) enumerates the n number of matchings, i.e. partitions of the vertex set into singletons and adjacent pairs, of the graph G. We will show that if G is a tree, then (G,v) can be approached via "tree expressions," a generalization of continued fractions. The second descriptor associates to each vertex in G a polynomial in whose coefficients p_i (v) enumerate the n number of distinct paths of length i that begin at the vertex v. Together, adaptations of these descriptors form a "local vertex space" such that two vertices with similar local characteristics are mapped to points that are close in this space. As an application of such a space, we can quickly search large databases of chemical compounds for atoms with specific local connectivity environments.