科研之友
微信
新浪微博
Facebook
分享链接
摘要
Bandwidth, cutwidth, cyclic bandwidth, bandwidth sum and cyclic bandwidth sum are well-known indices about optimal labeling of graphs applied in VLSI design,network communications, and other areas involving the graph layout. To design the graphs with the given indices, we need to study the ergodicity. Let F be a set of graphs under consideration and φ an integer-valued function defined on F, namely, φ is an index,such as bandwidth and cutwidth. If there exists a graph G ∈ F such that φ(G) = x for any integer x in the interval [a,b], where a and b are the minimum and maximum of φ on F, respectively, then φ is said to have ergodicity on F. Let Gnbe the set of simple connected graphs with order n and Tnthe set of trees with order n. In this paper, we investigate the ergodicity of bandwidth, cutwidth, cyclic bandwidth, the bandwidth sum and cyclic bandwidth sum on Tn and Gn.
- 单位
