Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers

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|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
add comment

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

share|improve this answer
add comment

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

http://doi.wiley.com/10.1002/jgt.20244

share|improve this answer
add comment

Your Answer

 
discard

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.