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