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


Induced subgraphs of hypercubes
Authors:Geir Agnarsson
Affiliation:Department of Mathematical Sciences, George Mason University, MS 3F2, 4400 University Drive, Fairfax, VA 22030, United States
Abstract:Let QkQk denote the kk-dimensional hypercube on 2k2k vertices. A vertex in a subgraph of QkQk is full   if its degree is kk. We apply the Kruskal–Katona Theorem to compute the maximum number of full vertices an induced subgraph on n≤2kn2k vertices of QkQk can have, as a function of kk and nn. This is then used to determine min(max(|V(H1)|,|V(H2)|))min(max(|V(H1)|,|V(H2)|)) where (i) H1H1 and H2H2 are induced subgraphs of QkQk, and (ii) together they cover all the edges of QkQk, that is E(H1)∪E(H2)=E(Qk)E(H1)E(H2)=E(Qk).
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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