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


Disjoint cliques and disjoint maximal independent sets of vertices in graphs
Authors:Paul Erdös  Arthur M Hobbs  C Payan
Institution:Hungarian Academy of Sciences, Budapest, Hungary;Dept. of Mathematics, Texas A&M University, College Station, TX 77843, USA;IRMA, BP 53 38041 Grenoble Cedex, France
Abstract:In this paper, we find lower bounds for the maximum and minimum numbers of cliques in maximal sets of pairwise disjoint cliques in a graph. By complementation, these yield lower bounds for the maximum and minimum numbers of independent sets in maximal sets of pairwise disjoint maximal independent sets of vertices in a graph. In the latter context, we show by examples that one of our bounds is best possible.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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