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 caveman 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
].
