| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418193 | Discrete Applied Mathematics | 2015 | 5 Pages |
Abstract
We show that the maximum number of different sizes of maximal complete kk-partite induced subgraphs of a graph GG of sufficiently large order nn is at least (n−k+1)−log2(n−k+1)−4(n−k+1)−log2(n−k+1)−4 and at most n−⌊log2(nk!)⌋. We analyze some features of the structure of graphs with the maximum possible number of different sizes of maximal independent sets, and give best-possible estimates for K1,kK1,k-free graphs and regular graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Márcia R. Cappelle, Felix Joos, Janina Müttel, Dieter Rautenbach,