On the Djoković-Winkler relation and its closure in subdivisions of fullerenes, triangulations, and chordal graphs

Abstract

It was recently pointed out that certain SiO${}_2$ layer structures and SiO${}_2$ nanotubes can be described as full subdivisions aka subdivision graphs of partial cubes. A key tool for analyzing distance-based topological indices in molecular graphs is the Djoković-Winkler relation $\Theta$ and its transitive closure ${\Theta }^{\ast }$. In this paper we study the behavior of $\Theta$ and ${\Theta }^{\ast }$ with respect to full subdivisions. We apply our results to describe ${\Theta }^{\ast }$ in full subdivisions of fullerenes, plane triangulations, and chordal graphs.

13 pages, 5 figures, fixed a bug in Lemma 4.1