On the number of OE-trails for a fixed transition system

Бесплатный доступ

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.

Planar graph, eulerian cycle, ordered enclosing, transition system, а-trail

Короткий адрес: https://sciup.org/147158994

IDR: 147158994   |   DOI: 10.14529/mmph160101

Статья научная