Research Article | | Peer-Reviewed

Some New Results on Domination and Independent Dominating Set of Some Graphs

Received: 22 February 2024     Accepted: 12 March 2024     Published: 10 May 2024
Views:       Downloads:
Abstract

One area of graph theory that has been studied in great detail is dominance in graphs. Applications for dominating sets are numerous. In wireless networking, dominant sets are used to find effective paths inside ad hoc mobile networks. They have also been used in the creation of document summaries and safe electrical grid systems. A set SV is said to be dominating set of G if for every v є V-S there exists a vertex u є S such that uv є E. The dominance number of G, represented by γ(G), is the lowest cardinality of vertices among the dominating set of G. A classic NP-complete decision problem in computational complexity theory determines whether, given a graph G and input K, γ(G) ≤ K. This is known as the dominating set issue. Consequently, it is thought that calculating γ(G) for each given graph G may not be possible to do with a feasible algorithm. In addition to efficient approximation tactics, there exist efficient exact techniques for various graph classes. If there are no neighboring vertices in a subset S, then SV is an independent set. Additionally, the empty set and the subset with just one vertex are independent. An independent dominating set of G is a set S of vertices in a graph G that is both an independent and a dominating set of G. This paper's primary goal is to investigate the dominance and independent dominating set of many graphs, including the line graph, the alternate triangular belt graph, the bistar graph, the triangular snake graph, and others.

Published in Applied and Computational Mathematics (Volume 13, Issue 3)
DOI 10.11648/j.acm.20241303.11
Page(s) 53-57
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Dominating Set, Domination Number, Triangular Snake Graph, Bistar Graph, Alternate Triangular Belt Graph, Line Graph, Crystal Planar Map, k-kite Chains Graph, Jewel Graph

