On the maximum size of resistant subgraphs in graphs with given average threshold

Abstract

Let (G,τ) be a graph together with a threshold assignment r : V(G) → N such that 1 ≤ τ (v)≤d(v), where d(v) is the degree of v in G. A proper subset M C V(G) is called r-resistant if for any vertex v M, τ (v) ≥ d(v) - dm(v) + 1, where dm(v) is the degree of v in M. Resistant subgraphs have key role in the study of (irreversible) dynamic monopolies in graphs. Denote the smallest cardinality of any r-resistant subset of G by ρ τ (G). For any positive integer s with |G| ≤ s ≤2|E(G)|, we define ρ ∗s(G) as ρ ∗s(G) = max τ:(∑v v,(G) τ (v))=s ρ τ (G). In this paper we first investigate the relationship between ρ ∗s(G) and the well-known concept defensive alliance and then we study some properties of ρ ∗s(G) as a function in s. At the end we determine ρ ∗a(Kn) for any value s and also specify the minimum resistant sets in Kn. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.