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.
| 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 |
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] | 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. |
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
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
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
Share This Article
Twitter
Linked In
Facebook
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}
}
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 -
Mathematics and Computer Science Department, Faculty of Science, Menoufia University, Shebin El-Kom, Egypt
