Distances in Sierpi\'nski graphs

Sara Zemljič
Science Institute, University of Iceland

PDF

Minisymposium: GENERAL SESSION TALKS

Content: Sierpi\'nski graphs form a family of graphs which has been studied thoroughly especially due to its connections to the problem of the Tower of Hanoi puzzle. The puzzle is interesting because of several open problems, for example an optimal solution for 4 (or more) pegs. These can be linked to the state graphs of the puzzle, the Hanoi graphs. Sierpi\'nski and Hanoi graphs have a very similar structure. We are particularly interested in the metric properties of Sierpi\'nski graphs due to their close relation to optimal solutions to the Tower of Hanoi puzzle. For arbitrary two vertices of a Sierpi\'nski graph $S_p^n$, the general distance formula is given as the minimum of $p$ values. Our aim is to find a closed or a simplified distance formula. This was first done for extreme vertices and recently also for so called almost-extreme vertices. In this talk we will generalize this idea for any vertex with only two different entries (i.e., a vertex on a geodesic between two extreme vertices).

Back to all abstracts