Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are some ubiquitous families of graphs — the complete graphs (or simplices) $K_n$, the circle graphs $C_n$, the path graphs $P_n$, and the hypercube graphs $Q_n$ — that intuitively seem to play a special role, not only in graph theory.

Can this intuition be made rigorous somehow, maybe by categorical means?

Observations making them "special" (but not unique):

  • They are examples of "categorical" graph properties: there is exactly one graph for every $n$. (Of course there are many, many other such families - e.g. wheels or stars -, but these are the most common ones, I guess.)

  • $K_1 = C_1 = P_1 = Q_1$
    $K_2 = C_2 = P_2 \neq Q_2$
    $K_3 = C_3 \neq P_3 \neq Q_3$
    $K_n \neq C_n \neq P_n \neq Q_n$ for $n>3$

  • They have to do with fundamental classes of topological structures: balls, tori, and euclidean spaces.

  • ADDED: They are - except for the path graphs - regular and vertex-transitive. The path graphs are at least "almost" regular (and the double-infinite path graph $\mathbb{Z}$ is even vertex-transitive).

What I am looking for is something like a categorical characterization, e.g. "being universal (= initial or terminal) objects" in some (not too) specialized graph categories.

And I'd like to learn whether there are other families of graphs of this kind (whatever "this kind" may be).

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.