# Star-like graphs; terminology

By definition, an $n$-star graph, $n \geq 3$, consists of $n+1$ nodes: one node of degree $n$ and $n$ leaves. This is just the complete bipartite graph $K_{1,n}$.

Is there a name for a star-like graph where instead of leaves we allow paths of arbitrary length? In other words, a tree with exactly one node of degree $n$ and all other nodes of degree $\leq 2$.

• @bof: But this condition was explicitly in conjunction with being a tree. Aug 17 '18 at 12:42
• @HenningMakholm Oops, I missed the word "tree". Never mind!
– bof
Aug 17 '18 at 12:46

Wolfram calls them "spiders" and I also heard that name in lectures before. I don't know how well-established the notation is, but I think it's pretty intuitive.

Did you mean a finite spider graph or do you want to consider infinite "legs"? Those would still fit your definition.

Another definition in Wolfram-speech would be "tree with only one fork".

There are also caterpillar and lobster-graphs, which are also mentioned on the website.

• Perfect. Thanks!
– Jeff
Aug 17 '18 at 12:56
• Another fun name I’ve heard for these things is “octopus.” Aug 17 '18 at 16:51

I have also heard such graphs referred to as “subdivided stars”, since they can be obtained from a star by repeatedly subdividing edges.

It is interesting to me how many definitions in the field of graph theory are not universally known. If you were writing a paper, you may be asked by the referees to present a definition of "spider graph". You could also specify the graph as a spider graph, subdivided star, ect, as a tree with at most one vertex of degree strictly higher than 2. That definition is crisp and perfectly rigorous.