Several Special Classes Of Graphs, Two-dimensional Bandwidth Problem

In the optimal layout problem about large scale networks, we need to embed the vertices of a guest graph to a given host graph such that some parameter of the embedding reach to minimal; we call this the optimal embedding(labeling) problem for graph. This problem arises from the circuit layout of VLSI designs, interconnection networks, sparse matrix computations, error-correcting code designs, data structures, biology, etc, which has extensive backgrounds.Graphs studied in this dissertation are finit, simple, undirected graphs. The problems we are concerned in this dissertation are mainly as follows:Two-dimensional bandwidth problem was proposed by S.N.Bhatt and F.T.Leighton in 1984. F.R.K.Chung has studied this problem. Based on their work, we investigate some further problems below.A two-dimensional embedding of graph G is an injection / from V(G) into V(H), the vertex set of grid graph H in the plane. The two-dimensional bandwidth problem of G, denoted by B₂(G), is the minimum value of B₂(G, f) over all embeddings f,where B₂(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 Li-norm, that is the rectilinear distance.Obviously, the two-dimensionsl bandwidth problem is harder than the one-dimensional one. Generally speaking, the two-dimensionsl bandwidth problem is known to be NP-complete. Our main results here are determining the precise value of some graphs.Lemma 1^[7] For a complete graph Kn of n vertices,For convenience, we denote 8(n) = minDefinition 2 A simple graph is a split graph if V(G) can be partitioned into Q and 5 such that Q is a clique and S is a independent set of G.Definition 3 is defined as follows:Definition 4 Let Ji, J₂ J₂ be n closed intervals of length unit in the real line. A graph G is called a unit interval graph, ifDefinition 5 An integer n is said to be inadequate to S(n) ifTheorem 6 Let Then if m,n are inadequate to resp.otherwise.Theorem 7 Let G = (S, Q; E) is a split graph with n vertices such that Q is a clique and S is a independent set of G. If , thenwhere Theorem 8 Let . If otherwise if t is inadequate to S(t + 1);otherwise.Corollary9 For any graph G, we have TheoremlO Let be the number of maximum clique of a unit interval graph G. ThenTheoremll Let G be a unit interval graph, then B₂(G) is equal to if and only if is not inadequate to and there exist two maximal cliques Q₁ and Q2 such that , where...