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.
The 
-caveman graph is a 
cyclic group graph.
Caveman graphs are implemented in the Wolfram Language as GraphData[
"Caveman", 
n, k
].
