Simplicial powers of graphs
In a graph, a vertex is simplicial if its neighborhood is a clique. For an integer k >= 1. a graph G = (V(G), E(G)) is the k-simplicial power of a graph H = (V(H), E(H)) (H a root graph of G) if V(G) is the set of all simplicial vertices of H, and for all distinct vertices x and y in V(G), xy is an element of E(G) if and only if the distance in H between x and y is at most k. This concept generalizes k-leaf powers introduced by Nishimura, Ragde and Thilikos which were motivated by the search for underlying phylogenetic trees; k-leaf powers are the k-simplicial powers of trees. Recently, a lot of work has been done on k-leaf powers and their roots as well as on their variants phylogenetic roots and Steiner roots. For k  = 6, the recognition and characterization problems of k-leaf powers are still open. Since trees and block graphs (i.e., connected graphs whose blocks are cliques) have very similar metric properties, it is natural to study k-simplicial powers of block graphs. We show that leaf powers of trees and simplicial powers of block graphs are closely related, and we study simplicial powers of other graph classes containing all trees such as ptolemaic graphs and strongly chordal graphs. (C) 2009 Elsevier B.V. All rights reserved.
simplicial powers leaf powers block graphs ptolemaic graphs strongly chordal graphs chordal graphs graph powers forbidden induced subgraph