The NLC-width and clique-width for powers of graphs of bounded tree-width

The k-power graph of a graph G is a graph with the same vertex set as G, in that two vertices are adjacent if and only if, there is a path between them in G of length at most k. A k-tree-power graph is the k-power graph of a tree, a k-leaf-power graph is the subgraph of some k-tree-power graph induced by the leaves of the tree. We show that (1) every k-tree-power graph has NLC-width at most k + 2 and clique-width at most k + 2 + maxi { left perpendicular k/2 right perpendicular - 1, 0}, (2) every k-leaf-power graph has NLC-width at most k and clique-width at most k + max{ left perpendicular k/2 right perpendicular - 2, 0}, and (3) every k-power graph of a graph of tree-width l has NLC-width at most (k + 1)(l+1) - 1, and clique-width at most 2 . (k + 1)(l+1) - 2. (C) 2008 Elsevier B.V. All rights reserved.