Extremal by Wiener index maximal outerplane graphs with two simplicial vertices

Yu. L. Nosov

Čelâbinskij fiziko-matematičeskij žurnal, Tome 4 (2019) no. 3, pp. 285-322

Résumé

We consider the maximal outerplane graphs (mops) with two simplicial vertices, with the extreme values of the Wiener index. The lower $W^L_n = n^2-3n+3$ and upper $W^U_n=(4n^3+6n^2-4n-3+3(-1)^n)/48$ bounds of the Wiener index of arbitrary mops of the order $n$ are determined. For the lattice mops (L-mops), i. e. the graphs that are laid out on the lattice of equilateral triangles without voids and overlaps, we prove that the upper bound of Wiener index matches that of the arbitrary mops. The lower bound $W^{[L]}_n$ of Wiener index of L-mops is defined as follows: $W^{[L]}_n = (n^3 +6n^2-15n+26)/18$ if $(n- 4) \bmod 3 = 0$ and $W^{[L]}_n = (n^3 +6n^2-9n+2-2(-1)^q)/18$ if $(n- 4) \bmod 3 = q$ where $q=1,2$. For the lower and upper bounds of Wiener index of arbitrary and lattice mops we determine the extremal graphs, where these bounds are reached. We provide a constructive classification of L-mops. For all classes of L-mops we determine the extremal graphs and their respective Wiener indices. For each class of L-mops we show the existence of isomorphism and geometric similarity between dual graphs of L-mop class and molecular graphs of isomers and conformers of conjugated polyene hydrocarbons (CPH). The obtained results can be used for classification of shapes in images represented by mops and for classification of CPH isomers.

Détail

Keywords: maximal outerplane graph, extremal graph, Wiener index.