高校应用数学学报B辑
高校應用數學學報B輯
고교응용수학학보B집
APPLIED MATHEMATICS A JOURNAL OF CHINESE UNIVERSITIES
2002年
2期
125-134
,共10页
combinatorial optimization%graph labeling%cutwidth%bandwidth
The cutwidth problem for a graph G is to embed G into a path such that the maximum number of overlap edges is minimized. This paper presents an approach based on the degree sequence of G for determining the exact value of cutwidth of typical graphs (e.g., n-cube,caterpillars). Relations between the cutwidth and other graph-theoretic parameters are studied as well.