Interval numbers of powers of block graphs Original Research Article

The interval number of a graph G is the minimum t such that each vertex of G can be assigned a set that is the union of at most t intervals on the real line so that distinct vertices are adjacent if and only if their corresponding sets intersect. A graph with interval number one is an interval graph. We prove that the interval number of the kth power of a block graph is at most k+1. We also characterize block graphs whose kth powers are interval graphs. Since trees are block graphs and are their own first powers, these results generalize those of Trotter and Harary that the interval number of a tree is at most two, and a tree is an interval graph if and only if it is a caterpillar.