TOPICS
Search

Caveman Graph


CavemanGraph

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 Problem

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Caveman Graph

Cite this as:

Weisstein, Eric W. "Caveman Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CavemanGraph.html

Subject classifications