Welcome to MathOverflow

Question

3

1

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

edited Apr 23 2010 at 15:30

Charles Stewart
1,669●9●15

asked Nov 1 2009 at 13:54

Rune
1,280●10●19

Harrison Brown · Accepted Answer · 2009-11-01 14:59:23Z UTC

4

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?

answered Nov 1 2009 at 14:59

Harrison Brown
7,871●1●28●77

	"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 2009 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 2009 at 16:20

Scott Morrison · Answer 2 · 2009-11-01 17:04:25Z UTC

2

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

answered Nov 1 2009 at 17:04

Scott Morrison♦
4,537●4●26●44

Emil · Answer 3 · 2009-11-01 14:49:51Z UTC

1

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

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

answered Nov 1 2009 at 14:49

Emil
422●3●11

A name for a claw-graph with paths attached to it

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.