1. Introduction
All graphs considered here are simple, finite, nontrivial, undirected and connected. The problem of counting the number of independent sets in a graph is NP-complete (see for instance Roth ). However, for certain types of graphs, the problem of determining their number of independent subsets is polynomial.
Many applications of domination theory in wireless communication networks . Also dominating sets play an important role in much practical application, for example in the context of distributed computing or mobile ad-hoc networks . An independent dominating set of G is a set that is both dominating and independent in G. The independent domination number of G, denoted by i(G), is the minimum cardinality of an independent dominating set. The independence number of G, denoted by α(G), is the maximum cardinality of an independent set in G. In particular,
γGiGαG.
An independent dominating set of G of cardinality i(G) is called an i(G)-set. The concept of independent domination originated in chessboard problems, and elementary properties were provided by Berge , while the parameter was defined by Hedetniemi et al. .
Haviland (2008a) investigated the maximum value of i(G) when G is triangle-free. Let M(n,δ) denote this maximum as a function of the order n and the minimum degree δ. Goddard and Henning provided the independent domination numbers of paths and cycles. Roongrat Samanmoo et al. presented the γindependent dominating graphs of all paths and all cycles. Nagy studied the existence and the number of k-dominating independent sets in certain graph families. Laforest et al. presented a new approach to solve the minimum independent dominating set problem in general graphs which is one of the hardest optimization problem. Sikhwal et al. studied the domination numbers of graph containing vertex disjoint cycles with some identities of domination set and independent set and presented some identities related to domination number, upper domination number, Independence number and independent domination number of graphs containing vertex disjoint cycles. Shaheen calculated the independent domination number of the Cartesian product of two directed paths Pm and Pn for arbitraries m and n and determined the independent domination number of the Cartesian product of two directed cycles Cm and Cn for m, n ≡ 0 (mod 3) and n ≡ 0 (mod m). Further information might be found in the literature .
In this paper we study the domination and independent dominating set of some graphs such as Triangular snake graph, Bistar graph, Alternate triangular belt graph, line graph and etc.
2. Preliminary Notes
Definition 2.1. Bistar graph is the graph obtained by joining the root vertices of two copies of star 𝐾1,
Definition 2.2. Alternate triangular belt graph
Let Ln=Pn × P2 (n ≥ 2) be the ladder graph with vertex set ui and vi, i = 1, 2,..., n. The Alternate Triangular Belt is obtained from the ladder by adding the edges u2i+1 v2i+2 for all i = 0, 1, 2,..., n − 1 and v2i u2i+1 for all i = 1, 2,..., n − 1. This graph is denoted by ATB (n).
Definition 2.3. Line graph is the graph whose vertex set is V(G)⋃ E(G) and two vertices are adjacent whenever they are either adjacent or incident in G. This graph is denoted by T(G).
Definition 2.4. The jewel graph 𝐽𝑛 is the graph with the vertex set (𝐽𝑛) = {𝑢, 𝑣, 𝑥, 𝑦, 𝑢𝑖: 1 ≤ 𝑖 ≤ 𝑛} and the edge set 𝐸 (𝐽𝑛) = {𝑢𝑥, 𝑢𝑦, 𝑥𝑦, 𝑥𝑣, 𝑦𝑣, 𝑢𝑢𝑖, 𝑣𝑢𝑖: 1 ≤ 𝑖 ≤ 𝑛}.
3. On Domination Numbers of Some Graphs
The outcomes of the special cases of the triangular snake, double triangular snake, and alternate triangular belt are presented first in this section.
Theorem (1): ()
A dominating set D of a graph G is minimal if and only if for each vertex one of the following conditions satisfied.
There exist a vertex u є V-D such that N(u)∩D={V}
v is an isolated vertex in D.
Proposition (1): The domination number of Alternate triangular belt graph (ATB(4)) is 2
(i.e. (ATB(4))=2).
Proof: Let the vertices of this graph indicated as: V(ATB(4))={v1,v2,v3,v4,v5,v6,v7,v8}(See Figure 1)
Figure 1. Ladder graph L3.
The dominating set in this graph S={v3,v7}was provided by. Since the set S only has one vertex and there isn't a suitable subset of it, the set's minimality is quite obvious (theorem (1)).
So S is minimum.
γ(ATB(4))=|S|=2
Theorem (2): For k ≥4 the domination number of Alternate triangular belt graph ATB(n) is k2.
First we give the dominating set of this graph by a set S where:
S1=(vk+3,vk+5,...,v2k+1)wheren2isoddandk≥2
S2=(vk,vk+4,vk+6,...,v2k+1)wheren2isevenandk≥3
For any v є S that is either v in S1 or v in S2 so the proof divided into two cases:
Case (1): If v є S1
We have always minimum one vertex of the form 2k not dominating with any vertex in Ś
So Ś is not dominating set.
So chosen S in this way ensures that there is no proper subset of S dominating AT B(n).
Case (2): If v є S2 such that v =(vk+1,vk+4,vk+6,...,v2k+1) that mean v≠v1; also we have always minimum one vertex of the form 2k not dominating with any vertex in Ś
So Ś is not dominating set.
Hence S is minimum
So γ (A T B (n))=|S|= k2.
Proposition (2): the domination number of Bistar graph 𝐵3,3 is 2
(i.e. (𝐵3,3 )=2).
Proof: Let the vertices of this graph indicated as:
V(B3,3)={v1,v2,v3,v4,v5,v6,v7,v8} (See Figure 2)
We identified S={v4,v5} as the dominating set of this graph. Since the set S only has one vertex and there isn't a suitable subset of it, the set's minimality is quite obvious (theorem (1)).
So S is minimum.
γ (B3,3)=|S|=2
Lemma (1): For n ≥ 4 the domination number of Bistar graph 𝐵n,n is 2
We have given the dominating set of this graph as follows:
S=(n2,n2+1)
 S=S-v́
