2025/03/11 by Gupta, Uttam K., Henning, Michael A., Maniya, Paras Vinubhai +1
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2503.08088
A dominating set of a graph G is a set S ⊆ V(G) such that every vertex in V(G) ∖ S has a neighbor in S, where two vertices are neighbors if they are adjacent. A secure dominating set of G is a dominating set S of G with the additional property that for every vertex v ∈ V(G) ∖ S, there exists a neighbor u of v in S such that (S ∖ \u\) ∪ \v\ is a dominating set of G. The secure domination number of G, denoted by γs(G), is the minimum cardinality of a secure dominating set of G. We prove that if G is a P5-free graph, then γs(G) ≤ (3)/(2)α(G), where α(G) denotes the independence number of G. We further show that if G is a connected (P5, H)-free graph for some H ∈ \ P3 ∪ P1, K2 ∪ 2K1, ~paw,~ C4\, then γs(G)≤ max\3,α(G)\. We also show that if G is a (P3 ∪ P2)-free graph, then γs(G)≤ α(G)+1.