Mutually avoiding Eulerian circuits

Two Eulerian circuits, both starting and ending at the same vertex, are avoiding if at every other point of the circuits they are at least distance 2 apart. An Eulerian graph which admits two such avoiding circuits starting from any vertex is said to be doubly Eulerian. The motivation for this definition is that the extremal Eulerian graphs, i.e. the complete graphs on an odd number of vertices and the cycles, are not doubly Eulerian. We prove results about doubly Eulerian graphs and identify those that are the "densest" and "sparsest" in terms of the number of edges.

Authors

Institutions

Publication Details

Journal
Ars Mathematica Contemporanea
Published
2025-09-12
DOI
https://doi.org/10.26493/1855-3974.3220.12a
Primary Topic
Quantum Computing Algorithms and Architecture
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Mutually avoiding Eulerian circuits

Terry S. Griggs, Grahame Erskine, James Tuite, Robert Lewis
Ars Mathematica Contemporanea
Quantum Computing Algorithms and Architecture
article

Mutually avoiding Eulerian circuits

Terry S. Griggs, Grahame Erskine, James Tuite, Robert Lewis
article en

Abstract

Two Eulerian circuits, both starting and ending at the same vertex, are avoiding if at every other point of the circuits they are at least distance 2 apart. An Eulerian graph which admits two such avoiding circuits starting from any vertex is said to be doubly Eulerian. The motivation for this definition is that the extremal Eulerian graphs, i.e. the complete graphs on an odd number of vertices and the cycles, are not doubly Eulerian. We prove results about doubly Eulerian graphs and identify those that are the "densest" and "sparsest" in terms of the number of edges.

Ars Mathematica Contemporanea
The Open University (GB), Klaipėda University (LT)
Openalex Percentile: Top 87%
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.