Shortest paths in Sierpi?ski graphs ?
In [23], Klavar and Milutinovi? (1997) proved that there exist at most two different shortest paths between any two vertices in Sierpi?ski graphs S k n , and showed that the number of shortest paths between any fixed pair of vertices of S k n can be computed in O(n) O ( n ) . An almost-extreme vertex of S k n , which was introduced in Klavar and Zemlji? (2013) [27], is a vertex that is either adjacent to an extreme vertex or incident to an edge between two subgraphs of S k n isomorphic to S k n ? 1 . In this paper, we completely determine the set S u = { v ? V ( S k n ) : thereexisttwoshortest u , v -pathsin S k n } , where u u is any almost-extreme vertex of S k n .
shortest path sierpi?ski graph almost-extreme vertex