pith. sign in

arxiv: 1804.02259 · v1 · pith:26GVWATBnew · submitted 2018-04-06 · 🧮 math.CO

On the extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives

classification 🧮 math.CO
keywords extremalgraphsalphaboundcharacterizedegeneratedynamicincentives
0
0 comments X
read the original abstract

The famous lower bound $\alpha(G)\geq \sum_{u\in V(G)}\frac{1}{d_G(u)+1}$ on the independence number $\alpha(G)$ of a graph $G$ due to Caro and Wei is known to be tight if and only if the components of $G$ are cliques, and has been generalized several times in the context of large degenerate subsets and small dynamic monopolies. We characterize the extremal graphs for a generalization due to Ackerman, Ben-Zwi, and Wolfovitz. Furthermore, we give a simple proof of a related bound concerning partial incentives due to Cordasco, Gargano, Rescigno, and Vaccaro, and also characterize the corresponding extremal graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.