Edge Addition Number of Cartesian Product of Paths and Cycles

Graph bandwidth problem has been studies for over forty years. The relation between the bandwidth and number of edges in the graph is always interesting. The edge addition number ad(G) of a graph is the minimum number of edges that added into the graph G which cause the resulting graph's bandwidth greater than the bandwidth of G. This paper determines the edge addition number for the Cartesian product of a path with a path, a path with a cycle and a cycle with a cycle.