图的循环带宽的Harper型下界

Harper Type Lower Bounds for the Cyclic Bandwidth of Graphs

设Ｇ为具有ｎ个顶点的图，Ｚｎ为模ｎ整数加群．从Ｇ的顶点集到Ｚｎ的任一双射ｆ称为Ｇ的一个循环标号．ｆ的循环带宽Ｂｃ（Ｇ，ｆ）定义为ｍａｘ（ｕ，ｖ）∈Ｅ（Ｇ）ｄ（ｆ（ｕ），ｆ（ｖ）），其中对任意ｘ，ｙ∈Ｚｎ，ｄ（ｘ，ｙ）＝ｍｉｎ｛｜ｘ－ｙ｜，ｎ－｜ｘ－ｙ｜｝．Ｇ的循环带宽Ｂｃ（Ｇ）是指对Ｇ的所有循环标号ｆ的循环带宽的最小值．借鉴关于带宽的已有结论，深入讨论循环带宽的Ｈａｒｐｅｒ型下界。

Let G be a graph of order n and Z n the additive group of integers modulo n . Any bijection f from the vertex set of G to Z n is called a cyclic labeling f which is defined as max (u, v)∈E(G) d(f(u), f(v)) , where d(x, y) =min {|x-y|, n-|x-y|} for x, y ∈Z n . The cyclic bandwidth of G , denoted by B c(G) , is the minimum value of B c(G, f) and is taken for all cyclic labelings f of G . Some lower bounds for the cyclic bandwidth are given and the results obtained will be helpful in the determination of the cyclic bandwidth of some special types of graph.