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 74
Reads 25
Downloads 89

Abstract

Domination in graphs has been an extensively researched branch of graph theory. A set SV is said to be the dominating set of graph G if for every vV-S there exists a vertex uS such that uvE. The minimum cardinality of vertices among the dominating set of G is called the domination number of G denoted by γ(G). The main object of this paper is to study the domination number of some networks such as triangular belt networks TBn, alternate triangular belt networks ATBn and restricted square of bistar networks Bn,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 kc4-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 TBn, alternate triangular belt networks ATBn and restricted square of bistar networks Bn,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=V,E. DV is formally a dominating set of G if and only if ( vV\D) (uD) (u and v are neighbors).

Definition 2 [22]. Bistar network is the network obtained by joining the root vertices of two copies of star K1,n.

Definition 3 [23]. Alternate triangular belt network. Assume that the ladder graph Ln=Pn×P2 (n 2) has vertex sets ui and vi, where i= 1, 2,..., n. By adding the edges u2i+1v2i+2 for all i= 0, 1, 2,..., n-1 and v2iu2i+1for 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 TBn, Alternate triangular belt networks ATBn and restricted square of bistar networks Bn,n.

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

There exist a vertex uV-D such that N(u)D={V}, v is an isolated vertex in D.

Theorem 2. The domination number of triangular belt networks TBn 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: VTBn=v1,v2,v3,,vn.

Fig. 1Triangular belt networks TBn

Triangular belt networks TBn

We denoted this network’s dominating set by S={v1,v3,v5,,vn2-1}. 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.

rv1,S=0,2,4,.,n-42,

rv3,S=2,0,2,4,, n-82,

rv5,S=4,2,0,2,4,, n-122,

rvn2-1,S=i-1,i-3,i-5,, n-22-i,

rvn2+1,S=1,3,5,,n-22,

rvn2+3,S=2,1,3,5,,n-22-2,

rvn-1,S=i-32.i-72,,2,1.

Subcase 2. i is even.

rv2,S=1,1,3,., n-62,

rv4,S=3,1,1,3,,n-102,

rv6,S=5,3,1,,n-142,

rvn2-2,S=i-1,i-3,i-5,,3,1,1,

rvn2,S=i-1,i-3,i-5,,i-n-22,

rvn2+2,S=1,2,4,,i-6,i-4,

rvn2+4,S=3,1,2,4,,n-i,

rvn2+6,S=5,3,1,2,,n-i,

rvn-2,S=n-62,n-102,n-142,,1,2,

rvn,S=i2-1,i2-3,,3,1.

Case 2. k is even.

Subcase 1. i is odd.

r(v1,S)=0,2,4,.,n-22

r(v3,S)=2,0,2,4,, n-62

r(v5,S)=4,2,0,2,4,, n-102

r(vn2,S)=i-1,i-3,i-5,, n2-i

r(vn2+2,S)=1,2,4,, n2-1

rvn-2,S=i-42,i-82,,1,3,

rvn,S=i2-1,i2-3,,2,1.

Subcase 2. i is even.

rv2,S=1,1,3,.,n-42,

rv4,S=3,1,1,3,, n-82,

rv6,S=5,3,1,,n-122,

rvn2+1,S=1,3,5,, n2,

rvn2+3,S=2,1,3,5,, n-42,

rvn,S=i2-1,i2-3,,2,1.

Theorem 3. For k 4, the Alternate Triangular Belt Networks ATBn dominance number is k/2.

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

S1=(vk+3,vk+5,,v2k+1) where n/2 is odd and k2.

S2=(vk,vk+4,vk+6,,v2k+1) where n/2 is even and k3.

The proof is split into two examples for any vS that is either v in S1 or v in S2.

Case (1): If vS1.

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

So S' is not dominating set.

So chosen S in this way ensures that there is no proper subset of S dominating ATBn.

Case (2): If vS2 such that v=(vk+1,vk+4,vk+6,,v2k+1) that mean vv1; also we have always minimum one vertex of the form 2k not dominating with any vertex in S'.

So S' is not dominating set.

Hence S is minimum.

So γ(AT Bn)=S=k/2.

Lemma 1. For n 4, the domination number of restricted square of bistar graph Bn,nis 2.

We have given the dominating set of this graph as follows: S=v1 v2, S'=S-v, S is minimum, γBn,n=S= 2.

The minimality of this set is fairly easily demonstrated.

Suppose S is not minimum this suggests that there is an appropriate subset dominating Bn,n.

If vS that is either v=v1 or v=v2.

If v=v1, v=n/2, let S'=S-v we have all the vertices that adjacent to v not dominating with the vertex v2=S-v=S'.

So S' is not dominating set.

In the same way, for v=v2.

So selected S in this way guarantees that there is no proper subset of S dominating Bn,n. Sminimum, γBn,n= 2.

5. Conclusions

In this paper, we have invested by determining the dominance set of some graphs such as triangular belt networks TBn, alternate triangular belt networks ATBn and restricted square of bistar networks Bn,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

About this article

Received
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.