Treewidth of Generalized Hamming Graph, Bipartite Kneser Graph and Generalized Petersen Graph

Source abstract

Let $t,q$ and $n$ be positive integers. Write $[q] = \{1,2,\ldots,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\ge 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)) = \Theta(tq^n/\sqrt{n})$ when $n$ goes to infinity. Based on those results, we show that the treewidth of bipartite Kneser graph $BK(n,k)$ is $\binom{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.