Star-like graphs; terminology

290 Views Asked by At

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

3

There are 3 best solutions below

2
On BEST ANSWER

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.

0
On

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

0
On

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.