Odd Yao-Yao Graphs are Not Spanners

Abstract

It is a long standing open problem whether Yao-Yao graphs ${\mathsf{YY}}_k$ are all spanners [li2002sparse]. Bauer and Damian [bauer2013infinite] showed that all ${\mathsf{YY}}_{6k}$ for $k\ge 6$ are spanners. Li and Zhan [li2016almost] generalized their result and proved that all even Yao-Yao graphs ${\mathsf{YY}}_{2k}$ are spanners (for $k\ge 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\ge 1$, there exist odd Yao-Yao graph ${\mathsf{YY}}_{2k+1}$ instances, which are not spanners.

29 pages, 26 figures

References in corpus (2)

• Beta-Skeletons have Unbounded Dilation
• A Simple Yao-Yao-Based Spanner of Bounded Degree