两类图的带宽和上界

UPPER BOUNDS OF BANDWIDTH SUM OF TWO GRAPHS

设Ｇ是有ｎ个顶点的简单图．ｆ：Ｖ（Ｇ）→｛１，２，…，ｎ｝是双射．定义Ｓ（Ｇ）＝ｍｉｎＳｆ（Ｇ），其中Ｓｆ（Ｇ）＝ｕｖ∈Ｅ｜ｆ（ｕ）－ｆ（ｖ）｜，称Ｓ（Ｇ）为Ｇ的带宽和。

Let G be a simple graph with n vertices, f:V(G)→{1,2,…,n} is a 1 1 mapping. S(G)= min S f(G), where S f(G)=uv∈E|f(u)-f(v)|.S(G) is called the bandwidth sum of G . Upper bounds of bandwidth sum on tree and graph containing no triangles are reasoned out.