Erratum to “More Benefits of Adding Sparse Random Links to Wireless Networks: Yet Another Case for Hybrid Networks”

In the original paper, the author proposed and analyzed sparse models of random wired edge additions upon a wireless network modeled as a random geometric graph G(n, r) and proved exponential improvement to average path lengths, diameter, and mixing time for the resulting hybrid graphs G1 and G2. Experiments on algebraic connectivity were also performed to confirm the mixing time results, based on established connections between the two measures. We see no mistake in the theorems regarding diameter and average path lengths of the hybrid networks. Similarly, the experimental results do confirm the hypothesis that the hybrid networks are rapidly mixing. However, the proof for the theoretical bounds on the mixing time of hybrid networks contains a subtle error in reasoning, affecting only Section 5.1. That result was stated for a model referred to as G1 that was actually more general than G1 and G2 considered throughout the rest of the paper due to its underlying graph being an arbitrary, connected, almostregular graph rather than a random geometric graph specifically. The adversely affected statement is Corollary 26 as follows.