图加一条边后的带宽和  

Bandwidth sum with an edge added

作　　者：林艺舒 刘岩[1] 

机构地区：[1]华南师范大学数学科学学院,广州510631

出　　处：《运筹学学报》2014年第4期105-110,共6页Operations Research Transactions

基　　金：国家自然科学基金(No.11061027);广东高校国际科技合作创新平台(No.2012gjhz0007)

摘　　要：令BS(G,f)=∑|f(u)—f(v)|,其中f为V(G)→{1,2,…,|V(G)|}的双射,并称BS(G)=min BS(G,f)为图G的带宽和.讨论顶点数为n的简单图G加上一条边e∈E(G)后,带宽和BS(G+e)与BS(G)的关系,得其关系式BS(G)+1≤BS(G+e)≤BS(G)+n-1.并证明此不等式中等号可取到,即存在图G_1和G_2使得BS(G_1+e)=BS(G_1)+1,BS(G_2+e)=BS(G_2)+n-1.Suppose f is a one-to-one mapping from V（G） onto {i,2,…, ｜V（G）｜}.Let BS（G, f）=∑uv∈E（G）｜f（u） - f（v）｜. The bandwidth sum of G, denoted by BS（G）, is BS（G） = min f BS（G, f）. In this paper, we obtain the relationship between BS（G ＋ e） and BS（G）, where e ∈ E（G）, BS（G） ＋ 1 ≤BS（G ＋ e） ≤BS（G） ＋ n - 1. We also showthat these bounds are sharp.

关 键 词：图 图的标号 带宽和 

分 类 号：O157.5[理学—数学]