On the number of \(OE\)-trails for a fixed transition system. (Russian. English summary) Zbl 1336.05065

Summary: The existence of \(OE\)-trail for a plane Eulerian graph had been established earlier and algorithm of its constructing was suggested. This paper is devoted to a question of enumeration of \(OE\)-trails for a system of transitions induced by a particular \(OE\)-trail. The upper bound of this estimation does not exceed the double sum of vertices adjacent the outer face and sum of cutvertices degrees. This bound is reachable if a transition system satisfies any \(A\)-trail. The number of \(OE\)-trails for an arbitrary chosen transition system is also examined.


05C30 Enumeration in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles


[1] [1] Т. А. Панюкова, ”Оптимальные эйлеровы покрытия с упорядоченным охватыванием для плоских графов”, Дискретный анализ и исследование операций, 18:2 (2011), 64–74 · Zbl 1249.05238
[2] [2] T. A. Makarovskikh, ”The Algorithm for Constructing of Cutter Optimal Path”, Journal of Computational and Engineering Mathematics, 1:2 (2014), 52–61 · Zbl 1337.05063
[3] [3] В. Д. Фроловский, ”Автоматизация проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ”, Информационные технологии в проектировании и производстве, 2005, 4, 63–66 · Zbl 0342.02023
[4] [4] T. A. Panioukova, A. V. Panyukov, ”The Algorithm for Tracing of Flat Euler Cycles with Ordered Enclosing”, Известия Челябинского научного центра УрО РАН, 2000, 4(9), 18–22
[5] [5] H. Fleischner, Eulerian Graphs and Related Topics, v. 1, Ann. Discrete Mathematics, 45, 1990, 450 pp. · Zbl 0792.05091
[6] [6] С. Б. Белый, ”О самонепересекающихся и непересекающихся цепях”, Математические заметки, 34:4 (1983), 625–628 · Zbl 0532.05043
[7] [7] Т. А. Панюкова, ”Обходы с упорядоченным охватыванием в плоских графах”, Дискретный анализ и исследование операций. Сер. 2, 13:2 (2006), 31–43 · Zbl 1249.05370
[8] [8] Т. А. Панюкова, ”Построение эйлеровых циклов с упорядоченным охватыванием как математическая модель решения задачи раскроя”, Современные информационные технологии и ИТ-образование, Сборник избранных трудов VIII Международной научно-практической конференции, ред. В. А. Сухомлин, ИНТУИТ. РУ, М., 2013, 706–713 · Zbl 1307.35110
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.