Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2602.15220 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915801346342912 |
|---|---|
| author | Stawiski, Marcin |
| author_facet | Stawiski, Marcin |
| contents | Let $G$ be a graph, and $H$ be a finite subgraph of $G$. We say that $H$ is a (semi) $S$-Eulerian subgraph if there exists a closed (open) trail $T$ in $G$ such that each edge of $H$ appears in $T$. We show that the problem of determining whether a subgraph $H$ of a finite graph $G$ is (semi) $S$-Eulerian is NP-Complete. Moreover, we show that both versions of the problem become linear in time if we restrict ourselves to connected subgraphs $H$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_15220 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A new problem related to Eulerian graphs Stawiski, Marcin Combinatorics Let $G$ be a graph, and $H$ be a finite subgraph of $G$. We say that $H$ is a (semi) $S$-Eulerian subgraph if there exists a closed (open) trail $T$ in $G$ such that each edge of $H$ appears in $T$. We show that the problem of determining whether a subgraph $H$ of a finite graph $G$ is (semi) $S$-Eulerian is NP-Complete. Moreover, we show that both versions of the problem become linear in time if we restrict ourselves to connected subgraphs $H$. |
| title | A new problem related to Eulerian graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2602.15220 |