On Bandwidth Sum Problem Of Graphs And Hypergraphs

The bandwidth sum problem of hypergraphs is a problem for many applications, which can be denned as follows. Given a hypergraph H = (E1,E2,... ,Em), where its vertex set is X with |X| = n. A bijection f : X {1,2, ...?n} is called a labelling of if. For any labelling / of H and any edge E, define f(E) = max{|f(u) -f(v)||u, v E}. The bandwisth sum / of hypergraph H is BS(H, f) =and the bandwidth sum of H is BS(H) = mm{BS(H,f)|f is a labelling of H}. The labelling minimizing BS(H) is called an optimal labelling of H. The problems studied in this paper are mainly as follows:1. The relationship between BS(H) and BS(G)As you know, the bandwidth sum prolem of graphs is a special case of the bandwidth sum problem of hypergraphs. But can we solve the bandwidth sum problem of hypergraphs in terms of the bandwidth sum problem of graphs? In this paper, we consider this problem. In Chapter 2, we give out an operation for a hypergraph H as follows: replacing every edge of H with a path, and let G denote the obtained multigraph class. Then the bandwidth sum problem of hypergraphs can be determined in terms of a special multigraph of the corresponding multigraph class. Using this, we obtain some lower bounds of the bandwidth sum problem of hypergraphs.Theorem 1 For a hypergraph H = (E1,E2,... ,Em), G is the multigraph class defined as before. Then BS(H) = min{BS{G)|G G}.Theorem 2 For any linear hypergraph H, we have BS(H) < BS{[H]2). The equality holds if and only if H is a simple graph.Theorem 3 Suppose that H* is the dual hypergraph of linear hypergraph H, L(H) is the line-graph of H and A is the maximum degree of H, then BS(H*) 2), m is the size of H. Let = max Theorem 10 Mobius ladders Mk is a cycle of length 2k with each pair of vertices at distance k apart in the cycle joined by an edge, then BS(Mk) = 9k-8. Theorem 11 For a simple hypergraph H with order n, we haveTheorem 12 Let HB(x) be a r-uniform B-star of vertex x, and B be its maximum B-degree. Then...