Title | ||
---|---|---|
Binomial andQ-Binomial Coefficient Inequalities Related to the Hamiltonicity of the Kneser Graphs and TheirQ-Analogues |
Abstract | ||
---|---|---|
The Kneser graphK(n, k) has as vertices all thek-subsets of a fixedn-set and has as edges the pairs {A, B} of vertices such thatAandBare disjoint. It is known that these graphs are Hamiltonian if[formula]forn⩾2k+1. We determine asymptotically for fixedkthe minimum valuen=e(k) for which this inequality holds. In addition we give an asymptotic formula for the solution ofkΓ(n)Γ(n−2k+1)=Γ2(n−k+1) forn⩾2k+1, ask→∞, whennandkare not restricted to take integer values. We also show that for all prime powersqandn⩾2k,k⩾1, theq-analoguesKq(n, k) are Hamiltonian by consideration of the analogous inequality forq-binomial coefficients. |
Year | DOI | Venue |
---|---|---|
1996 | 10.1006/jcta.1996.0089 | Journal of Combinatorial Theory, Series A |
DocType | Volume | Issue |
Journal | 76 | 1 |
ISSN | Citations | PageRank |
0097-3165 | 4 | 0.56 |
References | Authors | |
1 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
W. Edwin Clark | 1 | 136 | 23.14 |
Mourad E. H. Ismail | 2 | 75 | 25.95 |