Study On Optimal Embedding Problems

Optimal embedding (labelling) problem for graphs arises from the circuit lay- out of VLSI designs, interconnection networks, sparse matrix computations, error- correcting code designs, data structures, biology, etc, which has extensive back- grounds. Graphs studied in the dissertation are finite simple graphs. The problems which we ~are concerned in this dissertation are mainly as follows: i. Two-dimensional bandwidth problem. ii. Cyclic bandwidth sum of graphs. in. Extremal problem on bandwidth and cutwidth. 1. Two-dimensional bandwidth problem. Two-dimensional bandwidth problem was proposed by S.N. Bhatt and F.T. Leighton in 1984. F.R.K. Chung and Lin Yixun have studied this problem. Based on their work, we investigate some further problems as follows. A two-dimensional embedding of graph G is an injection f from V(G) into V(H), the vertex set of grid gr~ph H in the plane. The two-dimensional bandwidth of G, denoted by 62(G), is the minimum value of B2(G, f) over all embeddings f, where B2(G, f) is the maximum distance in H between f(u) and f(v) for adjacent vertices u, v in G. Here, the distance in H means the distance of L1-norm. When this distance is replaced by that of L~-norm, the two-dimensional bandwidth of C is denoted by /32(G). Generally speaking, the two-dimensional bandwidth problem is known to be NP-complete. Our results are mainly concerned with three aspects: (1) exact values of bandwidth for special graphs; (2) lower and upper bounds; (3) approximation algorithm. Theorem 1.1. For the wheel of n + 1 vertices, Theorem 1.2. For the Mobius ladder Mh, Theorem 1.3. For 2we have Theorem 1.4. Let m > 2, denote d = ?11. We have Theorem 1.5. Let n m> 3, we have Theorem 1.6. Let C be a connected graph, IV(G)~ >2 and V(U)I n. We haurr where Go H denotes G corona H, D(G) is the diameter of C. Theorem 1.7. For any two graphs C and H, we have 2. Cyclic bandwidth sum of graphs. The cyclic bandwidth sum problem is a combination of the cyclic bandwidth problem and the bandwidth sum problem. A cyclic embedding of C with n vertices is a bijection f from V(G) into V(C~), where C~ is a cycle of n vertices. The cychc bandwidth sum of G, denoted by BSc(G), is the minimum value of Bh拁(G, f) over all cyclic embeddings f, where BSc(G, f) stands for the sum of distances in (,, between f(u) and f(v) for adjacent vertices u, v in C. Cyclic bandwidth sum problem was proposed by Prof. Yun Jinjiang in 1995. The problem is similar to that of bandwidth sum problem. We present some lower and upper bounds for this problem. Theorem 2.1. For an optimal cyclic bandwidth sum labeling of C, if there are no edges flying over vertex v whose degree is minimum, we have where 6k(G) = min and ~5 is the minimum degree of C. Theorem 2.2. Let G be a k-connected graph, IV(G)~ = n, )E(G)~ = nz, we have Theorem 2.3. For a graph C of order n and with m edges. n ~ 1, we have Theorem 2.4. Let C be a graph with m vertices and H be a graph with n vertices, we have 3. Extremal problem on bandwidth and cutwidth. Bandwidth and cutwidth are two important concepts in graph theory. denoted by B and C, respectively. Arrange the vertices of G into a line, let the longest edges be as short as possible, this is the meaning of bandwidth. Similarly...