Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419733 | Discrete Applied Mathematics | 2009 | 13 Pages |
Abstract
The kk-power graph of a graph GG is a graph with the same vertex set as GG, in that two vertices are adjacent if and only if, there is a path between them in GG of length at most kk. A kk-tree-power graph is the kk-power graph of a tree, a kk-leaf-power graph is the subgraph of some kk-tree-power graph induced by the leaves of the tree.We show that (1) every kk-tree-power graph has NLC-width at most k+2k+2 and clique-width at most k+2+max{⌊k2⌋−1,0}, (2) every kk-leaf-power graph has NLC-width at most kk and clique-width at most k+max{⌊k2⌋−2,0}, and (3) every kk-power graph of a graph of tree-width ll has NLC-width at most (k+1)l+1−1(k+1)l+1−1, and clique-width at most 2⋅(k+1)l+1−22⋅(k+1)l+1−2.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Frank Gurski, Egon Wanke,