Powers of distance-hereditary graphs (Q1901030)

Powers of graphs that belong to several classes have been studied. In this paper, the authors investigate powers of distance-hereditary graphs. A connected graph \(G\) is distance-hereditary if every induced path \(H\) of \(G\) is isometric; that is, the distance of any two vertices in \(H\) equals their distance in \(G\). For \(G\) distance-hereditary, the authors obtain two types of results about the power graph \(G^k\): (1) forbidden induced subgraphs (the house, domino, cycles with 5 or more vertices, isometric \(n\)-sun for \(n\geq 4\) are forbidden) and (2) distance conditions (for example, the 4-point distance condition satisfied by distance-hereditary graphs can be relaxed). The authors devote a section to the occurrence in \(G^k\) of a particular graph---the \(m\)-fan.