Published: 31 July 2024

# Finding the domination number of triangular belt networks

Sultan Almotairi1
Olayan Alharbi2
Zaid Alzaid3
M. Yasser Hausawi4
Jaber Almutairi5
Basma Mohamed6
1Department of Computer Science, Faculty of College of Computer and Information Sciences, Majmaah University, Majmaah, 11952, Saudi Arabia
2Department of Information Systems, College of Computer and Information Sciences, Majmaah University, Majmaah, 11952, Saudi Arabia
3Department of Computer Science, Faculty of Computer and Information Systems, Islamic University of Madinah, Medinah, 42351, Saudi Arabia
4IT Programs Center, Faculty of IT Department, Institute of Public Administration, Riyadh, 11141, Saudi Arabia
5Department of Computer Science, College of Computer Science and Engineering, Taibah University, Medina 42353, Saudi Arabia
6Mathematics and Computer Science Department, Faculty of Science, Menoufia University, Shebin Elkom, 32511, Egypt
Corresponding Author:
Basma Mohamed
Article in Press
Views 11

#### Abstract

Domination in graphs has been an extensively researched branch of graph theory. A set $S\subseteq V$ is said to be the dominating set of graph $G$ if for every $v\in V-S$ there exists a vertex $u\in S$ such that $uv\in E$. The minimum cardinality of vertices among the dominating set of $G$ is called the domination number of $G$ denoted by $\gamma \left(G\right)$. The main object of this paper is to study the domination number of some networks such as triangular belt networks $TB\left(n\right)$, alternate triangular belt networks $ATB\left(n\right)$ and restricted square of bistar networks ${B}_{n,n}$.

## 1. Introduction

Here, simple, finite, nontrivial, undirected, and connected graphs are all taken into consideration. The task of counting the number of dominating sets in a graph is NP-complete [1]. Domination theory has several applications in chess, security, defence strategies, and wireless communication networks [2]. Dominant sets are also important in many real-world applications, like mobile ad hoc networks and distributed computing [3].

Mohamed et al. [4] looked at the domination number of several networks, such as the linear $k{c}_{4}$-snake network, bistar network, double fan network, and twig network. In a variety of cycle-related graphs, the locating-total domination number was computed by Raza et al. [5]. Yegnanarayanan et al. [6] calculated a number of Domination values for the Rolf Nevanlinna Collaboration Graph, including Outer Connected Domination, Doubly Connected Domination, Fair Domination, and Independence Domination. The least connected dominating resolving set of graphs was heuristically calculated by Amin et al. [7] using a binary variant of the equilibrium optimisation algorithm (BEOA). Goddard et al. [8] computed two bounds on the $k$-domination number of a graph. Ahangar et al. [9] calculated a variety of constraints on the triple Roman domination number and provided precise values for a few graph families. Martnez et al. proposed new limitations on the double total domination number of graphs [10]. Consult the literature [11-20] for additional information.

In this manuscript, we introduce the domination set of some graphs such as triangular belt networks $TB\left(n\right)$, alternate triangular belt networks $ATB\left(n\right)$ and restricted square of bistar networks ${B}_{n,n}$.

## 2. Preliminary notes

Definition 1. Dominating Sets [21]: Any subset of $V$ such that any node out of $D$ is adjacent to at least one node from it is a dominant set $D$ of the graph $G=\left(V,E\right)$. $D\subseteq V$ is formally a dominating set of $G$ if and only if ($\forall v\in$$V\D$) ($\exists u\in D$) ($u$ and $v$ are neighbors).

Definition 2 [22]. Bistar network is the network obtained by joining the root vertices of two copies of star ${K}_{1,n}$.

Definition 3 [23]. Alternate triangular belt network. Assume that the ladder graph ${L}_{n}={P}_{n}×{P}_{2}$ ($n\ge$ 2) has vertex sets ${u}_{i}$ and ${v}_{i}$, where $i=$ 1, 2,..., $n$. By adding the edges ${u}_{2i+1}{v}_{2i+2}$ for all $i=$ 0, 1, 2,..., $n-$1 and ${v}_{2i}{u}_{2i+1}$for all $i=$ 1, 2,..., $n-$1 to the ladder, the Alternate Triangular Belt is formed.

## 3. Applications of domination number

