Some polynomial subclasses of the Eulerian walk problem for a multiple graph

Abstract

In this paper, we study undirected multiple graphs of any natural multiplicity $k>1$. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of $k$ linked edges, which connect 2 or $(k+1)$ vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common end of $k$ linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of another multi-edge. We study the problem of finding the Eulerian walk (the cycle or the trail) in a multiple graph, which generalizes the classical problem for an ordinary graph. The multiple Eulerian walk problem is NP-hard. We prove the polynomiality of two subclasses of the multiple Eulerian walk problem and elaborate the polynomial algorithms. In the first subclass, we set a constraint on the ordinary edges reachability sets, which are the subsets of vertices joined by ordinary edges only. In the second subclass, we set a constraint on the quasi-vertices degrees in the graph with quasi-vertices. The structure of this ordinary graph reflects the structure of the multiple graph, and each quasi-vertex is determined by $k$ indices of the ordinary edges reachability sets, which are incident to some multi-edge.

Keywords

• multiple graph
• divisible graph
• covering trails
• edge-disjoint paths
• eulerian trail
• eulerian cycle
• graph with quasi-vertices
• ordinary edges reachability set
• polynomial subclass