两个完全图的乘积的树宽(英文)

Treewidth of the Product of Two Complete Graphs

本文确定了乘积图Km×Kn的树宽.我们的结果是,若m和n都是偶数,且m>n,或m是奇数而n是偶数,或m和n都是奇数且n>m,则Km×Kn的树宽是 TW(Km×Kn)=n(m+1)/2-1.这恰好是图Km×Kn的带宽.

We determine in this paper the treewidth of Km × Kn. Our result is that: If both m and n are even and m > n, or m is odd and n is even, or both m and n are odd and n > m, then the treewidth of Km × Kn is TW(Km×Kn)=n(m+1)/2-1. This is exactly the bandwidth of Km × Kn.