Dual Bandwidth Of Some Graphs

The dual bandwidth of a graph G , denoted by B(G], is the maximum value of the minimum labelling variance of any two adjacent vertices in G.For a given host graphH, the dual bandwidth of embedding / for G isand the dual bandwidth of G with respect to H isThe problem is to determine the value BH(G) for given graphs G and H.Some fundamental results on dual bandwidth of graphs are given by Lin and Yuan in [11]. By [11], even the problem of deciding whether B(G) 1 is co-NP-complete. This means that the dual bandwidth problem is difficult and generally intractable for general graphs.We consider the case that the host graph H is a path in this paper. Suppose that |V(G)| = n. Then, the embedding of G in path Pn can be represented as a bijection / : V(G) {1, 2,..., n}, called a labelling of G. The dual bandwidth of labelling / for GIn this paper, the dual bandwidth of two-layer stars, uniform 2t-ary trees, equitable caterpillar, the product of two paths, the product of a path with length 2 and a cycle with length n, (m, n) caterpillars and Mbius ladder are studied. By using some known bounds for dual bandwidth and some new skills, we obtain the following main results.Theorem 2. For a tree T with n vertices and with A(T) ,nd only if T is a two-layer star such that the center of innerTheorem 3. The dual bandwidth of uniform 2i-ary tree 1 + 1 Especialy, The dual bandwidth of uniform binary treeTheorem 4. The dual bandwidth of the product of twoTheorem 5. The dual bandwidth of (m,n) caterpillar Pmn is B(Pmn) = [J.Theorem 6. The dual bandwidth of the product of a path with length 2 and a cycle with length n isTheorem 7. The dual bandwidth of Mbius ladder Theorem 8. The dual bandwidth of Petersen graph is 3.