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

Treewidth of the Product of Two Complete Graphs

作　　者：原晋江[1] 罗来兴[1] 

机构地区：[1]郑州大学数学系,郑州450052

出　　处：《运筹学学报》2004年第1期62-68,共7页Operations Research Transactions

基　　金：Research supported by the Natural Science Foundation of Henan Province ; the Huo Ying Dong Education Foundation of China.

摘　　要：本文确定了乘积图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.

关 键 词：完全图 树宽 乘积图 带宽 

分 类 号：O157.5[理学—数学]