Locally self-avoiding Eulerian circuits


Jane Tan




Thu, 07/02/2019 - 11:00am


RC-3085, The Red Centre, UNSW


 A feature of Eulerian circuits, evidenced for instance by Hierholzer's algorithm, is that in general they have many subcircuits and subcycles. We say that an Eulerian circuit is $k$-locally self-avoiding if it contains no subcycles of length $k$ or smaller. The basic problem that we consider is to determine which graphs admit a $k$-locally self-avoiding Eulerian circuit, which is of particular interest because it is closely related to path-decompositions of graphs. For $k=3$, there are some relatively broad subclasses of the Eulerian graphs that have been shown to admit such a circuit, but as soon as we look at $k = 4$ results are limited to complete and complete bipartite graphs. In this talk, I will describe a constructive proof that all but one 3-connected quartic planar graphs have 4-locally self-avoiding Eulerian circuits.

School Seminar Series: