Independent partial domination

L. Philo Nithya; Joseph Varghese Kureethara

doi:10.4067/S0719-06462021000300411

DOI:

https://doi.org/10.4067/S0719-06462021000300411

Abstract

For \(p\in(0,1]\), a set \(S\subseteq V\) is said to \(p\)-dominate or partially dominate a graph \(G = (V, E)\) if \(\frac{|N[S]|}{|V|}\geq p\). The minimum cardinality among all \(p\)-dominating sets is called the \(p\)-domination number and it is denoted by \(\gamma_{p}(G)\). Analogously, the independent partial domination (\(i_p(G)\)) is introduced and studied here independently and in relation with the classical domination. Further, the partial independent set and the partial independence number \(\beta_p(G)\) are defined and some of their properties are presented. Finally, the partial domination chain is established as \(\gamma_p(G)\leq i_p(G)\leq \beta_p(G) \leq \Gamma_p(G)\).

Keywords

Domination chain , independent partial dominating set , partial independent set

L. Philo Nithya Department of Mathematics, Christ University, Bengaluru, Karnataka, India.
Joseph Varghese Kureethara Department of Mathematics, Christ University, Bengaluru, Karnataka, India.

Pages: 411–421
Date Published: 2021-12-01
Vol. 23 No. 3 (2021)

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.

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.

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.

Y. Caro and A. Hansberg, “Partial domination–the isolation number of a graph”, Filomat, vol. 31, no. 12, pp. 3925–3944, 2017.

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.

A. Das, “Partial domination in graphs”, Iran. J. Sci. Technol. Trans. A Sci., vol. 43, no. 4, pp. 1713–1718, 2019.

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.

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.

O. Favaron and P. Kaemawichanurat, “Inequalities between the K_k-isolation number and the Independent K_k-isolation number of a graph”, Discrete Appl. Math., vol. 289, pp. 93–97, 2021.

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.

T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of domination in graphs, 464, CRC Press, Boca Raton, 1998.

R. D. Macapodi and R. T. Isla, “Total partial domination in graphs under some binary operations”, Eur. J. Pure Appl. Math., vol. 12, no. 4, pp. 1643–1655, 2019.

R. D. Macapodi, R. I. Isla and S. R. Canoy, “Partial domination in the join, corona, lexicographic and cartesian products of graphs”, Adv. Appl. Discrete Math., vol. 20, no. 2, pp. 277–293, 2019.

L. P. Nithya and J. V. Kureethara, “On Some Properties of Partial Dominating Sets”, AIP Conference Proceedings, vol. 2236, no. 1, 060004, 2020.

L. P. Nithya and J. V. Kureethara, “Partial domination in prisms of graphs”, Ital. J. Pure Appl. Math., to be published.