CUBO, A Mathematical Journal Vol. 23, no. 03, pp. 411–421, December 2021 DOI: 10.4067/S0719-06462021000300411 Independent partial domination L. Philo Nithya1 Joseph Varghese Kureethara1 1 Department of Mathematics, Christ University, Bengaluru, Karnataka, India. philo.nithya@res.christuniversity.in frjoseph@christuniversity.in ABSTRACT For p ∈ (0, 1], a set S ⊆ V is said to p-dominate or par- tially dominate a graph G = (V, E) if |N[S]||V | ≥ p. The minimum cardinality among all p-dominating sets is called the p-domination number and it is denoted by γp(G). Analogously, the independent partial domination (ip(G)) is introduced and studied here independently and in re- lation with the classical domination. Further, the par- tial independent set and the partial independence number βp(G) are defined and some of their properties are pre- sented. Finally, the partial domination chain is established as γp(G) ≤ ip(G) ≤ βp(G) ≤ Γp(G). RESUMEN Para p ∈ (0, 1], un conjunto S ⊆ V se dice que p- domina o parcialmente domina un grafo G = (V, E) si |N[S]| |V | ≥ p. La cardinalidad mínima entre todos los con- juntos p-dominantes se llama el número de p-dominación y se denota por γp(G). Análogamente, la dominación parcial independiente (ip(G)) es introducida y estudiada indepen- dientemente y en relación con la dominación clásica. Más aún el conjunto independiente parcial y el número de inde- pendencia parcial βp(G) se definen y se presentan algunas de sus propiedades. Finalmente, se establece la cadena de dominación partial como γp(G) ≤ ip(G) ≤ βp(G) ≤ Γp(G). Keywords and Phrases: Domination chain, independent partial dominating set, partial independent set. 2020 AMS Mathematics Subject Classification: 05C30, 05C69. Accepted: 13 September, 2021 Received: 10 November, 2020 ©2021 L. Philo Nithya et al. This open access article is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. http://cubo.ufro.cl/ http://dx.doi.org/10.4067/S0719-06462021000300411 https://orcid.org/0000-0003-4182-6231 https://orcid.org/0000-0001-5030-3948 412 L. Philo Nithya & J. Varghese Kureethara CUBO 23, 3 (2021) 1 Introduction The theory of domination is one of the profusely researched areas in graph theory. Recently a new domination parameter called partial domination number was introduced simultaneously in [3], [4] and [6], and studied in [12, 13, 14, 15]. We extend the concept of partial domination to independent domination in graphs. In [9], the concept of independent partial domination has been defined in the context of partial domination that was defined in [4]. But our work is based on the definition of partial domination in [3, 6] and we concentrate on partial domination chain. Domination addresses the issue of the number of vertices that are dominating all the vertices in a graph. As the set of all vertices of a graph dominates itself, the mathematical adventure is in finding the least number of vertices that can dominate the entire graph. This number is the domination number of a graph. Finding the domination number of a graph is a well known NP-complete decision problem [11]. In the case of large graphs with a good number of small-degree vertices, the domination number shoots up. Hence, instead of finding the dominating set that dominates the entire graph, it might be convenient to study the set of vertices that dominates the graph partially. This also could be treated as the density problem. By identifying the vertices with large degrees, we can find dense structures in the graph. The vertices that are contributing to the high density neighbourhoods are likely to dominate the major section of vertices of a graph. Hence, domination problem and its variations could also be interpreted as density problems. We follow the popular nomenclature domination and study the structures that are partially dominating a graph. Domination has been addressed in many different ways by imposing conditions on the dominating set or on its complement or on both. The relations between various domination parameters thus developed aroused mathematical curiosity. The domination chain proposed by Cockayne et al. is mathematically profound and aesthetically appealing (see Section 5). A recent survey by Bazgan et al. lists the most important results regarding the domination chain parameters [2]. In this paper, we partially address the problem raised by Case et al. in [3]. The paper is structured as follows. In Section 2, we present all the preliminary concepts required for this paper. In Section 3, we define independent partial domination number and study some of their properties. In Section 4, we explore some relations between independent dominating set and independent partial dominating set. In Section 5, we define partial independence number and investigate some of its properties which in turn lead to a part of the partial domination chain. 2 Preliminaries Let G be a simple, finite and undirected graph with V (G) as its set of vertices and E(G) as its edge set. A set S ⊆ V (G) is an independent set of vertices if no two vertices of S are adjacent to each CUBO 23, 3 (2021) Independent partial domination 413 other. An independent set S of vertices is said to be maximal if no superset T ⊃ S is independent. The maximum cardinality of an independent set in G is called its vertex independence number denoted by β(G) and the corresponding vertex set is called the β-set of G. For every vertex u in G, the set N(u) of all vertices adjacent to u is called the open neighbourhood of u. The set N(u) taken together with {u} is called the closed neighbourhood of u and is denoted by N[u]. A set D of vertices is called a dominating set of G if every vertex outside D is adjacent to at least one vertex in D. A dominating set D is minimal if no proper subset of D is a dominating set. The minimum cardinality of a minimal dominating set is called the domination number of G denoted by γ(G) and the maximum cardinality of a minimal dominating set is called the upper domination number denoted by Γ(G). If a dominating set is independent, it becomes an independent dominating set and the minimum cardinality of such a set is called the independent domination number of G denoted by i(G). For any graph G = (V, E) and proportion p ∈ (0, 1], a set S ⊆ V is a p-dominating or partial dominating set if |N[S]||V | ≥ p. The p-domination or partial domination number γp(G) equals the minimum cardinality of a p-dominating set in G. v1 v2 v3v4 v5 v6 v7 v8 v9 Figure 1: Partial domination by white vertices In the light of definitions of the neighbourhoods, it is obvious that, for a dominating set S, N[S] = V . So a partial dominating set, when compared with a dominating set, dominates a proportion ‘p’ of the vertex set, which is not necessarily the whole set and hence partially dominates G. The set of all white vertices in Figure 1 dominates exactly 4 vertices and hence is a 4 9 -dominating set. As {v7} is enough to dominate 4 vertices, γ 4 9 = 1 for the above graph. For all the other graph theoretic parameters and the notations that are used in this paper, one can refer to [11]. 3 Independent partial domination In this section, we define independent partial domination number and present some observations and some of the basic results. Since the observations are obvious, we present them without proofs. Definition 3.1. Suppose G = (V, E) is a simple graph and p ∈ (0, 1]. A subset S of V is called 414 L. Philo Nithya & J. Varghese Kureethara CUBO 23, 3 (2021) an independent p-dominating set (IPD-set) if S is a p-dominating set and is independent. Definition 3.2. The minimum cardinality of an independent p-dominating set is called the inde- pendent p-domination number (IPD-number) and is denoted by ip(G). Observations: (i) For p ∈ (0, 1], γp(G) ≤ ip(G). (ii) For any n-vertex graph G and for p ∈ (0, ∆+1 n ], ip(G) = 1. (iii) For all p ∈ (0, 1], ip(G) = 1 if and only if i(G) = 1. (iv) For p ∈ ( n−1 n , 1 ] , ip(G) = i(G). (v) For all p ∈ (0, 1], ip(G) ≤ i(G). We proceed to find the IPD-numbers of paths, cycles and complete bipartite graphs. Proposition 3.3. Suppose Pn and Cn are paths and cycles respectively on n-vertices. Then for n ≥ 3, ip(Cn) = ip(Pn) = ⌈np3 ⌉. Proof. Consider Cn for n ≥ 3. Let S be a γp-set of Cn. Then |S| = γp = ⌈np3 ⌉. If we can choose S in such a way that S is independent, then ip(Cn) = ⌈np3 ⌉. For this, consider Cn = (v1, v2, v3, ..., v3r, v3r+1, v3r+2). Here three cases arise viz., (i) n = 3r, (ii) n = 3r + 1, (iii) n = 3r + 2 where r ≥ 1. Let S1 = {v2, v5, ..., v3r−1}, S2 = {v2, v5, ..., v3r−1, v3r+1} and S3 = {v2, v5, ..., v3r−1, v3r+2}. We can see that |S1| = |S2| = |S3| = ⌈n3 ⌉ and Si is independent for 1 ≤ i ≤ 3. For cases (i), (ii) and (iii) we can choose our set of ⌈np 3 ⌉ vertices from S1, S2 and S3. Hence, ip(Cn) = ⌈np3 ⌉. This proof holds for Pn also. Proposition 3.4. For m ≤ n, ip(Km,n)=   1, for p ∈ (0, n+1 m+n ] i + 1, for p ∈ ( n+i m+n , n+(i+1) m+n ] where 1 ≤ i ≤ m − 1. Also ip(Km,n) ≤ m. Proof. Consider Km,n for m ≤ n. Let V1 = {v1, v2, ..., vm} and V2 = {u1, u2, ..., un} be the two partite sets of Km,n, where each of V1 and V2 is an independent set. Now, v1 ∈ V1 dominates n+1m+n vertices. Consequently, of the remaining m − 1 vertices in V1, each vi ∈ V1 dominates n+im+n vertices. Thus ip(Km,n) ≤ m. CUBO 23, 3 (2021) Independent partial domination 415 4 Independent domination and independent partial domina- tion Allan and Laskar described the relation between the domination number and the independent domination number of a graph in [1]. Partial domination is all about dominating a proportion p of the vertices of G. So a natural question which arises is that: whether this proportion p has any role in relating the partial domination and the original domination parameters. In this section, we do say ‘yes’ to that question by giving an upper bound for IPD-numbers in terms of p and independent domination numbers. We also give some results, which relate independent dominating sets [10] with that of partial independent dominating sets. Theorem 4.1. For any graph G with independent domination number i(G) and p ∈ (0, 1], ip(G) ≤ ⌈p.i(G)⌉. Proof. Let D = {v1, v2, ..., vi} be an i-set of G. Partition V into sets V1, V2, ..., Vi such that for each 1 ≤ j ≤ i, Vj ⊆ N[vj]. Without loss of generality, let us assume that |Vj| ≥ |Vj+1| for 1 ≤ j ≤ i. Consider D′ = {v1, v2, ..., v⌈p.i⌉}. Claim: D′ is an IPD-set of G. Proof of the Claim Our construction yields,∣∣∣∣∣∣ i⋃ j=1 Vj ∣∣∣∣∣∣ = |V | =⇒ ∣∣∣∣∣∣ ⌈p.i⌉⋃ j=1 Vj ∣∣∣∣∣∣ + ∣∣∣∣∣∣ i⋃ j=⌈p.i⌉ Vj ∣∣∣∣∣∣ = |V | =⇒ ∣∣∣⋃⌈p.i⌉j=1 Vj∣∣∣ ⌈p.i⌉ ≥ ∣∣∣⋃ij=1 Vj∣∣∣ i = |V | i∣∣∣∣∣∣ i⋃ j=1 Vj ∣∣∣∣∣∣ = |V | =⇒ ∣∣∣∣∣∣ ⌈p.i⌉⋃ j=1 Vj ∣∣∣∣∣∣ ≥ |V |.⌈p.i⌉i . Hence |N[D′]| ≥ p.|V |. We have thus proved the claim. Thus using the claim, we have ip(G) ≤ |D′| = ⌈p.i(G)⌉. Proposition 4.2. Let G be any graph with independent domination number i(G) and p ∈ (0, 1]. Then ip(G) + i1−p(G) ≤ i(G) + 1. Proof. By Theorem 5.7, ip(G) ≤ ⌈p.i⌉ < p.i + 1 and i1−p(G) ≤ ⌈(1 − p) .i⌉ < (1 − p).i + 1, then ip(G) + i1−p(G) < i + 2 ≤ i + 1. Proposition 4.3. Let S be any independent dominating set of G. If p = |N[H]||V | , for some H ⊂ S, then S − H is a 1 − p independent dominating set in G. 416 L. Philo Nithya & J. Varghese Kureethara CUBO 23, 3 (2021) Proof. It can be easily proved that, N[S] − N[H] ⊆ N[S − H]. Therefore, |N[S−H]||V | ≥ 1 − p since N[S] = V . The following result provides us with an algorithm that develops a minimal independent dominating set from a minimal IPD-set. Proposition 4.4. Every minimal IPD-set can be extended to form a minimal independent domi- nating set. Proof. Let I be a minimal IPD-set for any p ∈ (0, 1]. The following algorithm extends I to I′, a minimal independent dominating set and gives m, the cardinality of I′. Procedure 1 Algorithm to construct I′ from I Input: V (G), I, N[I], N[u]∀u ∈ V (G) − N[I] Output: I′, m 1: I′ = I, m = |I′|, M = {} 2: M = V (G) − N[I′] 3: if M = ϕ then 4: return I′, m 5: else 6: I′ = I′ ∪ {u} for any u ∈ M 7: N[I′] = N[I′] ∪ N[u] 8: m = m + 1 9: go to 2 10: end if When a graph is claw-free, it has been already proved in [1], that its domination number coincides with that of its independent domination number. We found that to be true in the context of partial domination also. Proposition 4.5. If a graph G is claw-free, then γp(G) = ip(G). Proof. Let S be a γp−set of G, for any p ∈ (0, 1]. Since G is claw-free, < N[S] > is also claw- free. Hence, γ(< N[S] >) = i(< N[S] >). This implies that γp(G) ≥ ip(G). But in general, γp(G) ≤ ip(G). Thus γp(G) = ip(G). Corollary 4.6. If L(G) is the line graph of a graph G, then γp(L(G)) = ip(L(G)). CUBO 23, 3 (2021) Independent partial domination 417 5 Partial domination chain A chain of inequalities involving domination numbers, independence numbers and irredundance numbers of the form ir(G) ≤ γ(G) ≤ i(G) ≤ β(G) ≤ Γ(G) ≤ IR(G) was first observed in 1978 (see [5]). This type of chain was observed in the case of many other domination parameters like α-domination [7] and k-dependent domination [8]. Also one of the open questions posed by Case et al. in [3] was to find out, what relationship the above parameters have amongst themselves in the context of partial domination. Hence we try to establish a similar kind of chain involving partial domination and partial independence parameters. Having already defined independent partial domination, we now define partial independence number of a graph. Definition 5.1. Suppose G = (V, E) is a graph and p ∈ (0, 1]. A set S of independent vertices is called a p-independent set in G if N[S] ⊆ V (H) for some induced subgraph H of G with |V (H)| ≥ np. A p-independent set S is said to be p-maximal if S is a maximal independent set in V (H). A maximal p-independent set S is said to be min-max p-independent set if T ⊂ S is not p-maximal. Partial independence number or p-independence number is the maximum cardinality of a min-max p-independent set and is denoted by βp(G) and the associated induced subgraph H is denoted by Hp. For the graph in Figure 1, the set of all white vertices form a β 4 9 -set. For the same graph, the set {v5, v8} is a min-max 49 -independent set, but it is not of maximum cardinality and hence is not a β 4 9 -set. 5.1 Partial independent sets This section explores some of the properties of partial independent sets, thereby proceeding towards the suggested partial domination chain. In light of the above definition, it may be noted that, for every maximal p-independent set S, N[S] = V (H) of the proposed induced subgraph H of G and hence S is a p-dominating set. Thus independent p-domination number is the minimum cardinality of a maximal p-independent set and we have the following inequality. Proposition 5.2. For p ∈ (0, 1], γp(G) ≤ ip(G) ≤ βp(G). Proposition 5.3. If p1 ≤ p2, then βp1(G) ≤ βp2(G). Proof. Let S ⊆ V be such that |S| = βp2(G). Then S is also maximal p1-independent set. Also the cardinality of every min-max p1-independent set ≤ |S|. Thus βp1(G) ≤ βp2(G). 418 L. Philo Nithya & J. Varghese Kureethara CUBO 23, 3 (2021) We now proceed to relate partial independence number βp with that of upper p-domination number, Γp which is the maximum cardinality of a minimal p-dominating set. Proposition 5.4. Every min-max p-independent set is a minimal p-dominating set. Proof. Let S be a min-max p-independent set and Hp be an induced subgraph associated with it. Then by definition, S is p-dominating in G. Suppose S is not minimal p-dominating. Then ∃ u ∈ S such that S − {u} is p-dominating. Then ∃ v ∈ S − {u}, such that uv ∈ E(H) which is a contradiction since S is an independent set. Thus S is a minimal p-dominating set. Corollary 5.5. For p ∈ (0, 1], βp(G) ≤ Γp(G). From Proposition 5.2 and Corollary 5.5 we obtain the following chain of inequalities: For p ∈ (0, 1], γp(G) ≤ ip(G) ≤ βp(G) ≤ Γp(G). We present some more properties of independent sets, which in turn lead us to a method, by which one can deduce βp-sets for some ‘p’ values from the existing β-set of a graph. Lemma 5.6. Suppose S is a β-set of a graph G and T ⊂ S. Then T is a min-max |N[T ]| n - independent set. Proof. By definition T is a maximal |N[T ]| n -independent set. It is also min-max since R ⊂ T is not |N[T ]| n maximal. Suppose R is maximal then (S−T)∪R is a dominating set which is a contradiction as S is a minimal dominating set of G. Theorem 5.7. Let Bi denote the set of all i-element subsets of a β-set of a graph G for 1 ≤ i ≤ β(G). Let Bi ∈ Bi be such that |N[Bi]| = min{|N[X]|/X ∈ Bi}. Then (i) Bi is a βp−set for p = |N[Bi]| n . (ii) For 0 < p ≤ |N[B1]| n , βp = 1 and B1 is a βp−set. Proof. For 1 ≤ i ≤ β(G) let Bi be chosen by the given method. By the previous Lemma (5.6) Bi is a min-max |N[Bi]| n independent set. Suppose Bi is not of maximum cardinality amongst all |N[Bi]| n independent sets, then for j > i there exists a Y ∈ Bj such that Y is a min-max |N[Bi]| n independent set. Also Y is min-max |N[Y ]| n independent set and thus Y is a maximal independent set in both < N[Bi] > and < N[Y ] > and also |N[Bi]| = |N[Y ]|. But by the definition of Bis, |N[Y ]| ≥ |N[Bj]| which implies that |N[Bj]| ≤ |N[Bi]| which is a contradiction since for j > i, |N[Bj]| > |N[Bi]|. CUBO 23, 3 (2021) Independent partial domination 419 Suppose |N[Bj]| ≤ |N[Bi]| for some j > i, choose R such that R ⊂ Bj and |R| = i. Then |N[R]| < |N[Bj]| which implies that |N[R]| < |N[Bi]| by our assumption. This contradicts our definition of Bi. 6 Conclusion Partial domination has a lot to promise. One of the striking features of the concept of partial domination is its nature of accommodation. Domination with conditions are studied extensively. In the case of partial domination, the imperfect situations are addressed. Hence, it is worth exploring the partial domination in all the numerous types of dominations. In this context we could establish the partial domination chain. Future beckons with great hope of the explorations of partial domination in the areas of distance domination, stratified domination, Roman domination etc., but not exclusively. Acknowledgement We thank all the referees for their reviews of this paper and their creative suggestions. 420 L. Philo Nithya & J. Varghese Kureethara CUBO 23, 3 (2021) References [1] R. B. Allan and R. Laskar, “On Domination and Independent Domination Numbers of a Graph”, Discrete Math., vol. 23, no. 2, pp. 73–76, 1978. [2] C. Bazgan, L. Brankovic, K. Casel and H. Fernau, “Domination chain: Characterisation, classical complexity, parameterised complexity and approximability”, Discrete Appl. Math., vol. 280, pp. 23–42, 2020. [3] B. M. Case, S. T. Hedetniemi, R. C. Laskar and D. J. Lipman, “Partial domination in graphs”, Congr. Numer., vol. 228, pp. 85–96, 2017. [4] Y. Caro and A. Hansberg, “Partial domination–the isolation number of a graph”, Filomat, vol. 31, no. 12, pp. 3925–3944, 2017. [5] E. J. Cockayne, S. T. Hedetniemi and D. J. Miller, “Properties of hereditary hypergraphs and middle graphs”, Canad. Math. Bull., vol. 21, no. 4, pp. 461–468, 1978. [6] A. Das, “Partial domination in graphs”, Iran. J. Sci. Technol. Trans. A Sci., vol. 43, no. 4, pp. 1713–1718, 2019. [7] J. E. Dunbar, D. G. Hoffman, R. C. Laskar and L. R. Markus, α-Domination, Discrete Math., vol. 211, no. 1–3, pp. 11–26, 2000. [8] O. Favaron, S. M. Hedetniemi, S. T. Hedetniemi and D. F. Rall, “On k-dependent domination”, Discrete Math., vol. 249, nos. 1–3, pp. 83–94, 2002. [9] O. Favaron and P. Kaemawichanurat, “Inequalities between the Kk-isolation number and the Independent Kk-isolation number of a graph”, Discrete Appl. Math., vol. 289, pp. 93–97, 2021. [10] W. Goddard and M. A. Henning, “Independent domination in graphs: a survey and recent results”, Discrete Math., vol. 313, no. 7, pp. 839–854, 2013. [11] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of domination in graphs, 464, CRC Press, Boca Raton, 1998. [12] R. D. Macapodi and R. T. Isla, “Total partial domination in graphs under some binary oper- ations”, Eur. J. Pure Appl. Math., vol. 12, no. 4, pp. 1643–1655, 2019. [13] R. D. Macapodi, R. I. Isla and S. R. Canoy, “Partial domination in the join, corona, lexi- cographic and cartesian products of graphs”, Adv. Appl. Discrete Math., vol. 20, no. 2, pp. 277–293, 2019. [14] L. P. Nithya and J. V. Kureethara, “On Some Properties of Partial Dominating Sets”, AIP Conference Proceedings, vol. 2236, no. 1, 060004, 2020. CUBO 23, 3 (2021) Independent partial domination 421 [15] L. P. Nithya and J. V. Kureethara, “Partial domination in prisms of graphs”, Ital. J. Pure Appl. Math., to be published. Introduction Preliminaries Independent partial domination Independent domination and independent partial domination Partial domination chain Partial independent sets Conclusion