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
    Commented 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
    Commented 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
    Commented Mar 29, 2015 at 17:57
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .