Go ask the web: The Tarjan Graph
The concept of
Erdös Number parodies the prolific publication rate of
Hungarian mathematician Paul Erdös. This idea has itself been parodied
with the Tarjan Number and related concepts. It appears to be well
known among practioners of theoretical computer science.
Tarjan Graph
Form an undirected graph where the vertices are people,
and an edge connects person X to person Y if X has had sexual intercourse
with Y.
Tarjan Number
The Tarjan Number of X is the length of the
shortest path in the Tarjan Graph connecting X with Tarjan.
Tarjan Distance
The Tarjan Distance between X and Y is the length of the
shortest path in the Tarjan Graph connecting X with Y.
Open Questions
Consideration of the Tarjan Graph can generate hours of barside
conversation. My personal favourite Tarjan Graph related question
is, ``What is the size of the second largest connected component?''