Treewidth of generalized Hamming graph, bipartite Kneser graph and generalized Petersen graph

Let t, q and n be positive integers. Write q = \1, 2, , q\. The generalized Hamming graph H (t, q, n) is the graph whose vertex set is the cartesian product of n copies of q (q 2), where two vertices are adjacent if their Hamming distance is at most t. In particular, H (1, q, n) is the well-known Hamming graph and H (1, 2, n) is the hypercube. In 2006, Chandran and Kavitha described the asymptotic value of tw (H (1, q, n) ), where tw (G) denotes the treewidth of G. In this paper, we give the exact pathwidth of H (t, 2, n) and show that tw (H (t, q, n) ) = (tqⁿ/n) when n goes to infinity. Based on those results, we show that the treewidth of bipartite Kneser graph BK (n, k) is nk - 1 when n is sufficient large relative to k and the bounds of tw (BK (2k+1, k) ) are given. Moreover, we present the bounds of the treewidth of generalized Petersen graph.