Hierarchical, 4-connected Small-World Graph

A new sequences of graphs are introduced that mimic small-world properties. The graphs are recursively constructed but retain a fixed, regular degree. They consist of a one-dimensional lattice backbone overlayed by a hierarchical sequence of long-distance links in a pattern reminiscent of the tower-of-hanoi sequence. These 4-regular graphs are non-planar, have a diameter growing as 2$^{\sqrt{\log_{2}N^{2}}}$ (or as $\left[\log_{2}N\right]^{\alpha}$ with $\alpha\sim\sqrt{\log_{2}N^{2}}/\log_{2}\log_{2}N^{2}$), and a nontrivial phase transition T$_{c}>0$, for the Ising ferromagnet. These results suggest that these graphs are similar to small-world graphs with mean-field-like properties.