Powers of graphs are well-studied combinatorial objects; it is well-known that the cube of an undirected graph is Hamiltonian, and Fleischner's theorem states that the square of a two-connected undirected graph is also Hamiltonian, resolving a conjecture of Plummer-Nash-Williams. In this note, we prove that the $\lceil \tfrac{1}{2} \sqrt{n} \log_2^2 n \rceil^{th}$ power of a connected $n$-vertex Eulerian digraph is Hamiltonian, and provide an infinite family of digraphs for which the $\lfloor \sqrt{n}/2 \rfloor^{th}$ power is not.
@article{10_37236_11905,
author = {Enrico Col\'on and John Urschel},
title = {Hamilton powers of {Eulerian} digraphs},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {2},
doi = {10.37236/11905},
zbl = {1543.05064},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11905/}
}
TY - JOUR
AU - Enrico Colón
AU - John Urschel
TI - Hamilton powers of Eulerian digraphs
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/11905/
DO - 10.37236/11905
ID - 10_37236_11905
ER -
%0 Journal Article
%A Enrico Colón
%A John Urschel
%T Hamilton powers of Eulerian digraphs
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/11905/
%R 10.37236/11905
%F 10_37236_11905
Enrico Colón; John Urschel. Hamilton powers of Eulerian digraphs. The electronic journal of combinatorics, Tome 31 (2024) no. 2. doi: 10.37236/11905