S minimum
γ(Bn,n)=|S|=2.
It is very easy to proof the minimality of this set.
Suppose S is not minimum this implies that there is a proper sub set dominating 𝐵n,n.
If v є S that is either v=n2 or v=n2+1
If =n2, let S=S-v́ we have all the vertices that adjacent to v not dominating with the vertex n2+1=S-v=Ś
So Ś is not dominating set.
Similarly, for v =n2+1
So chosen S in this way ensures that there is no proper subset of S dominating 𝐵n,n.
S minimum
γBn,n=2
Independent dominating set of some graphs:
Theorem 3. Let G is line graph Ln with k blocks and n vertices, then IDS(Ln)=n-k2 where k is odd and IDS(Ln)=n-k-12 where k is even.
Theorem 4. let G be a crystal planar map Cn with n vertices where k blocks, then IDS (G) = 2
Figure 3. Crystal planar map Cn.
Proof. We label a crystal planar graph G=Cn as shown in Figure 3. It is clear that the number of vertices is n=k+3 and k is the number of blocks of G. let W ={v1, vn}
Begin
d(v1,w)=(0,2)
for i= 2: n-1
d(vi, w)=(1,1)
end
d(vn, w)=(2,0)
end
Theorem 5. let G is triangular snake graph (∆k-snake) with k blocks and n vertices, then IDSLn=n-k2 where k is odd and IDSLn=n-k-12 where k is even.
Theorem 6: let G be a k-kite chains graph Kk with k blocks and n vertices, the IDS(Kk)=(k+2, k+3,..., n-k-1).
Theorem 7: let G be a jewel graph Jn with k blocks and n vertices, then IDS (jn)=(v1,v3).
Figure 4. Jewel graph Jn.
Proof. We label a jewel graph Jn as shown in Figure 4. it is clear that the number of vertices is n=k+3 and k is the number of blocks of G. Let W ={v1, v3}
Begin
j=2
for i= 1: 3
d(vi, w)=(i-1,j)
j=j-1
end
for i= 4:n
d(vi, w)=(1,1)
end
end
Mathematical model of independent dominating set of graphs:
In this section we propose a new mathematical formulation for independent dominating set of graphs. Given a simple connected undirected graph G= (V, E), where V={1, 2,……, n}, let A=(aij)n×n be the neighborhood matrix such that
aij=ajiif i,jEor i=j, and aij=aji=0 otherwise without loss of generality, we define the edge set E as follows: E={(i,j):aij=1,i,jV with i<j)}
For i є V, let xi є{0,1} be a decision variable such that xi =1 if vertex i is included in dominating set; xi = 0 otherwise.
ILP model of independent dominating set problem can now be formulated as:
miniVxi(1)
s.t
js.taijxj1(2)
xi+xj1 foreachedge{i,jE(3)
xi0,1, foreachvertexiV(4)
4. Conclusion
Domination and independent in graphs is a branch of graph theory that has received a lot of attention. In this paper, we have interested by calculating the domination and independent dominating set of some graphs such as Triangular snake graph, Bistar graph, Alternate triangular belt graph, line graph and etc. We proposed a new mathematical formulation for independent dominating set of graphs.
For further work in the future, we plan to compute other variants of the domination of several graphs.
Abbreviations
γ (G): Domination Number
G: Graph
(∆k-snake): Triangular Snake Graph
Cn: Crystal Planar Map
𝐵n,n: Bistar Graph
𝐽n: Jewel Graph
Conflicts of Interest
The authors declare no conflicts of interest.
References
[1] D. Roth, on the hardness of approximate reasoning, Artif. Intell. 82 (1996) 273–302.
[2] Hurink, J. L. and Nieberg, T. 2008. "Approximating minimum independent dominating sets in wireless networks", Information processing letters, Vol. 109, pp. 155-160. D
[3] Cooper, C. Klasing, R. and Zito, M. 2005." Lower Bounds and Algorithms for Dominating Sets in Web Graphs", Internet Math. Vol. 2, No. 3, pp. 275-300.
[4] Berge, C.: Theory of Graphs and its Applications. Methuen & Co. Ltd., London (1962).
[5] Cockayne, E. J., Hedetniemi, S. T.: Independence graphs. Congr. Numer. X, 471–491 (1974).
[6] Cockayne, E. J., Hedetniemi, S. T.: Towards a theory of domination in graphs. Networks 7(3), 247–261 (1977).
[7] W. Goddard and M. A. Henning, “Independent domination in graphs: A survey and recent results”, Discrete Math., 2013, 313, 839-854.
[8] Roongrat Samanmoo, Nantapath Trakultraipruk and Nawarat Ananchuen “γIndependent dominating graphs of paths and cycles” Maejo Int. J. Sci. Technol. 2019, 13(03), 245-256.
[9] Zoltán Lóránt Nagy," On the number of k-dominating independent sets "Journal of Graph Theory, April 15, 2015.
[10] Christian Laforest and Raksmey Phan " Solving the minimum independent domination set problem in graphs by exact algorithm and greedy heuristic" RAIRO-Oper. Res. 47 (2013) 199–221.
[11] Omprakash Sikhwal and Rekha Lahoti "Domination Numbers of Graphs Containing Vertex-Disjoint Cycles in Graphs" Turkish Journal of Analysis and Number Theory, 2017, Vol. 5, No. 1, 1-4.
[12] Ramy Shaheen "On independent domination numbers of grid and toroidal grid directed graphs" Communications in Combinatorics and Optimization Vol. 4 No. 1, 2019 pp. 71-77.
[13] Mohamed, Basma, Linda Mohaisen, and Mohammed Amin. "Binary Archimedes Optimization Algorithm for Computing Dominant Metric Dimension Problem." Intelligent Automation & Soft Computing 38.1 (2023).
[14] Mohamed, Basma, and Mohamed Amin. "A hybrid optimization algorithms for solving metric dimension problem." Available at SSRN 4504670 (2023).
[15] Mohamed, Basma, Linda Mohaisen, and Mohamed Amin. "Binary equilibrium optimization algorithm for computing connected domination metric dimension problem." Scientific Programming 2022 (2022): 1-15.
[16] Mohamed, Basma, and Mohamed Amin. "Domination number and secure resolving sets in cyclic networks." Applied and Computational Mathematics 12.2 (2023): 42-45.
[17] Mohamed, Basma, Linda Mohaisen, and Mohamed Amin. "Computing Connected Resolvability of Graphs Using Binary Enhanced Harris Hawks Optimization." Intelligent Automation & Soft Computing 36.2 (2023).
[18] Mohamed, Basma, and Mohamed Amin. "The metric dimension of subdivisions of lilly graph, tadpole graph and special rees." Applied and Computational Mathematics 12.1 (2023): 9-14.
[19] D. Muthuramakrishnan and G. Jayaraman, Total Chromatic Number of Star and Bistar Graphs, International Journal of Pure and Applied Mathematics Volume 117 No. 21 2017, 699-708.
[20] S. K. Vaidya and D. D. Bantva, Radio Number for Total Graph of Paths, ISRN Combinatorics, 2013 (2013), 1-5.
[21] V. Govindan and S. Dhivya. "Difference Labelling of Jewel Graph" International Journal of Mathematics Trends and Technology (IJMTT) - Volume 65 Issue 4 - April 2019.
[22] S. Arumugam, and K. R. Chandrasekar, Minimal dominating sets in maximum domatic partitions. Australasian Journal of Combinatorics Volume 52 (2012), 281–292.
Cite This Article
  • APA Style

    Mohamed, B., Badawy, M. (2024). Some New Results on Domination and Independent Dominating Set of Some Graphs. Applied and Computational Mathematics, 13(3), 53-57. https://doi.org/10.11648/j.acm.20241303.11

    Copy | Download

    ACS Style

    Mohamed, B.; Badawy, M. Some New Results on Domination and Independent Dominating Set of Some Graphs. Appl. Comput. Math. 2024, 13(3), 53-57. doi: 10.11648/j.acm.20241303.11

    Copy | Download

    AMA Style

    Mohamed B, Badawy M. Some New Results on Domination and Independent Dominating Set of Some Graphs. Appl Comput Math. 2024;13(3):53-57. doi: 10.11648/j.acm.20241303.11

    Copy | Download

  • @article{10.11648/j.acm.20241303.11,
      author = {Basma Mohamed and Mohammed Badawy},
      title = {Some New Results on Domination and Independent Dominating Set of Some Graphs
    },
      journal = {Applied and Computational Mathematics},
      volume = {13},
      number = {3},
      pages = {53-57},
      doi = {10.11648/j.acm.20241303.11},
      url = {https://doi.org/10.11648/j.acm.20241303.11},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20241303.11},
      abstract = {One area of graph theory that has been studied in great detail is dominance in graphs. Applications for dominating sets are numerous. In wireless networking, dominant sets are used to find effective paths inside ad hoc mobile networks. They have also been used in the creation of document summaries and safe electrical grid systems. A set S⊆V is said to be dominating set of G if for every v є V-S there exists a vertex u є S such that uv є E. The dominance number of G, represented by γ(G), is the lowest cardinality of vertices among the dominating set of G. A classic NP-complete decision problem in computational complexity theory determines whether, given a graph G and input K, γ(G) ≤ K. This is known as the dominating set issue. Consequently, it is thought that calculating γ(G) for each given graph G may not be possible to do with a feasible algorithm. In addition to efficient approximation tactics, there exist efficient exact techniques for various graph classes. If there are no neighboring vertices in a subset S, then S⊆V is an independent set. Additionally, the empty set and the subset with just one vertex are independent. An independent dominating set of G is a set S of vertices in a graph G that is both an independent and a dominating set of G. This paper's primary goal is to investigate the dominance and independent dominating set of many graphs, including the line graph, the alternate triangular belt graph, the bistar graph, the triangular snake graph, and others.
    },
     year = {2024}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Some New Results on Domination and Independent Dominating Set of Some Graphs
    
    AU  - Basma Mohamed
    AU  - Mohammed Badawy
    Y1  - 2024/05/10
    PY  - 2024
    N1  - https://doi.org/10.11648/j.acm.20241303.11
    DO  - 10.11648/j.acm.20241303.11
    T2  - Applied and Computational Mathematics
    JF  - Applied and Computational Mathematics
    JO  - Applied and Computational Mathematics
    SP  - 53
    EP  - 57
    PB  - Science Publishing Group
    SN  - 2328-5613
    UR  - https://doi.org/10.11648/j.acm.20241303.11
    AB  - One area of graph theory that has been studied in great detail is dominance in graphs. Applications for dominating sets are numerous. In wireless networking, dominant sets are used to find effective paths inside ad hoc mobile networks. They have also been used in the creation of document summaries and safe electrical grid systems. A set S⊆V is said to be dominating set of G if for every v є V-S there exists a vertex u є S such that uv є E. The dominance number of G, represented by γ(G), is the lowest cardinality of vertices among the dominating set of G. A classic NP-complete decision problem in computational complexity theory determines whether, given a graph G and input K, γ(G) ≤ K. This is known as the dominating set issue. Consequently, it is thought that calculating γ(G) for each given graph G may not be possible to do with a feasible algorithm. In addition to efficient approximation tactics, there exist efficient exact techniques for various graph classes. If there are no neighboring vertices in a subset S, then S⊆V is an independent set. Additionally, the empty set and the subset with just one vertex are independent. An independent dominating set of G is a set S of vertices in a graph G that is both an independent and a dominating set of G. This paper's primary goal is to investigate the dominance and independent dominating set of many graphs, including the line graph, the alternate triangular belt graph, the bistar graph, the triangular snake graph, and others.
    
    VL  - 13
    IS  - 3
    ER  - 

    Copy | Download

Author Information
  • Mathematics and Computer Science Department, Faculty of Science, Menoufia University, Shebin El-Kom, Egypt

  • Department of Computer Science and Engineering, Faculty of Electronic Engineering, Menoufia University, Menouf, Egypt; Department of Computer Science, Faculty of Computers and Artificial Intelligence, AlRyada University for Science and Technology, Sadat City, Egypt