首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Homotopy type of neighborhood complexes of Kneser graphs, $$\varvec{KG_{2,k}}$$
Authors:Nandini Nilakantan  Anurag Singh
Institution:1.Department of Mathematics and Statistics,Indian Institute of Technology Kanpur,Kanpur,India
Abstract:Schrijver (Nieuw Archief voor Wiskunde, 26(3) (1978) 454–461) identified a family of vertex critical subgraphs of the Kneser graphs called the stable Kneser graphs \(SG_{n,k}\). Björner and de Longueville (Combinatorica 23(1) (2003) 23–34) proved that the neighborhood complex of the stable Kneser graph \(SG_{n,k}\) is homotopy equivalent to a k-sphere. In this article, we prove that the homotopy type of the neighborhood complex of the Kneser graph \(KG_{2,k}\) is a wedge of \((k+4)(k+1)+1\) spheres of dimension k. We construct a maximal subgraph \(S_{2,k}\) of \(KG_{2,k}\), whose neighborhood complex is homotopy equivalent to the neighborhood complex of \(SG_{2,k}\). Further, we prove that the neighborhood complex of \(S_{2,k}\) deformation retracts onto the neighborhood complex of \(SG_{2,k}\).
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号