Domination numbers and diameters in certain graphs
Subject Areas : Combinatorics, Graph theory
1 - Department of Mathematics, Faculty of Basic Sciences, Ilam University, Ilam, Iran
Keywords: Domination number, bicritical graph, diameter.,
Abstract :
Regarding the problem mentioned by Brigham et al. ``Is it correct that each connected bicritical graph possesses a minimum dominating set having every two appointed vertices of graphs?", we first give a class of graphs that disprove it and second obtain domination numbers and diameters of the graphs of this class. This class of graphs has the property: $\omega(\mathcal{H}) - diam(\mathcal{H})\rightarrow \infty$ when $|\mathcal{V}(\mathcal{H})|= n \rightarrow \infty$. Also, for the bicritical graphs of this class, $i(\mathcal{H})=\omega(\mathcal{H})$.
[1] N. Almalki, P. Kaemawichanurat, Structural properties of connected domination critical graphs, Mathematics. 9 (2021), 20:2568.
[2] R. C. Brigham, T. W. Haynes, M. A. Henning, D. F. Rall, Bicritical domination, Discrete Math. 305 (2005), 18-32.
[3] O. Favaron, D. Summer, E. Wojcicka, The diameter of domination-critical graphs, J. Graph Theory. 18 (1994), 723-724.
[4] W. Goddard, M. A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (7) (2013), 839-854.
[5] T. W. Haynes, S. T. Hedetniem, P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[6] D. A. Mojdeh, H. Abdollahzadeh Ahangar, S. S. Karimizad, On open problems on the connected bicritical graphs, Sci. Magna. 9 (1) (2013), 71-79.
[7] D. A. Mojdeh, N. Jafari Rad, On an open problem of total domination critical graphs, Expos. Math. 25 (2) (2007), 175-179.
[8] D. A. Mojdeh, N. Jafari Rad, On the total domination critical graphs, Elect. Notes. Disc. Math. 24 (2006), 89-92.
[9] D. P. Sumner, E. Wojcicka, Graphs Critical with Respect to the Domination Number, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
[10] W. Zhao, Y. Li, R, Lin, The existence of a graph whose vertex set can be partitioned into a fixed number of strong domination-critical vertex-sets, AIMS Mathematics. 9 (1) (2023), 1926-1938.