One area of graph theory that has been studied in great detail is dominance in graphs. One of the fastest-growing areas of contemporary mathematics and computer science is graph theory. A number of factors have led to the development of graph theory as a rather rich and fascinating area of mathematics. Hundreds of research articles on graph theory have been published in the previous thirty years. Mathematicians have given Graph Theory considerable attention in a number of fields. Algebraic Graph Theory, Labeling of Graphs, Matching Theory, Domination Theory, and Coloring of Graphs are a few of these topics.

The theory of domination has been the core of graph theory research recently, and it has a wide range of applications in many domains, including engineering, the physical, social, and biological sciences, linguistics, etc.

Domination emerges in facility location problems, in which the number of facilities (such as fire stations and hospitals) is set and the goal is to reduce the travel time for individuals to reach the closest facility. When the maximum distance to a facility is set and one tries to reduce the number of facilities required to service everyone, a similar issue arises. Land surveying, communication or electrical network monitoring, and difficulties involving selecting groups of representatives all involve concepts from dominance [25-28].

## 4. Main results

In this section we first give the results of the special cases of Triangular belt networks $TB\left(n\right)$, Alternate triangular belt networks $ATB\left(n\right)$ and restricted square of bistar networks ${B}_{n,n}$.

Theorem 1 [24]. If and only if one of the following conditions is fulfilled for every vertex $v\in D$ in a graph $G$, then a dominating set $D$ is minimum.

There exist a vertex $u\in V-D$ such that $N\left(u\right)\cap D=\left\{V\right\}$, $v$ is an isolated vertex in $D$.

Theorem 2. The domination number of triangular belt networks $TB\left(n\right)$ is $n-k-1/2$ if $k$ is odd block and $n-k/2$ if $k$ is even block.

Proof. Let the vertices of this network indicated as: $V\left(TB\left(n\right)\right)=\left\{{v}_{1},{v}_{2},{v}_{3},\dots ,{v}_{n}\right\}$.

Fig. 1Triangular belt networks TBn

We denoted this network’s dominating set by $S=\left\{{v}_{1},{v}_{3},{v}_{5},\dots ,{v}_{\frac{n}{2}-1}\right\}$. It is evident that $n=2k+2$ is the number of vertices, where $k$ is the number of blocks in $G$.

Case 1. $k$ is odd.

Subcase 1. $i$ is odd.

$r\left({v}_{1},S\right)=\left(0,2,4,\dots .,\frac{n-4}{2}\right),$

$r\left({v}_{3},S\right)=\left(2,0,2,4,\dots ,\frac{n-8}{2}\right),$

$r\left({v}_{5},S\right)=\left(4,2,0,2,4,\dots ,\frac{n-12}{2}\right),$

$⋮$

$r\left({v}_{\frac{n}{2}-1},S\right)=\left(i-1,i-3,i-5,\dots ,\frac{n-2}{2}-i\right),$

$r\left({v}_{\frac{n}{2}+1},S\right)=\left(1,3,5,\dots ,\frac{n-2}{2}\right),$

$r\left({v}_{\frac{n}{2}+3},S\right)=\left(2,1,3,5,\dots ,\frac{n-2}{2}-2\right),$

$⋮$

$r\left({v}_{n-1},S\right)=\left(\frac{i-3}{2}.\frac{i-7}{2},\dots ,2,1\right).$

Subcase 2. $i$ is even.

$r\left({v}_{2},S\right)=\left(1,1,3,\dots .,\frac{n-6}{2}\right),$

$r\left({v}_{4},S\right)=\left(3,1,1,3,\dots ,\frac{n-10}{2}\right),$

$r\left({v}_{6},S\right)=\left(5,3,1,\dots ,\frac{n-14}{2}\right),$

$⋮$

$r\left({v}_{\frac{n}{2}-2},S\right)=\left(i-1,i-3,i-5,\dots ,3,1,1\right),$

$r\left({v}_{\frac{n}{2}},S\right)=\left(i-1,i-3,i-5,\dots ,i-\frac{n-2}{2}\right),$

$r\left({v}_{\frac{n}{2}+2},S\right)=\left(1,2,4,\dots ,i-6,i-4\right),$

$r\left({v}_{\frac{n}{2}+4},S\right)=\left(3,1,2,4,\dots ,n-i\right),$

$r\left({v}_{\frac{n}{2}+6},S\right)=\left(5,3,1,2,\dots ,n-i\right),$

$⋮$

$r\left({v}_{n-2},S\right)=\left(\frac{n-6}{2},\frac{n-10}{2},\frac{n-14}{2},\dots ,1,2\right),$

$r\left({v}_{n},S\right)=\left(\frac{i}{2}-1,\frac{i}{2}-3,\dots ,3,1\right).$

