|
This article is cited in 1 scientific paper (total in 1 paper)
Mathematics
Maximal outerplane graphs of extremal diameter
Yu. L. Nosov Guardian Software Inc., Calgary, Canada; remote office: Lipetsk, Russia
Abstract:
We explore the maximal outerplane graphs (MOP-graphs) with extremal values of diameter. For arbitrary MOP-graphs we determine the lower and upper bounds of the diameter.
For lattice MOP-graphs (i. e., graphs embedded into the lattice of equilateral triangles without "holes" and intersections) we prove that the upper bound of the diameter matches that of the arbitrary MOP-graphs; a preliminary lower bound of the diameter is determined.
For the lower and upper bounds of the diameter of arbitrary and lattice MOP-graphs we determine the extremal graphs where these bounds are reached. Extremal graphs with maximal diameter are the same for both arbitrary and lattice MOP-graphs.
The obtained results can be used for classification of images represented by MOP-graphs, and for classification of isomers of conjugated polyene hydrocarbons.
Keywords:
maximal outerplane graphs, diameter, extremal graphs,
graphs with extremal values of diameter.
Received: 12.04.2018 Revised: 14.06.2018
Citation:
Yu. L. Nosov, “Maximal outerplane graphs of extremal diameter”, Chelyab. Fiz.-Mat. Zh., 3:4 (2018), 421–437
Linking options:
https://www.mathnet.ru/eng/chfmj116 https://www.mathnet.ru/eng/chfmj/v3/i4/p421
|
|