Path-Width and Tree-Width of the Join of Graphs

Let \(\operatorname{PW}(G)\) and \(\operatorname{TW}(G)\) denote the path-width and tree-width of a graph \(G\), respectively. Let \(G+H\) denote the join of two graphs \(G\) and \(H\). We show in this paper that

\(\operatorname{PW}(G + H) = \min\{|V(G)| + \operatorname{PW}(H),|V(H)| + \operatorname{PW}(G)\}\)

and

\(\operatorname{TW}(G + H) = \min\{|V(G)| + \operatorname{TW}(H), |V(H)| + \operatorname{TW}(G)\}\).