Case 2. $k$ is even.

Subcase 1. $i$ is odd.

$r\left({v}_{1},S\right)=\left(0,2,4,\dots .,\frac{n-2}{2}\right)$

$r\left({v}_{3},S\right)=\left(2,0,2,4,\dots ,\frac{n-6}{2}\right)$

$r\left({v}_{5},S\right)=\left(4,2,0,2,4,\dots ,\frac{n-10}{2}\right)$

$⋮$

$r\left({v}_{\frac{n}{2}},S\right)=\left(i-1,i-3,i-5,\dots ,\frac{n}{2}-i\right)$

$r\left({v}_{\frac{n}{2}+2},S\right)=\left(1,2,4,\dots ,\frac{n}{2}-1\right)$

$⋮$

$r\left({v}_{n-2},S\right)=\left(\frac{i-4}{2},\frac{i-8}{2},\dots ,1,3\right),$

$r\left({v}_{n},S\right)=\left(\frac{i}{2}-1,\frac{i}{2}-3,\dots ,2,1\right).$

Subcase 2. $i$ is even.

$r\left({v}_{2},S\right)=\left(1,1,3,\dots .,\frac{n-4}{2}\right),$

$r\left({v}_{4},S\right)=\left(3,1,1,3,\dots ,\frac{n-8}{2}\right),$

$r\left({v}_{6},S\right)=\left(5,3,1,\dots ,\frac{n-12}{2}\right),$

$⋮$

$r\left({v}_{\frac{n}{2}+1},S\right)=\left(1,3,5,\dots ,\frac{n}{2}\right),$

$r\left({v}_{\frac{n}{2}+3},S\right)=\left(2,1,3,5,\dots ,\frac{n-4}{2}\right),$

$⋮$

$r\left({v}_{n},S\right)=\left(\frac{i}{2}-1,\frac{i}{2}-3,\dots ,2,1\right).$

Theorem 3. For $k\ge$4, the Alternate Triangular Belt Networks $ATB\left(n\right)$ dominance number is $\left[k/2\right]$.

Initially, we provide this network’s dominating set by a set $S$ where:

${S}_{1}=\left({{v}_{k}}_{+3},{v}_{k+5},\dots ,{v}_{2k+1}\right)$ where $n/2$ is odd and $k\ge 2$.

${S}_{2}=\left({v}_{k},{v}_{k+4},{v}_{k+6},\dots ,{v}_{2k+1}\right)$ where $n/2$ is even and $k\ge 3$.

The proof is split into two examples for any $v\in S$ that is either $v$ in ${S}_{1}$ or $v$ in ${S}_{2}$.

Case (1): If $v\in {S}_{1}$.

