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 .