Document Type

Article

Publication Date

7-2021

Publisher

Elsevier

Source Publication

Discrete Mathematics

Source ISSN

0012-365x

Abstract

We study the problem of maximizing the number of independent sets in n-vertex k-chromatic ℓ-connected graphs. First we consider maximizing the total number of independent sets in such graphs with n sufficiently large, and for this problem we use a stability argument to find the unique extremal graph. We show that our result holds within the larger family of n-vertex k-chromatic graphs with minimum degree at least ℓ, again for n sufficiently large. We also maximize the number of independent sets of each fixed size in n-vertex 3-chromatic 2-connected graphs. We finally address maximizing the number of independent sets of size 2 (equivalently, minimizing the number of edges) over all n-vertex k-chromatic ℓ-connected graphs.

Comments

Accepted version. Discrete Mathematics, Vol. 344, No. 7 (July 2021): 112376. DOI. © 2021 Elsevier. Used with permission.

Available for download on Monday, July 10, 2023

Share

COinS