Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bound...Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bounds on cyclic bandwidth sum of graphs are studied.展开更多
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 layo...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.展开更多
文摘Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bounds on cyclic bandwidth sum of graphs are studied.
基金Supported by Science and Technology Program of Guangzhou(Grant No.202002030183)Natural Science Foundation of Guangdong(Grant No.2021A1515012045)+1 种基金National Natural Science Foundation of China(Grant No.12161073)Natural Science Foundation of Qinghai(Grant No.2020-ZJ-924)。
文摘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.
