Geodesic
Maximal outerplane graphs with two simplicial vertices
Prikladnaâ diskretnaâ matematika, no. 3 (2015), pp. 95-109.

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

The class of maximal outerplane graphs with two simplicial vertices is considered. The following results are obtained for graphs of this class: recursive characterization, a formula for computation of unlabeled graphs, a complete invariant that differs from the known complete invariant of arbitrary maximal outerplane graphs, and a polynomial algorithm for computation of the complete invariant.
Keywords: maximal outerplanar graphs, $2$-path, enumeration, unlabeled graphs, complete invariant. 
@article{PDM_2015_3_a7,
     author = {Y. L. Nosov},
     title = {Maximal outerplane graphs with two simplicial vertices},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {95--109},
     publisher = {mathdoc},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2015_3_a7/}
}
TY  - JOUR
AU  - Y. L. Nosov
TI  - Maximal outerplane graphs with two simplicial vertices
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2015
SP  - 95
EP  - 109
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2015_3_a7/
LA  - ru
ID  - PDM_2015_3_a7
ER  - 
%0 Journal Article
%A Y. L. Nosov
%T Maximal outerplane graphs with two simplicial vertices
%J Prikladnaâ diskretnaâ matematika
%D 2015
%P 95-109
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2015_3_a7/
%G ru
%F PDM_2015_3_a7
Y. L. Nosov. Maximal outerplane graphs with two simplicial vertices. Prikladnaâ diskretnaâ matematika, no. 3 (2015), pp. 95-109. http://geodesic.mathdoc.fr/item/PDM_2015_3_a7/

[1] Chartrand G., Harary F., “Planar permutation graphs”, Ann. Inst. Henri Poincare. Sec. B, 3:4 (1967), 433–438 | MR | Zbl

[2] Harary F., Graph Theory, Perseus Books, 1994 | MR

[3] Evstigneev V. A., Kas'yanov V. N., Dictionary of Graphs in Computer Science, OOO “Sibirskoe Nauchnoe Izdatel'stvo”, Novosibirsk, 2009, 300 pp. (in Russian)

[4] Mitchel S., “Linear algorithms to recognize outerplanar and maximal outerplanar graphs”, Inform. Process. Lett., 5:1 (1979), 229–232 | DOI | MR

[5] Asratian A. S., Oksimets N., “Graphs with hamiltonian balls”, Australasian J. Combinatorics, 17:4 (1998), 185–198 | MR | Zbl

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

[7] Hedetniemi S. M., Proskurowski A. J., Syslo M. M., “Interior graphs of maximal outerplane graphs”, J. Combin. Theory. Ser. B, 38:2 (1985), 156–167 | DOI | MR | Zbl

[8] Cornelsen S., Schank T., Wagner D., “Drawing graphs on two and three lines”, J. Graphs Algorithms Appl., 8:2 (2004), 161–177 | DOI | MR | Zbl

[9] Guanzhang Hu., “Catalan number and enumeration of maximal outerplanar graphs”, Tsinghua Sci. Technol., 5:1 (2000), 109–114 | MR | Zbl

[10] Beyer T., Jones W., Mitchell S., “Linear algorithms for isomorphism of maximal outerplanar graphs”, J. ACM, 26:4 (1979), 603–610 | DOI | MR | Zbl

[11] Nosov Yu. L., “The Wiener index of maximal outerplane graphs”, Prikladnaya diskretnaya matematika, 2014, no. 4(26), 112–122 (in Russian)

[12] Markenzon L., Justel C. M., Paciornik N., “Subclasses of $k$-trees: Characterization and recognition”, Discr. Appl. Math., 154:5 (2006), 818–825 | DOI | MR | Zbl

[13] Minieka E., Optimization Algorithms for Networks and Graphs, Marcel Dekker, Inc., N.Y.–Basel, 1978, 323 pp. | MR | MR | Zbl

[14] Swamy M. N. S., Thulasiraman K., Graphs, Networks and Algorithms, Wiley, N.Y., 1981, 592 pp. | MR | Zbl

[15] Harary F., Schwenk A. J., “The number of caterpillars”, Discr. Math., 6:4 (1973), 359–365 | DOI | MR | Zbl

[16] Harary F., Schwenk A. J., “A new crossing number for bipartite graphs”, Utilitas Math., 1 (1972), 203–209 | MR | Zbl

[17] Gionfrido M., Harary F., Tuza Z., “The color cost of caterpillar”, Discr. Math., 174:1–3 (1997), 125–130 | DOI | MR

[18] Sloane N. J. A., The On-Line Encyclopedia of Integer Sequences, http://www.oeis.org/A005418