A study on partial domination in graphs

Abstract

The theory of domination is one of the most studied fields in graph theory. Many new domination parameters have been defined and studied so far. One such parame- ter that was introduced in 2017 is partial domination number. For a graph G = (V, E) and for a p and#8712; (0, 1], a subset S of V (G) is said to partially dominate or p-dominate G if |N[S]| and#8805; p|V (G)|. The cardinality of a smallest p-dominating set is called the p-domination number and it is denoted by and#947;p(G). In scenarios wherein domination con-cepts are applied, partial domination concepts can also be applied with the added ad-vantage of being able to dominate the underlying graph partially, when the need arises. This advantage makes this parameter appear unique amongst most other domination parameters. We present some basic properties of partial dominating sets, some prop- erties related to particular values of p, some properties related to the eccentricity of a p-dominating set, some results in the line of classical domination and characterization of minimal and minimum p-dominating sets. Then we study partial domination in the con-text of prisms of graphs. We give some bounds for partial domination numbers of prisms of graphs G in terms of partial domination numbers of G for particular values of p. We define universal and#947;p-fixers and universal and#947;p-doublers and we characterize paths, cycles and complete bipartite graphs which are universal and#947;1 2 - fixers and universal and#947;1 2 - dou- blers. Then we concentrate on establishing a domination chain in the context of partial domination, which we call as partial domination chain . For this, we defined indepen-dent partial domination number (IPD-number), found exact values of IPD-numbers for some classes of graphs, found bounds for IPD-numbers in terms of independent domi-nation number and some relations between the independent partial dominating sets and the independent dominating sets.