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/√n)$ when $n$ goes to infinity. Based on those results, we show that the treewidth of bipartite Kneser graph $BK(n,k)$ is ${n}{k} - 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.