Odd Yao-Yao Graphs may not be Spanners

It is a long-standing open problem whether Yao-Yao graphs \YYk\YYk\YY{k} are all spanners. Bauer and Damian~\cite{bauer2013infinite} showed that all \YY6k\YY6k\YY{6k} for k≥6k≥6k \geq 6 are spanners. Li and Zhan~\cite{li2016almost} generalized their result and proved that all even Yao-Yao graphs \YY2k\YY2k\YY{2k} are spanners (for k≥42k≥42k\geq 42). However, their technique cannot be extended to odd Yao-Yao graphs, and whether they are spanners are still elusive. In this paper, we show that, surprisingly, for any integer k≥1k≥1k \geq 1, there exist odd Yao-Yao graph \YY2k+1\YY2k+1\YY{2k+1} instances, which are not spanners.