This paper presents a new family of small diameter and fixed degree interconnection networks inspired by chordal graphs and the small-world phenomenon. Whereas most small-world graphs are constructed by a random process, the proposed graphs are completely deterministic and regular. The constructions are based on linear feedback shift registers, where an underlying graph is extended by the state graph of the shift register. The resulting networks are shown to have a small diameter and fixed degree, while maintaining all of the regularity and algorithmic properties of the underlying graph. The most suitable graphs to be used for this purpose are shown to be small degree graphs such as the torus, mesh, ring and other Cartesian product graphs, which can benefit more by the introduction of additional edges since they exhibit a diameter much larger than the Moore limit .