Caveman Graph


The (connected) caveman graph is a graph arising in social network theory formed by modifying a set of isolated k-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 n cliques form a single unbroken loop (Watts 1999). A number of cavemen graphs formed in this manner from K_5-e are illustrated above.

Caveman graphs are perfect.

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

See also

Small World Network, Social Network Theory

Explore with Wolfram|Alpha


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.

Referenced on Wolfram|Alpha

Caveman Graph

Cite this as:

Weisstein, Eric W. "Caveman Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications