0
$\begingroup$

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

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

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.

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

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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