Physics Seminar

Graphs are a cosmopolitan representation of a wide range of things, including group networks in sociology, food-webs in biology, Feynman diagrams in physics, electrical circuits in engineering (and physics), and molecules in chemistry (& physics). As molecular representations, graphs seemingly retain information about only a small part of a molecule?s character ? in particular, they seem to suppress molecular geometry (along with associated electron densities), though such graphs were developed ~150 years ago, and have been extensively used since. Thus identification of intrinsic limitations to graph representations is of interest. Naturally there is a question of intrinsic metrics on graphs, independently of whether the graphs are used to represent molecules, or whatever.

In mathematical graph-theory, there is extensive work on the shortest-path metric ? and practically nothing else was described as a metric. Still one might imagine other possibilities for an intrinsic graph metric. One may view waves on the graph network, so that emphasizing longer wavelength waves, squares of wave-amplitude differences on 2 sites might naturally be anticipated to correspond to a ?distance? between these 2 sites. Also if one looks at the number of spanning 2-component acyclic graphs with sites i & j in the different components, this might be anticipated to be a candidate for a distance between i & j (since the farther apart they are, the more opportunity there is to delete an intervening edge from a spanning tree to obtain the desired type of 2-component graph). Another possibility is to consider random walks on the graph, and in particular the probability of a walk returning to its starting site i before reaching site j might be imagined to be inversely related to a distance between i & j. Also the effective electrical resistance between i & j might be anticipated to be a distance between i & j. Some results involving these candidate metrics (wave-like, combinatorial, probablistic, & electric) are noted.

Granted a distance function, there are associated graph invariants, possibly of use in molecular structure/property correlations. Since the proposed novel metrics deal with cycles differently than the shortest-path metric ρ, a suitable comparison to ρ might measure ?graph cyclicity?. Invariants may be defined via analogy to classical Euclidean-geometric quantities ? including: linear curvature, torsion, Gaussian curvature, & mean volumina measures. One might surmise a possibility of some sort of intrinsic ?graph geometry?.