The Odd Girth of the Generalised Kneser Graph

LetX={1,2,..., n}be a set ofnelements and letX(r)be the collection of all the subsets ofXcontaining preciselyrelements. Then the generalised Kneser graphK(n,r,s)(when2r-s≤n)is the graph with vertex setX(r)and edgesABforA,B∈X(r)with ‖A∩B‖≤s.Here we show that the odd girth of the generalised Kneser gr...

Full description

Saved in:
Bibliographic Details
Published in:European journal of combinatorics 1997-08, Vol.18 (6), p.607-611
Main Author: Denley, Tristan
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:LetX={1,2,..., n}be a set ofnelements and letX(r)be the collection of all the subsets ofXcontaining preciselyrelements. Then the generalised Kneser graphK(n,r,s)(when2r-s≤n)is the graph with vertex setX(r)and edgesABforA,B∈X(r)with ‖A∩B‖≤s.Here we show that the odd girth of the generalised Kneser graphK(n,r, s)is 2⌈(r − s)/[n − 2(r − s)]⌉+1 provided thatnis large enough compared withrands.
ISSN:0195-6698
1095-9971
DOI:10.1006/eujc.1996.0122