Partial domination of network modelling

Shumin Zhang; Tianxia Jia; Minhui Li; Shumin Zhang; Tianxia Jia; Minhui Li

doi:10.3934/math.20231235

AIMS Mathematics

2023, Volume 8, Issue 10: 24225-24232. doi: 10.3934/math.20231235

Previous Article Next Article

Research article Special Issues

Partial domination of network modelling

1.
School of Mathematics and Statistics, Qinghai Normal University, Xining 810001, China
2.
Academy of Plateau Science and Sustainability, People's Government of Qinghai Province and Beijing Normal University, China

Received: 28 March 2023 Revised: 18 July 2023 Accepted: 20 July 2023 Published: 11 August 2023
MSC : 05C07, 05C69

Partial domination was proposed in 2017 on the basis of domination theory, which has good practical application background in communication network. Let $ G = (V, E) $ be a graph and $ \mathcal{F} $ be a family of graphs, a subset $ S\subseteq V $ is called an $ \mathcal{F} $-isolating set of $ G $ if $ G[V\backslash N_G[S]] $ does not contain $ F $ as a subgraph for all $ F\in\mathcal{F} $. The subset $ S $ is called an isolating set of $ G $ if $ \mathcal{F} = \{K_2\} $ and $ G[V\backslash N_G[S]] $ does not contain $ K_2 $ as a subgraph. The isolation number of $ G $ is the minimum cardinality of an isolating set of $ G $, denoted by $ \iota(G) $. The hypercube network and $ n $-star network are the basic models for network systems, and many more complex network structures can be built from them. In this study, we obtain the sharp bounds of the isolation numbers of the hypercube network and $ n $-star network.
- partial domination,
- isolation number,
- hypercube network,
- $ n $-star network
Citation: Shumin Zhang, Tianxia Jia, Minhui Li. Partial domination of network modelling[J]. AIMS Mathematics, 2023, 8(10): 24225-24232. doi: 10.3934/math.20231235

Related Papers:

Abstract

Partial domination was proposed in 2017 on the basis of domination theory, which has good practical application background in communication network. Let $ G = (V, E) $ be a graph and $ \mathcal{F} $ be a family of graphs, a subset $ S\subseteq V $ is called an $ \mathcal{F} $-isolating set of $ G $ if $ G[V\backslash N_G[S]] $ does not contain $ F $ as a subgraph for all $ F\in\mathcal{F} $. The subset $ S $ is called an isolating set of $ G $ if $ \mathcal{F} = \{K_2\} $ and $ G[V\backslash N_G[S]] $ does not contain $ K_2 $ as a subgraph. The isolation number of $ G $ is the minimum cardinality of an isolating set of $ G $, denoted by $ \iota(G) $. The hypercube network and $ n $-star network are the basic models for network systems, and many more complex network structures can be built from them. In this study, we obtain the sharp bounds of the isolation numbers of the hypercube network and $ n $-star network.

References

[1]	D. B. West, Introduction to graph theory, 2 Eds., Upper Saddle River, NJ: Prentice Hall, 2001.
[2]	C. Berge, The theory of graphs and its applications, Paris: Dunod, 1958.
[3]	Y. Caroa, A. Hansbergb, Partial domination-the isolation number of a graph, Filomath, 31 (2017), 3925–3944. https://doi.org/10.2298/FIL1712925C doi: 10.2298/FIL1712925C
[4]	P. Borg, K. Fenech, P. Kaemawichanurat, Isolation of $k$-cliques, Discrete Math., 343 (2020), 1–7. https://doi.org/10.1016/j.disc.2020.111879 doi: 10.1016/j.disc.2020.111879
[5]	S. Tokunaga, T. Jiarasuksakun, P. Kaemawichanurat, Isolation number of maximal outerplanar graphs, Discrete Appl. Math., 267 (2019), 215–218. https://doi.org/10.1016/j.dam.2019.06.011 doi: 10.1016/j.dam.2019.06.011
[6]	P. Borg, P. Kaemawichanurat, Partial domination of maximal outerplanar graphs, Discrete Appl. Math., 283 (2020), 306–314. https://doi.org/10.1016/j.dam.2020.01.005 doi: 10.1016/j.dam.2020.01.005
[7]	P. Borg, P. Kaemawichanurat, A generalization of the Art Gallery Theorem, arXiv Press, 2020. https://doi.org/10.48550/arXiv.2002.06014
[8]	M. Lemańska, M. J. Souto-Salorio, A. Dapena, F. J. Vazquez-Araujo, Isolation number versus domination number of trees, Mathematics, 9 (2021), 1–10. https://doi.org/10.3390/math9121325 doi: 10.3390/math9121325
[9]	O. Favaron, P. Kaemawichanurat, Inequalities between the $K_k$-isolation number and the independent $K_k$-isolation number of a graph, Discrete Appl. Math., 289 (2021), 93–97. https://doi.org/10.1016/j.dam.2020.09.011 doi: 10.1016/j.dam.2020.09.011
[10]	Y. Saad, M. H. Schultz, Topological properties of hypercubes, IEEE Trans. Comput., 37 (1988), 867–872. https://doi.org/10.1109/12.2234 doi: 10.1109/12.2234
[11]	A. K. Somani, O. Peleg, On diagnosability of large fault sets in regular topology-based computer systems, IEEE Trans. Comput., 45 (1996), 892–903. https://doi.org/10.1109/12.536232 doi: 10.1109/12.536232
[12]	S. B. Akers, D. Horel, B. Krishnamurthy, The star graph: an attractive alternative to the $n$-cube, Proceedings of International Conference on Parallel Processing, 1987,393–400.
[13]	T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of domination in graphs, New York, NY: Marcel Dekker, 1998.
[14]	O. Ore, Theory of graphs, Americal Mathematial Society, Providence, 1962.
[15]	N. Alon, J. H. Spencer, The probabilistic method, 3 Eds., Hoboken, NJ, USA: Wiley, 2008.

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)