Secure domination in P5-free graphs
Uttam K. Gupta, Michael A. Henning, Paras Vinubhai Maniya, Dinabandhu Pradhan · Discrete Mathematics · 2025
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 P 5 -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 ( P 5 , H ) -free graph for some H ∈ { P 3 ∪ P 1 , K 2 ∪ 2 K 1 , paw , C 4 } , then γ s ( G ) ≤ max { 3 , α ( G ) } . We also show that if G is a ( P 3 ∪ P 2 ) -free graph, then γ s ( G ) ≤ α ( G ) + 1 .