1
$\begingroup$

What's the name of a tree that looks like the below?

I've provided a few iterations $d = 0,1, \dotsc$, because it looks sort of fractal. The 0's are nodes, and the lines, edges.

$d=0$

0

$d=1$

  0  
  |  
0-0-0
  |  
  0   

$d = 2$

       0
       |
  0  0-0-0  0  
  |    |    |  
0-0----0----0-0
  |    |    |  
  0  0-0-0  0   
       |
       0

I was thinking of calling them "lattice trees", but after a bit of Googling, it looks like these might be called "star-like" trees, but if anyone could give a reference or a confirmation that would be nice.

The way I've constructed them is by setting the length of the maximum path in the graph to be $2d$ and then tried to have as many vertices as possible.

$\endgroup$
  • 1
    $\begingroup$ If you order the tree from the nodes of $d$ up-down, setting the center node at the top, what is doing is just adding three new nodes from each node of the previous level (except for $d=0$ where the tree add four new nodes). $\endgroup$ – Masacroso Apr 21 '17 at 6:13
  • 1
    $\begingroup$ If we were to consider the center vertex as the root, if it weren't for the fact that it had four children, I would have called it a full, complete and balanced ternary tree, or a perfect ternary tree. Every interior vertex has three children except that one. $\endgroup$ – JMoravitz Apr 21 '17 at 6:15
  • 1
    $\begingroup$ These are certainly not star-like trees, because the Wikipedia definition is violated by your last graph. There are more than one vertices with degree greater than $2$ in it. $\endgroup$ – Shraddheya Shendre Apr 21 '17 at 6:15
  • $\begingroup$ @ShraddheyaShendre Ah good to know that option has been eliminated! :) $\endgroup$ – jamesh625 Apr 21 '17 at 6:38
  • $\begingroup$ They look like the balls of radius $d$ about the identity, in the Cayley graph of the free group on 2 generators. The wiki page for the free group has this as its first image. You could equivalently consider these as balls of radius $d$ in the infinite 4-valent tree. $\endgroup$ – Joppy Apr 21 '17 at 6:58

Your Answer

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

Browse other questions tagged or ask your own question.