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 kk-locally self-avoiding if it contains no subcycles of length kk or smaller. The basic problem that we consider is to determine which graphs admit a kk-locally self-avoiding Eulerian circuit, which is of particular interest because it is closely related to path-decompositions of graphs. For k=3k=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=4k=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.
Thu, 07/02/2019 - 11:00am
RC-3085, The Red Centre, UNSW