Contents

-

On 4-Cutwidth Critical Trees

Zhenkun Zhang1, Yixun Lin2
1Department of Mathematics, Huanghuai University, Zhumadian 463000, China;
2Department of Mathematics, Zhengzhou University, Zhengzhou 450052, China

Abstract

Arising from the VLSI design and network communication, the cutwidth problem for a graph G is to embed G into a path such that the maximum number of overlap edges (i.e., the congestion) is minimized. The characterization of forbidden subgraphs or critical graphs is meaningful in the study of a graph-theoretic parameter. This paper characterizes the set of 4-cutwidth critical trees by twelve specified ones.