Caveman Graph

The (connected) caveman graph is a graph arising in social network theory formed by modifying a set of isolated -cliques (or "caves") by removing one edge from each clique and using it to connect to a neighboring clique along a central cycle such that all  cliques form a single unbroken loop (Watts 1999). A number of cavemen graphs formed in this manner from  are illustrated above.

Caveman graphs are perfect.

Caveman graphs will are implemented in the Wolfram Language as GraphData["Caveman", n, k].

REFERENCES

Watts, D. J. Small Worlds: The Dynamics of Networks between Order and Randomness. Princeton, NJ: Princeton University Press, 1999.

Watts, D. J. "Networks, Dynamics, and the Small-World Phenomenon." Amer. J. Soc. 105, 493-527, 1999.