On the Wiener inverse interval problem

Matjaž Krnc
Institute of Mathematics, Physics and Mechanics

Riste Škrekovski
Faculty of Mathematics and Physics

PDF

Minisymposium: CHEMICAL GRAPH THEORY

Content: The well studied Wiener index $W(G)$ of a graph $G$ is equal to the sum of distances between all pairs of vertices of $G$. Denote by $\mathrm{Im}\left(n\right)$ the set of all values of the Wiener Index over all connected graphs on $n$ vertices. Also, let $\mathcal{I}_{n}$ be the largest interval which is fully contained in $\mathrm{Im}\left(n\right)$. In the minisymposium I will outline our results on the cardinality of $\mathcal{I}_{n}$ and $\mathrm{Im}\left(n\right)$. In particular, I will show that $\mathcal{I}_{n}$ and $\mathrm{Im}\left(n\right)$ are of cardinality $\frac{1}{6}n^{3}+O\left(n^{2}\right)$, and that they both start at $\binom{n}{2}$. We will also discuss other properties of $\mathrm{Im}\left(n\right)$ and $\mathcal{I}_{n}$ and state some open problems.

Back to all abstracts