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.展开更多
For a graph G=(V,E) of order p, a 1-1 mapping f:V→{1,2,…,P) is called a labelling of G.Bsum(G)=minf{Σ(u,v)∈E|f(u)-f(v)|:f is a labellied of G} is called the bandwidth sum of G.In this paper, some lower bounds and ...For a graph G=(V,E) of order p, a 1-1 mapping f:V→{1,2,…,P) is called a labelling of G.Bsum(G)=minf{Σ(u,v)∈E|f(u)-f(v)|:f is a labellied of G} is called the bandwidth sum of G.In this paper, some lower bounds and upper bounds of bandwidth sums of graphs are given.展开更多
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.展开更多
设 f 表示图 G 顶点上的标号函数,定义 b(G)=min max{f(u)+f(v)|边(u,v)∈E(G)}.其中图 G 是简单、连通图。称 b(G)为 G 的和宽.期望利用 b(G)来研究带宽 B(G)。证得2B(G)≤b(G)-1及 b(G)≥p(G)+δ(G),b(G)≥△(G)+2,b(G)+b(G^C)≥2p(G)...设 f 表示图 G 顶点上的标号函数,定义 b(G)=min max{f(u)+f(v)|边(u,v)∈E(G)}.其中图 G 是简单、连通图。称 b(G)为 G 的和宽.期望利用 b(G)来研究带宽 B(G)。证得2B(G)≤b(G)-1及 b(G)≥p(G)+δ(G),b(G)≥△(G)+2,b(G)+b(G^C)≥2p(G)+2,p(G)=|V(G)|。展开更多
文摘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.
文摘For a graph G=(V,E) of order p, a 1-1 mapping f:V→{1,2,…,P) is called a labelling of G.Bsum(G)=minf{Σ(u,v)∈E|f(u)-f(v)|:f is a labellied of G} is called the bandwidth sum of G.In this paper, some lower bounds and upper bounds of bandwidth sums of graphs are given.
基金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.
文摘设 f 表示图 G 顶点上的标号函数,定义 b(G)=min max{f(u)+f(v)|边(u,v)∈E(G)}.其中图 G 是简单、连通图。称 b(G)为 G 的和宽.期望利用 b(G)来研究带宽 B(G)。证得2B(G)≤b(G)-1及 b(G)≥p(G)+δ(G),b(G)≥△(G)+2,b(G)+b(G^C)≥2p(G)+2,p(G)=|V(G)|。
