On The Cutwidth Problem Of Product Of Graphs

Graph theory is an ancient branch of mathematics, written on graph theory first appeared in the works of Euler in 1736. Nowadays the graph theory has the widespread application in chemistry, physics, biology, operations research, circuit analysis, information theory, cybernetics, economic, social sciences and other disciplines, and demonstrates the enormous superiority. At the same time, old and classic issues in graph theory (such as shortest path problem, travel vendors, chinese postman problem etc) research, promote the development of the graph theory itself.Graph labeling problem is a classic problem in graph theory, a labeling of graph G is a mapping that maps the vertex set V (G) into integer set. When we consider different requirement of the mapping, many variations of graph labelings have been evolved. The cutwidth problem is a special labeling of graphs,This problem has important applications in the very large scale integrated circuit design, circuit layout, the very large network design,etc. The cutwidth problem for general graphs has been proved to be NP-complete, so we intend to resolve it for some special graphs.The cutwidth of graph G deals with the number of edge passing over a vertex when all vertices are arranged in a path. We call it is the linear cutwidth(lcw).In this paper, based on the known n-cube and other special linear graph cut wide basis, make full use of the properties of the product graph, we prove the following results:...