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.展开更多
The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact valu...The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact value of cutwidth of typical graphs (e.g.,n- cube,cater- pillars) .Relations between the cutwidth and other graph- theoretic parameters are studied as wel展开更多
The cutwidth problem for a graph G is to embed G into a path P n such that the maximum number of overlap edges (i.e., the congestion) is minimized. It is known that the problem for general graphs is NP-hard while it ...The cutwidth problem for a graph G is to embed G into a path P n such that the maximum number of overlap edges (i.e., the congestion) is minimized. It is known that the problem for general graphs is NP-hard while it is polynomially solvable for trees. This paper presents an exact formula for the cutwidth of trees with diameter at most 4. A relation with the bandwidth is discussed as well.展开更多
设 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 the National Natural Science Foundation of China (1 0 0 71 0 76 )
文摘The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact value of cutwidth of typical graphs (e.g.,n- cube,cater- pillars) .Relations between the cutwidth and other graph- theoretic parameters are studied as wel
基金Supported by the National Natural Science Foundation of China( 1 0 0 71 0 76)
文摘The cutwidth problem for a graph G is to embed G into a path P n such that the maximum number of overlap edges (i.e., the congestion) is minimized. It is known that the problem for general graphs is NP-hard while it is polynomially solvable for trees. This paper presents an exact formula for the cutwidth of trees with diameter at most 4. A relation with the bandwidth is discussed as well.
文摘设 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)|。
