English

运筹学学报 ›› 2014, Vol. 18 ›› Issue (4): 105-110.

• 运筹学 • 上一篇    下一篇

图加一条边后的带宽和

林艺舒1, 刘岩1,*   

  1. 1. 华南师范大学数学科学学院, 广州 510631
  • 收稿日期:2014-05-19 出版日期:2014-12-15 发布日期:2014-12-15
  • 通讯作者: 刘岩 E-mail:liuyan@scnu.edu.cn
  • 基金资助:

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

Bandwidth sum with an edge added

LIN Yishu1, LIU Yan1,*   

  1. 1. School of Mathematical Science, South China Normal University, Guangzhou 510631, China
  • Received:2014-05-19 Online:2014-12-15 Published:2014-12-15

PDF

603

摘要： 令$BS(G,f)=\sum\limits_{uv\in E(G)}|f(u)-f(v)|$, 其中$f$为$V(G)\rightarrow\{1,2,\cdots,|V(G)|\}$的双射, 并称$BS(G)=\min\limits_{f}BS(G,f)$为图$G$的带宽和. 讨论顶点数为$n$的简单图$G$加上一条边$e\in\overline{E(G)}$后, 带宽和$BS(G+e)$与$BS(G)$的关系, 得其关系式$BS(G)+1\leq BS(G+e)\leq 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$.

关键词: 图, 图的标号, 带宽和

Abstract:  Suppose $f$ is a one-to-one mapping from $V(G)$ onto $\{1,2,\cdots,|V(G)|\}$. Let $BS(G,f)=\sum\limits_{uv\in E(G)}|f(u)-f(v)|$. The bandwidth sum of $G$, denoted by $BS(G)$, is $BS(G)=\min\limits_{f}BS(G,f)$. In this paper, we obtain the relationship between $BS(G+e)$ and $BS(G)$, where $e\in\overline{E(G)}$, $BS(G)+1\leq BS(G+e)\leq BS(G)+n-1$. We also show that these bounds are sharp.

Key words: graph, labelling, bandwidth sum

中图分类号: