Geodesic
NP-completeness of the Eulerian walk problem for a multiple graph
Modelirovanie i analiz informacionnyh sistem, Tome 31 (2024) no. 1, pp. 102-114

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

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. We prove that the recognition variant of the multiple eulerian walk problem is NP-complete. For this purpose we first prove NP-completeness of the auxiliary problem of recognising the covering trails with given endpoints in an ordinary graph.
Keywords: multiple graph, multiple path, covering trails, edge-disjoint paths, eulerian trail, eulerian cycle, NP-completeness.
Mots-clés : divisible graph 
@article{MAIS_2024_31_1_a5,
     author = {A. V. Smirnov},
     title = {NP-completeness of the {Eulerian} walk problem for a multiple graph},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {102--114},
     publisher = {mathdoc},
     volume = {31},
     number = {1},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2024_31_1_a5/}
}
TY  - JOUR
AU  - A. V. Smirnov
TI  - NP-completeness of the Eulerian walk problem for a multiple graph
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2024
SP  - 102
EP  - 114
VL  - 31
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2024_31_1_a5/
LA  - ru
ID  - MAIS_2024_31_1_a5
ER  - 
%0 Journal Article
%A A. V. Smirnov
%T NP-completeness of the Eulerian walk problem for a multiple graph
%J Modelirovanie i analiz informacionnyh sistem
%D 2024
%P 102-114
%V 31
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2024_31_1_a5/
%G ru
%F MAIS_2024_31_1_a5
A. V. Smirnov. NP-completeness of the Eulerian walk problem for a multiple graph. Modelirovanie i analiz informacionnyh sistem, Tome 31 (2024) no. 1, pp. 102-114. http://geodesic.mathdoc.fr/item/MAIS_2024_31_1_a5/