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 等数据库收录！ |
|