The form 2$k$ always has at least one vertex that is not dominating with any vertex in $S\text{'}$.

So $S\text{'}$ is not dominating set.

So chosen $S$ in this way ensures that there is no proper subset of $S$ dominating $ATB\left(n\right)$.

Case (2): If $v\in {S}_{2}$ such that $v=\left({v}_{k+1},{v}_{k+4},{v}_{k+6},\dots ,{v}_{2k+1}\right)$ that mean $v\ne {v}_{1}$; also we have always minimum one vertex of the form 2$k$ not dominating with any vertex in $S\text{'}$.

So $S\text{'}$ is not dominating set.

Hence $S$ is minimum.

So $\gamma \left(AT\mathrm{}B\left(n\right)\right)=\left|S\right|=k/2$.

Lemma 1. For $n\ge$ 4, the domination number of restricted square of bistar graph ${B}_{n,n}$is 2.

We have given the dominating set of this graph as follows: $S=\left({v}_{1}{v}_{2}\right)$, $S\text{'}=S-v$, $\therefore S$ is minimum, $\gamma \left({B}_{n,n}\right)=\left|S\right|=$2.

The minimality of this set is fairly easily demonstrated.

Suppose $S$ is not minimum this suggests that there is an appropriate subset dominating ${B}_{n,n}$.

If $v\in S$ that is either $v={v}_{1}$ or $v={v}_{2}$.

If $v={v}_{1}$, $v=n/2$, let $S\text{'}=S-v$ we have all the vertices that adjacent to $v$ not dominating with the vertex ${v}_{2}=S-v=S\text{'}$.

So $S\text{'}$ is not dominating set.

In the same way, for $v={v}_{2}$.

So selected $S$ in this way guarantees that there is no proper subset of $S$ dominating ${B}_{n,n}$. $\therefore S$minimum, $\gamma \left({B}_{n,n}\right)=$ 2.

## 5. Conclusions

In this paper, we have invested by determining the dominance set of some graphs such as triangular belt networks $TB\left(n\right)$, alternate triangular belt networks $ATB\left(n\right)$ and restricted square of bistar networks ${B}_{n,n}$.

#### References

• M. R. Garey and D. S. Johnson, “Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco1979, x + 338 pp.,” Journal of Symbolic Logic, Vol. 48, No. 2, pp. 498–500, Mar. 2014, https://doi.org/10.2307/2273574
• J. L. Hurink and T. Nieberg, “Approximating minimum independent dominating sets in wireless networks,” Information Processing Letters, Vol. 109, No. 2, pp. 155–160, Dec. 2008, https://doi.org/10.1016/j.ipl.2008.09.021
• C. Cooper, R. Klasing, and M. Zito, “Lower bounds and algorithms for dominating sets in web graphs,” Internet Mathematics, Vol. 2, No. 3, pp. 275–300, Jan. 2005, https://doi.org/10.1080/15427951.2005.10129105
• B. Mohamed and M. Amin, “Domination number and secure resolving sets in cyclic networks,” Applied and Computational Mathematics, Vol. 12, No. 2, pp. 42–45, May 2023, https://doi.org/10.11648/j.acm.20231202.12
• H. Raza, N. Iqbal, H. Khan, and T. Botmart, “Computing locating-total domination number in some rotationally symmetric graphs,” Science Progress, Vol. 104, No. 4, p. 003685042110534, Nov. 2021, https://doi.org/10.1177/00368504211053417
• V. Yegnanarayanan and B. Logeshwary, “Computation of various domination numbers of Rolf Nevanlinna (RNP) collaboration graph,” Brazilian Archives of Biology and Technology, Vol. 60, Aug. 2017, https://doi.org/10.1590/1678-4324-2017160841
• B. Mohamed, L. Mohaisen, and M. Amin, “Binary equilibrium optimization algorithm for computing connected domination metric dimension problem,” Scientific Programming, Vol. 2022, pp. 1–15, Oct. 2022, https://doi.org/10.1155/2022/6076369
• E. Delaviña, W. Goddard, M. A. Henning, R. Pepper, and E. R. Vaughan, “Bounds on the k-domination number of a graph,” Applied Mathematics Letters, Vol. 24, No. 6, pp. 996–998, Jun. 2011, https://doi.org/10.1016/j.aml.2011.01.013
• H. Abdollahzadeh Ahangar, M. P. Álvarez, M. Chellali, S. M. Sheikholeslami, and J. C. Valenzuela-Tripodoro, “Triple Roman domination in graphs,” Applied Mathematics and Computation, Vol. 391, p. 125444, Feb. 2021, https://doi.org/10.1016/j.amc.2020.125444
• A. Cabrera-Martínez and F. A. Hernández-Mira, “New bounds on the double total domination number of graphs,” Bulletin of the Malaysian Mathematical Sciences Society, Vol. 45, No. 1, pp. 443–453, Oct. 2021, https://doi.org/10.1007/s40840-021-01200-0
• T. A. Ibrahim and A. A. Omran, “Upper whole domination in a graph,” Journal of Discrete Mathematical Sciences and Cryptography, Vol. 25, No. 1, pp. 73–81, Jan. 2022, https://doi.org/10.1080/09720529.2021.1939954
• W. Goddard and M. A. Henning, “Independent domination in graphs: A survey and recent results,” Discrete Mathematics, Vol. 313, No. 7, pp. 839–854, Apr. 2013, https://doi.org/10.1016/j.disc.2012.11.031
• E. Galby, P. T. Lima, and B. Ries, “Reducing the domination number of graphs via edge contractions and vertex deletions,” Discrete Mathematics, Vol. 344, No. 1, p. 112169, Jan. 2021, https://doi.org/10.1016/j.disc.2020.112169
• B. Mohamed, “A comprehensive survey on the metric dimension problem of graphs and its types,” International Journal of Theoretical and Applied Mathematics, Vol. 9, No. 1, pp. 1–5, Jul. 2023, https://doi.org/10.11648/j.ijtam.20230901.11
• B. Mohamed and M. Amin, “A hybrid optimization algorithms for solving metric dimension problem,” SSRN Electronic Journal, Vol. 15, pp. 1–10, Jan. 2023, https://doi.org/10.2139/ssrn.4504670
• B. Mohamed and M. Amin, “The metric dimension of subdivisions of lilly graph, tadpole graph and special trees,” Applied and Computational Mathematics, Vol. 12, No. 1, pp. 9–14, Mar. 2023, https://doi.org/10.11648/j.acm.20231201.12
• B. Mohamed, “Metric dimension of graphs and its application to robotic navigation,” International Journal of Computer Applications, Vol. 184, No. 15, pp. 1–3, Jun. 2022, https://doi.org/10.5120/ijca2022922090
• B. Mohamed, L. Mohaisen, and M. Amin, “Computing connected resolvability of graphs using binary enhanced Harris Hawks optimization,” Intelligent Automation and Soft Computing, Vol. 36, No. 2, pp. 2349–2361, Jan. 2023, https://doi.org/10.32604/iasc.2023.032930
• S. Almotairi, O. Alharbi, Z. Alzaid, B. Almutairi, and B. Mohamed, “The secure metric dimension of the globe graph and the flag graph,” Advances in Operations Research, Vol. 2024, No. 1, pp. 1–6, Apr. 2024, https://doi.org/10.1155/2024/3084976
• I. M. Batiha and B. Mohamed, “Binary rat swarm optimizer algorithm for computing independent domination metric dimension problem,” Mathematical Models in Engineering, Vol. 10, No. 3, Apr. 2024, https://doi.org/10.21595/mme.2024.24037
• M. Dell’Amico and J. Neto, “On total f-domination: Polyhedral and algorithmic results,” Discrete Applied Mathematics, Vol. 258, pp. 97–104, Apr. 2019, https://doi.org/10.1016/j.dam.2018.11.021
• D. Muthuramakrishnan and G. Jayaraman, “Total chromatic number of middle and total graph of path and sunlet graph,” International Journal of Scientific and Innovative Mathematical Research, Vol. 6, No. 4, pp. 1–9, Jan. 2018, https://doi.org/10.20431/2347-3142.0604001
• A. Elangovan and N. Ramya, “On prime labeling of snake graphs and triangular belt graph,” Malaya Journal of Matematik, Vol. S, No. 2, pp. 4046–4047, 2020.
• R. Jemimal Chrislight and Y. T. Sunitha Mary, “The nonsplit domination in subdivision graph,” Proyecciones (Antofagasta), Vol. 39, No. 5, pp. 1113–1120, Oct. 2020, https://doi.org/10.22199/issn.0717-6279-2020-05-0068
• C. Shi, Z. Yan, K. Lü, Z. Shi, and B. Wang, “A dominance tree and its application in evolutionary multi-objective optimization,” Information Sciences, Vol. 179, No. 20, pp. 3540–3560, Sep. 2009, https://doi.org/10.1016/j.ins.2009.06.035
• M. Mihajlov-Carević, “Dominance number on cyclooctane chains,” Vojnotehnicki Glasnik, Vol. 72, No. 1, pp. 35–55, Jan. 2024, https://doi.org/10.5937/vojtehg72-48272
• J. Lan, H. Zou, and M. Hu, “Dominance degrees for intervals and their application in multiple attribute decision-making,” Fuzzy Sets and Systems, Vol. 383, pp. 146–164, Mar. 2020, https://doi.org/10.1016/j.fss.2019.07.001
• D. Kroumi and S. Lessard, “Strong migration limit for games in structured populations: applications to dominance hierarchy and set structure,” Games, Vol. 6, No. 3, pp. 318–346, Sep. 2015, https://doi.org/10.3390/g6030318

31 May 2024
Accepted
08 July 2024
Published
31 July 2024
Keywords
dominating set
domination number
bistar network and alternate triangular belt network
Acknowledgements

The author would like to thank Deanship of Scientific Research at Majmaah University for supporting this work under project number: R-2024-1050.

Data Availability

The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.

Author Contributions

Sultan Almotairi contributed experiments and resources and wrote the initial draft of the paper. Olayan Alharbi contributed to the conceptualization, validation, and computations. Zaid Alzaid contributed by analysing the data, investigating this draft, and writing the final draft. Yasser M Hausawi contributed to methodology, validation, designing the experiments, and formal analysis. Jaber Almutairi contributed to the conceptualization, resources, computations, and analysis of the data. Basma Mohamed contributed to the conceptualization, validation, computations and analysis of the data. All authors read and approved the final version of the paper.

Conflict of interest

The authors declare that they have no conflict of interest.