Details

Autor(en) / Beteiligte

• Gurski, Frank
• Wanke, Egon

Titel

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

Ist Teil von

• Discrete Applied Mathematics, 2009-02, Vol.157 (4), p.583-595

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

2009

Link zum Volltext

Quelle

EZB Electronic Journals Library

Beschreibungen/Notizen

• 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 + max { ⌊ k 2 ⌋ − 1 , 0 } , (2) every k -leaf-power graph has NLC-width at most k and clique-width at most k + max { ⌊ k 2 ⌋ − 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 .