Binomial and \(q\)-binomial coefficient inequalities related to the hamiltonicity of the Kneser graphs and their \(q\)-analogues
type: Item
instance of: scholarly article
title: Binomial and \(q\)-binomial coefficient inequalities related to the hamiltonicity of the Kneser graphs and their \(q\)-analogues
zbMATH Open document ID: 0857.05066
author: W. Edwin Clark
author: Mourad E. H. Ismail
published in: Journal of Combinatorial Theory. Series A
publication date: 1996-11-24T00:00:00Z
review text: The \(q\)-analogue of the Kneser graph \(K(n,k)\) is the graph \(K_q(n,k)\), whose vertices are the \(k\)-subspaces of the \(n\)-dimensional vector space over the finite field with \(q\) elements and whose edges are the pairs of subspaces whose intersection is 0. It is shown that for any prime power \(q\) and for \(n\geq 2k\geq2\), the graph \(K_q(n,k)\) is hamiltonian, and in fact hamiltonian-connected. The key result in the proof is the following: If \(n\geq2k\geq2\), then \(K_q(n,k)\) is hamiltonian if \((\begin{smallmatrix} n-1\\ k-1\end{smallmatrix})_q\leq (\begin{smallmatrix} n-k\\ k\end{smallmatrix})_q\cdot q^{k^2}\), and hamiltonian-connected if the inequality is strict. The later result is analogous to the corresponding inequality that implies hamiltonicity for the Kneser graph \(K(n,q)\).
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 934992
zbMATH Keywords: \(q\)-analogue
zbMATH Keywords: Kneser graph
zbMATH Keywords: hamiltonian
zbMATH Keywords: hamiltonian-connected
zbMATH Keywords: hamiltonicity
reviewed by: Ralph Faudree
MaRDI profile type: Publication
full work available at URL: jcta.1996.0089
OpenAlex ID: W2005142167
DOI: 10.1006/JCTA.1996.0089
description: scientific article; zbMATH DE number 934992