MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I wanted to know if the following family of graphs has a name in graph theory: A claw with paths of any length attached to the three free vertices of the claw. More formally, a connected acyclic graph, with 1 vertex of degree 3 and the rest of degree 2 or less.

They're interesting because they arise in the study of graph minors. (In particular, if a graph of this type is a minor of another graph G, then it is also a subgraph of G.)

share|cite|improve this question
up vote 4 down vote accepted

I don't see any reason not to call them "subdivisions of claws," since that's exactly what they are; people working in subfactors apparently call them "star-shaped," or I guess in this case "claw-shaped." I don't know of any other name for them, though.

Now that I think about it, aren't these exactly the trees with exactly three leaves? Do trees with a specified number of leaves have a name?

share|cite|improve this answer
"Subdivisions of claws" probably seems best, since it's accurate and not confusing at all. One could call it a tree with three leaves only if you take a non-leaf as the root. If you consider one of the leaves as the root, then it has only 2 leaves. Since this is not unique, I don't think trees with a specified number of leaves have a name. – Rune Nov 1 '09 at 15:57
You could consider non-rooted trees, in which case the problem doesn't arise. But they don't seem to have a name in any case. – Harrison Brown Nov 1 '09 at 16:20

In this paper such graphs are referred to as "spiders" and "subdivisions of stars":

share|cite|improve this answer
"Spider" is indeed a standard name for a graph with at most one vertex of degree greater than 2. So Rune's graphs could be called "spiders with 3 legs" or "3-legged spiders". – Timothy Chow Mar 29 '15 at 17:57

See also the question A name for star-graph with long “laces”.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.