The Non-Isolated Domination Number of a Graph
DOI:
https://doi.org/10.20956/j.v21i3.43474Keywords:
dominating number, isolated vertex, non-isolated domination number, dominating setAbstract
A subset S of the vertex set V (G) of a graph G is said to be a dominating set if every vertex not in S is adjacent to at least one vertex in S. In this research, we introduce a new domination parameter called the non-isolated domination number of a graph. A subset S of V of a nontrivial graph G is said to be a non-isolated dominating set if S is a dominating set and there are no zero-degree vertices in the subgraph induced by S. The minimum cardinality taken over all non-isolated dominating sets is called the non-isolated domination number and is denoted by γI. In this research, we obtained lower and upper bounds for the non-isolated domination number of a connected graph. We also determine the characterization of connected graphs that have the non-isolated domination numbers 2 and 3. Furthermore, we determine the non-isolated domination number of complete, n-partite complete, wheel, fan, star, cycle, and path graphs. We also determine the characterization of tree graphs that have the non-isolated domination number 2γ.
References
[1] Arumugam, S., & Paulraj, J. J., 1999. On graphs with equal domination and connected domination numbers. Discrete Mathematics, 206, 45–49.
[2] Bujtás, C., & Henning, M. A., 2025. On the domination number of graphs with minimum degree at least seven. Discrete Mathematics, 348(6), 114424.
[3] Cabrera-Martínez, A., 2022. New bounds on the double domination number of trees. Discrete Applied Mathematics, 315, 97–103.
[4] Desormeaux, W. J., Haynes, T. W., & Henning, M. A., 2013. Bounds on the connected domination number of a graph. Discrete Applied Mathematics, 161(18), 2925–2931.
[5] Diestel, R. 2017. Graph theory (5th ed.). Springer.
[6] Duckworth, W., & Mans, B., 2009. Connected domination of regular graphs. Discrete Mathematics, 309(8), 2305–2322.
[7] Feng, X., & Ge, J., 2021. A conjecture on the lower bound of the signed edge domination number of 2-connected graphs. Discrete Applied Mathematics, 302, 42–45.
[8] Harary, F. 1969. Graph theory. Addison-Wesley.
[9] Haynes, T. W., Hedetniemi, S. T., & Slater, P. J., 1998. Fundamentals of domination in graphs. Marcel Dekker.
[10] Hedetniemi, S. T., & Laskar, R. 1984. Connected domination in graphs. Graph Theory and Combinatorics, 209–218.
[11] Henning, M. A., Pilśniak, M., & Tumidajewicz, E., 2022. Bounds on the paired domination number of graphs with minimum degree at least three. Applied Mathematics and Computation, 417, 126782.
[12] Henning, M. A., & Yeo, A., 2021. A new upper bound on the total domination number in graphs with minimum degree six. Discrete Applied Mathematics, 302, 1–7.
[13] Mafuta, P., Mukwembi, S., & Rodrigues, B. G., 2023. A note on connected domination number and leaf number. Discrete Mathematics, 346(2), 113228.
[14] Mahadevan, G., Avadayappan, S., Joseph, J. P., & Subramanian, T., 2012. Triple connected domination number of a graph. International Journal of Mathematics and Combinatorics, 3, 93–104.
[15] Mahalingam, G., 2005. Connected domination in graphs. University of South Florida, Doctoral dissertation, University of South Florida.
[16] Ore, O. 1962. Theory of graphs. American Mathematical Society Colloquium Publications.
[17] Sampathkumar, E., & Walikar, H. B., 1979. The connected domination number of a graph. Journal of Mathematical Physics and Science, 13(6), 607–613.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Jurnal Matematika, Statistika dan Komputasi
This work is licensed under a Creative Commons Attribution 4.0 International License.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Jurnal Matematika, Statistika dan Komputasi is an Open Access journal, all articles are distributed under the terms of the Creative Commons Attribution License, allowing third parties to copy and redistribute the material in any medium or format, transform, and build upon the material, provided the original work is properly cited and states its license. This license allows authors and readers to use all articles, data sets, graphics and appendices in data mining applications, search engines, web sites, blogs and other platforms by providing appropriate reference.
