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.
Download file
Counter downloads: 466
- Title Maximal outerplane graphs with two simplicial vertices
- Headline Maximal outerplane graphs with two simplicial vertices
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(29)
- Date:
- DOI
Keywords
максимальные внешнеплоские графы, 2-цепь, рекурсивная характеризация, непомеченные графы, полный инвариант, maximal outerplanar graphs, 2-path, enumeration, unlabeled graphs, complete invariantAuthors
References
Chartrand G. and Harary F. Planar permutation graphs // Ann. Inst. Henri Poincare, Sec. B. 1967. V. 3. No. 4. P. 433-438.
Харари Ф. Теория графов. М.: Мир, 1973. 300с.
Евстигнеев В. A., Касьянов В. Н. Словарь по графам в информатике. Новосибирск: ООО «Сибирское Научное Издательство», 2009. 300с.
Mitchel S. Linear algorithms to recognize outerplanar and maximal outerplanar graphs // Inform. Process. Lett. 1979. V. 5. No. 1. P. 229-232.
Asratian A. S. and Oksimets N. Graphs with hamiltonian balls // Australasian J. Combinatorics. 1998. V. 17. No 4. P. 185-198.
Markov M. On the vertex separation of maximal outerplanar graphs // Serdica J. Computing. 2008. V. 154. No 5. P. 207-238.
Hedetniemi S. M., Proskurowski A. J., and Syslo M. M. Interior graphs of maximal outerplane graphs // J. Combin. Theory. Ser.B. 1985. V. 38. No. 2. P. 156-167.
Cornelsen S., Schank T., and Wagner D. Drawing graphs on two and three lines // J. Graphs Algorithms Appl. 2004. V.8. No. 2. P. 161-177.
Guanzhang Hu. Catalan number and enumeration of maximal outerplanar graphs // Tsinghua Sci. Technol. 2000. V. 5. No. 1. P. 109-114.
Beyer T., Jones W., and Mitchell S. Linear algorithms for isomorphism of maximal outerplanar graphs // J. ACM. 1979. V.26. No. 4. P. 603-610.
Носов Ю.Л. Индекс Винера максимальных внешнеплоских графов // Прикладная дискретная математика. 2014. №4(26). С. 112-122.
Markenzon L., Justel C. M., and Paciornik N. Subclasses of k-trees: Characterization and recognition // Discr. Appl. Math. 2006. V. 154. No. 5. P. 818-825.
Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. 324с.
Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. 455 с.
Harary F. and Schwenk A. J. The number of caterpillars // Discr. Math. 1973. V. 6. No. 4. P. 359-365.
Harary F. and Schwenk A. J. A new crossing number for bipartite graphs // Utilitas Math. 1972. V. 1. P. 203-209.
Gionfrido M., Harary F., and Tuza Z. The color cost of caterpillar // Discr. Math. 1997. V. 174. No. 1-3. P. 125-130.
http://www.oeis.org/A005418 - Sloane N. J. A. The On-Line Encyclopedia of Integer Sequences.
Maximal outerplane graphs with two simplicial vertices | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2015. № 3(29).
Download full-text version
Counter downloads: 1006