4
$\begingroup$

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.)

Improve this question
$\endgroup$

3 Answers 3

Reset to default
4
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • $\begingroup$ "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. $\endgroup$
    – Rune
    Nov 1, 2009 at 15:57
  • $\begingroup$ 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. $\endgroup$
    – Harrison Brown
    Nov 1, 2009 at 16:20
2
$\begingroup$

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

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ "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". $\endgroup$
    – Timothy Chow
    Mar 29, 2015 at 17:57
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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