Eulerian circuits and path decompositions in quartic planar graphs

Jane Tan

paper

Eulerian circuits and path decompositions in quartic planar graphs

arXiv:1910.02819

Abstract

A subcycle of an Eulerian circuit is a sequence of edges that are consecutive in the circuit and form a cycle. We characterise the quartic planar graphs that admit Eulerian circuits avoiding 3-cycles and 4-cycles. From this, it follows that a quartic planar graph of order $n$ can be decomposed into $k_{1} + k_{2} + k_{3} + k_{4}$ many paths with $k_{i}$ copies of $P_{i + 1}$ , the path with $i$ edges, if and only if $k_{1} + 2 k_{2} + 3 k_{3} + 4 k_{4} = 2 n$ . In particular, every connected quartic planar graph of even order admits a $P_{5}$ -decomposition.

34 pages. Comments welcome