Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2405.11584 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Inhaltsangabe:
- The generalized $q$-Kneser graph $K_q(n,k,t)$ for integers $k>t>0$ and $n>2k-t$ is the graph whose vertices are the $k$-dimensional subspaces of an $n$-dimensional $F_q$-vectorspace with two vertices $U_1$ and $U_2$ adjacent if and only if $\dim(U_1\cap U_2)<t$. We determine the treewidth of the generalized $q$-Kneser graphs $K_q(n,k,t)$ when $t\ge 2$ and $n$ is sufficiently large compared to $k$. The imposed bound on $n$ is a significant improvement of the previously known bound. One consequence of our results is that the treewidth of each $q$-Kneser graph $K_q(n,k,t)$ with $k>t>0$ and $n\ge 3k-t+9$ is equal to $\gauss{n}{k}-\gauss{n-t}{k-t}-1$.