Open Access
Research Article
Radius, diameter, domination number, order and minimum degree
*P. MafutaCorresponding authorphillipmafuta@gmail.comDepartment of Mathematics and Applied Mathematics IB74 University of the Free State P. O. Box 339Bloemfontein, 9300, South AfricaView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 12 Oct 2022
- Published Online:
- 29 Jul 2024
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JIOS-1398
- Pages:
- 1281–1291
Abstract
Consider a simple graph G which is connected with given order, diameter, radius and minimum degree. Using set-theory and standard results, tight upper bounds on the domination number g(G) based on the aforementioned graph parameters are proven. The results bring to the literature new bounds on the domination number, apart from strengthening results by Henning and Mukwembi [Domination, radius and minimum degree, Discrete Applied Mathematics, 157 (2009), 2964-2968]. We show by construction that the results hold even if the graphs are highly connected. We consider only simple graphs.
Keywords
Subject Classifications
(2010) 05C0505C1205C35
References
[1] Ananchuen N., Ananchuen W., Plummer M.D., Domination in Graphs, In: Dehmer M. (eds) Structural Analysis of Complex Networks. Birkhuser Boston (2011), https://doi.org/10.1007/978-0-8176-4789-64. [2] Alfuraidan M.R., Das K.C., Vetr k T., Balachandran S., General sum-connectivity index of unicyclic graphs with given diameter, Discrete Applied Mathematics, 295, 39-46 (2021). [3] Caro Y., West D.B., Yuster R., Connected domination and spanning trees with many leaves, SIAM Journal on Discrete Mathematics 13, 202-211 (2000). [4] Chung F.K.R., The average distance and the independence number, Journal of Graph Theory, 12, 229-235 (1988). [5] Dankelmann P., Dlamini G., and Swart H.C., Upper bounds on the distance measures in -free graphs, Utilitas Mathenatica, 67, 205-222 (2005). [6] Dankelmann P., Entringer R.C., Average distance, minimum degree and spanning trees, Journal of Graph Theory, 33, 1-13 (2000). [7] Dankelmann P., and Mukwembi S., The Distance Concept and Distance in Graphs, In I Gutman, B. Furtula (Eds), Distance in Molecular Graphs-Theory, Univ. Kragujevac, Kragujevac, 3-48 (2012). [8] Dankelmann P., Swart H.C., and van den Berg P., Diameter and inverse degree, Discrete Mathematics, 308, 670-673 (2008). [9] DeLaviña E., Pepper B., and Waller B., Lower bounds for the domination number, Discussiones Mathematicae: Graph Theory, 30(3), 475-487 (2010). [10] Das A. Triameter of Graphs, Discussiones Mathematicae: Graph Theory, 41(2), 601-616 (2021). [11] Desormeaux W.J., Haynes T.W., and Henning M.A., Restrained domination in self-complementary graphs. Discussiones Mathematicae: Graph Theory, 41(2), 633-645 (2021). [12] Erdös P., Pach J., and Spencer J., On the mean distance between points of a graph, Congressus Numerantium, 64, 121-124 (1988). [13] Erdös P., Pach J., Pollack R. and Tuza Z., Radius, diameter and minimum degree, Journal of Combinatorial Theory, Series B, 47, 73-79 (1989). [14] Erdös P., Sachs M. and Sos V., Maximum induced trees in graphs, Journal of Combinatorial Theory, Series B, 41, 61-79 (1986). [15] Griggs J.R., Wu M., Spanning trees in graphs of minimum degree 4 or 5. Discrete Mathematics, 104, 167-183 (1992). [16] Haynes T.W., Hedetniemi S.M., Hedetniemi S.T., Henning M.A., Domination in Graphs, Advanced Topics, Marcel Dekker, New York, (1998). [17] Haynes T.W., Hedetniemi S.M., Hedetniemi S.T., and Henning M.A., Domination in graphs applied to electric power networks, Siam Journal on Discrete Mathematics, 15(4), 519-529 (2002). [18] Henning M.A., Mukwembi S., Domination, radius and minimum Degree, Discrete Applied Mathematics, 157, 2964-2968 (2009). [19] Liu, C. A note on domination number in maximal outerplanar graphs, Discrete Applied Mathematics, 293, 90-94 (2021). [20] Mafuta P., On the leaf number of a graph, DSI-NRF Centre of Excellence in Mathematical and Statistical Sciences-Seminar Series, (2021). https://youtu.be/Ih6pOB6X9ro. [21] Mafuta P. Bounds on the leaf number in graphs of girth 4 or 5, Journal of Discrete Mathematical Sciences and Cryptography, 24(6), 1573-1582 (2021). [22] Mafuta P., Mukwembi S., & Munyira S., Radius, leaf number, connected domination number and minimum degree, Quaestiones Mathematicae, 46(5), 1009-1016 (2023). [23] Mafuta P., Mukwembi S., Rodrigues B.G., A note on connected domination number and leaf number. Discrete Mathematics 346(2), 113228 (2023). [24] Mahadevan G., Vijayalakshmi V., Clone hop domination number of a graph, Journal of Discrete Mathematical Sciences and Cryptography, 22(5), 719-729 (2019). [25] Mukwembi S., On size, order, diameter and minimum degree, Indian Journal of Pure and Applied Mathamatics, 44(4), 467-472 (2013). [26] Mukwembi S., On size, radius and minimum degree, Discrete Mathematics and Theoretical Computer Science, 16(1), 1-6 (2014). [27] Munyira S., Bounds on distance-based parameters, University of Zimbabwe, 1-108 (2016). [28] Natarajan C., Ayyaswamy S., Hop domination in graphs II, Versita, 23(2), 187-199 (2015). [29] Raju M., Bhutani K.R., Moazzez B., Arumugam S., On F-domination in graphs, AKCE International Journal of Graphs and Combinatorics. https://doi.org/10.1016/j.akcej.2018.07.004. [30] Wu B., Ani X., Liu G., Yan G. and Liu X., Minimum degree, edge-connectivity and radius, Journal of Combinatorial Optimization, 26, 585-591 (2013). [31] Yan H., Kang L. and Xu G., The exact domination number of the generalized Petersen graphs. Discrete Mathematics, 309(8), 2596-2607 (2009).
Views: 137Downloads: 7Citations: 0
