article · The Electronic Journal of Combinatorics · 2026

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

Yichen Wang, Mengyu Cao, Zequn Lv, Mei Lu

Cited by 0Open access

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.

Cite this paper

APA 7

Wang, Y., Cao, M., Lv, Z., & Lu, M. (2026). Treewidth of Generalized Hamming Graph, Bipartite Kneser Graph and Generalized Petersen Graph. The Electronic Journal of Combinatorics, 33(1). https://doi.org/10.37236/12892

MLA 9

Wang, Yichen, et al. “Treewidth of Generalized Hamming Graph, Bipartite Kneser Graph and Generalized Petersen Graph.” The Electronic Journal of Combinatorics, vol. 33, no. 1, 2026, https://doi.org/10.37236/12892.

Chicago

Wang, Yichen, Mengyu Cao, Zequn Lv, and Mei Lu. 2026. “Treewidth of Generalized Hamming Graph, Bipartite Kneser Graph and Generalized Petersen Graph.” The Electronic Journal of Combinatorics 33 (1). https://doi.org/10.37236/12892.

Harvard

Wang, Y. et al. (2026) ‘Treewidth of Generalized Hamming Graph, Bipartite Kneser Graph and Generalized Petersen Graph’, The Electronic Journal of Combinatorics, 33(1). Available at: https://doi.org/10.37236/12892.

BibTeX

@article{wang2026treewidth,
  title = {{Treewidth of Generalized Hamming Graph, Bipartite Kneser Graph and Generalized Petersen Graph}},
  author = {Wang, Yichen and Cao, Mengyu and Lv, Zequn and Lu, Mei},
  journal = {The Electronic Journal of Combinatorics},
  volume = {33},
  number = {1},
  year = {2026},
  doi = {10.37236/12892}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.