摘要
本文建立了Ｈａｒｐｅｒ型割宽下界估计式，由此求出了轮形图Ｗｎ、完全二部图Ｋ（ｍ，ｎ）、圈幂Ｃｎｒ、格子图：Ｐｍ×Ｐｎ、Ｐｍ×Ｃｎ、Ｃｍ×Ｃｎ以及乘积图：Ｋｍ×Ｐｎ、Ｋｍ×Ｃｎ、Ｃｍｓ×Ｃｎｒ、Ｋｍ×Ｋｎ和强乘积图Ｐｍ Ｐｎ的割宽。
In this paper,we establish Harper's lower bound on cutwidth problem and determine the cutwidths of wheel Wn,complete bipartite graph K(m,n),the r-th power of a circle on n vertices Cnr,grid graphs:Pm×Pn,Pm×Cn,Cm×Cn,graph products:Km×Pn,Km×Cn,Cms×Cnr,Km×Kn and strong graph product Pm Pn.
出处
《高校应用数学学报（A辑）》
CSCD
北大核心
1995年第3期339-348,共10页
Applied Mathematics A Journal of Chinese Universities(Ser.A)
关键词
图
标号
割宽
边割集
轮形图
Graph
Labeling
Cutwidth
Edge-cut Set.
