Introducing 3-Path Domination in Graphs

The dominating set of a graph G is a set of vertices D such that for every v ∈ V (G) either v ∈ D or v is adjacent to a vertex in D. The domination number, denoted γ (G), is the minimum number of vertices in a dominating set. In 1998, Haynes and Slater 1 introduced paired-domination. Building on paired-domination, we introduce 3-path domination. We define a 3-path dominating set of G to be D = Q 1, Q 2, …, Q k | Q i is a 3-path such that the vertex set V (D) = V (Q 1) ∪ V (Q 2) ∪ ⋯ ∪ V (Q k) is a dominating set. We define the 3-path domination number, denoted by γ P 3 (G), to be the minimum number of 3-paths needed to dominate G. We show that the 3-path domination problem is NP-complete. We also prove bounds on γ P 3 (G) and improve those bounds for particular families of graphs such as Harary graphs, Hamiltonian graphs, and subclasses of trees. In general, we prove γ P 3 (G) ≤ n 3.