Shortest paths in Sierpiński graphs

In [23], Klavžar and Milutinović (1997) proved that there exist at most two different shortest paths between any two vertices in Sierpiński graphs Skn, and showed that the number of shortest paths between any fixed pair of vertices of Skn can be computed in O(n). An almost-extreme vertex of Skn, which was introduced in Klavžar and Zemljič (2013) [27], is a vertex that is either adjacent to an extreme vertex or incident to an edge between two subgraphs of Skn isomorphic to Skn−1. In this paper, we completely determine the set Su={v∈V(Skn):there exist two shortest  u,v-paths in  Skn}, where u is any almost-extreme vertex of Skn.