Bandwidth of Some Graph Products

摘要

It is known that determination problem of the bandwidth for an arbitrary graph is NP-complete. This paper establishes the bandwidth for the composition of a complete bipartite graph with other graphs; the strong product of a complete bipartite graph with a complete graph, a path, a. cycle; and the tensor product of a complete graph with a complete graph.