Geodesic
Maximal outerplane graphs of extremal diameter
Čelâbinskij fiziko-matematičeskij žurnal, Tome 3 (2018) no. 4, pp. 421-437.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{CHFMJ_2018_3_4_a3,
     author = {Yu. L. Nosov},
     title = {Maximal outerplane graphs of extremal diameter},
     journal = {\v{C}el\^abinskij fiziko-matemati\v{c}eskij \v{z}urnal},
     pages = {421--437},
     publisher = {mathdoc},
     volume = {3},
     number = {4},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHFMJ_2018_3_4_a3/}
}
TY  - JOUR
AU  - Yu. L. Nosov
TI  - Maximal outerplane graphs of extremal diameter
JO  - Čelâbinskij fiziko-matematičeskij žurnal
PY  - 2018
SP  - 421
EP  - 437
VL  - 3
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHFMJ_2018_3_4_a3/
LA  - ru
ID  - CHFMJ_2018_3_4_a3
ER  - 
%0 Journal Article
%A Yu. L. Nosov
%T Maximal outerplane graphs of extremal diameter
%J Čelâbinskij fiziko-matematičeskij žurnal
%D 2018
%P 421-437
%V 3
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHFMJ_2018_3_4_a3/
%G ru
%F CHFMJ_2018_3_4_a3
Yu. L. Nosov. Maximal outerplane graphs of extremal diameter. Čelâbinskij fiziko-matematičeskij žurnal, Tome 3 (2018) no. 4, pp. 421-437. http://geodesic.mathdoc.fr/item/CHFMJ_2018_3_4_a3/

[1] Evstigneev V.A., Dictionary of graphs in computer science, Siberian Scientific Publishing House, Novosibirsk, 2009, 300 pp. | MR

[2] Harary F., Graph Theory, Addison-Wesley, Reading, MA, 1969, 274 pp. | MR | Zbl

[3] A. S. Asratian, N. Oksimets, “Graphs with hamiltonian balls”, The Australian Journal of Combinatorics, 17:4 (1998), 185–198 | MR | Zbl

[4] A. Proskurowski, “Subgraphs in $k$-trees: cables and caterpillars”, Discrete Mathematics, 49:5 (1984), 275–278 | DOI | MR

[5] M. Markov, “On the vertex separation of maximal outerplanar graphs”, Serdica Journal of Computing, 154:5 (2008), 207–238 | MR

[6] A. M. Farley, A. Proskurowski, “Computation of the center and diameter of outerplanar graphs”, Discrete Applied Mathematics, 2:3 (1980), 185–191 | DOI | MR | Zbl

[7] S. J. Cyvin, E. K. Lloyd, B. N. Cyvin, J. Brunvoll, “Chemical relevance of a pure combinatorial problem: isomers of conjugated polyenes”, Structural Chemistry, 7:3 (1996), 183–186 | DOI

[8] P. F. Felzenszwalb, “Representation and detection of deformable shapes”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 27:2 (2005), 208–220 | DOI

[9] F. R. F. Chung, “Diameters of graphs: old problems and new results”, Congressus Numerantium, 60:2 (1987), 295–317 | MR | Zbl

[10] Nosov Yu.L., “The Wiener index of maximal outerplane graphs”, Applied discrete mathematics, 26:4 (2014), 112–122 (In Russ.)

[11] Nosov Yu.L., “Maximal outerplane graphs with two simplicial vertices”, Applied discrete mathematics, 29:3 (2015), 95–109 (In Russ.)

[12] Dobrynin A.A., Gutman I., “The Wiener index for trees and graphs of hexagonal systems”, Discrete analysis and operations research. Ser. 2, 5:2 (1998), 34–60 (In Russ.) | MR | Zbl