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.展开更多
The problem studied in this paper is to determine E(p,C),the maximum size of a connected graph G with the given vertex number p and cutwidth C. This paper presents some results on this problem.
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.展开更多
The cutwidth of a graph G is the minimum number of overlap edges when G is embedded into a path Pn.The cutwidth problem for a graph G is to determine the cutwidth of G.A graph G with cutwidth k is k-cutwidth critical ...The cutwidth of a graph G is the minimum number of overlap edges when G is embedded into a path Pn.The cutwidth problem for a graph G is to determine the cutwidth of G.A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has cutwidth less than k and G is homeomorphically minimal.In this paper,we completely investigated methods of forming a k-cutwidth(k>1)critical tree T.展开更多
基金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.
基金Supported by Natural Science Foundation of Zhejiang Province(1 0 2 0 5 5 )
文摘The problem studied in this paper is to determine E(p,C),the maximum size of a connected graph G with the given vertex number p and cutwidth C. This paper presents some results on this problem.
基金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.
基金Supported by Soft Science Foundation of Henan Province(Grant No.192400410212)the Science and Technology Key Project of Henan Province of China(Grant No.22210211008)。
文摘The cutwidth of a graph G is the minimum number of overlap edges when G is embedded into a path Pn.The cutwidth problem for a graph G is to determine the cutwidth of G.A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has cutwidth less than k and G is homeomorphically minimal.In this paper,we completely investigated methods of forming a k-cutwidth(k>1)critical tree T.
基金The project is supported by the Natural Science Foundation of Henan Province(No.082300460190)the Program for Science and Technology Innovation Talents in Universities of Henan Province(No. 2010HASTIT043)
