Strong Edge Criticality for Cardinality-Redundance in Graphs

Document Type : Original Scientific Paper

Authors

‎Department of Mathematics, ‎Shahed University‎, ‎‎Tehran‎, ‎I‎. ‎R‎. ‎Iran

10.22052/mir.2025.256792.1518

Abstract

‎
‎A vertex $v$ in a graph $G$ is said to be over-dominated by a subset $S$ of vertices of $G$ if $|N[v]\cap S|\geq 2$‎. ‎The cardinality--redundance of $S$‎, ‎which we denote by $CR(S)$‎, ‎is the number of vertices of $G$ that are over-dominated by $S$‎. ‎The cardinality--redundance number of a graph $G$‎, ‎which we denote by $CR(G)$‎, ‎is the minimum among all cardinality--redundances $CR(S)$ taken over all dominating sets $S$‎. ‎In this paper‎, ‎we study those graphs whose cardinality--redundance decreases by two upon the removal of any arbitrary edge‎. ‎We refer to such graphs as cardinality--redundance strong edge critical graphs‎. ‎We give a general characterization for all cardinality--redundance strong edge critical graphs‎, ‎and then focus on the cardinality--redundance strong edge critical graphs having cardinality--redundance $2$‎, ‎and present several characterizations for these graphs‎.

Keywords

Main Subjects

References

[1] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[2] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
[3] T. W. Johnson and P. J. Slater, Maximum independent, minimally credundant sets in graphs, Congr. Numer. 74 (1990) 193- 211.
[4] D. McGinnis and N. Shank, Extremal problems related to the Cardinality-Redundance of graphs, Australas. J. Combin. 87 (2023) 214 - 238.
[5] E. Mohammadi and N. Jafari Rad, On the trees with maximum Cardinality-Redundance number, Comput. Sci. J. Moldova 32 (2024) 38 - 45, https://doi.org/10.56415/csjm.v32.03.
[6] R. C. Brigham, P. Z. Chinn and R. D. Dutton, Vertex domination-critical graphs, Networks 18 (1988) 173 - 179, https://doi.org/10.1002/net.3230180304.
[7] R. D. Dutton and R. Brigham, On global domination critical graphs, Discrete Math. 309 (2009) 5894 - 5897, https://doi.org/10.1016/j.disc.2008.06.005.
[8] P. J. P. Grobler and C. M. Mynhardt, Secure domination critical graphs, Discrete Math. 309 (2009) 5820 - 5827.
[9] N. Jafari Rad, A. Hansberg and L. Volkmann, Vertex and edge critical Roman domination in graphs, Util. Math. 92 (2013) 73 - 88.
[10] D. Hanson and P. Wang, A note on extremal total domination edge critical graphs, Util. Math. 63 (2003) 89 - 96.
[11] M. A. Henning and N. Jafari Rad, On total domination vertex critical graphs of high connectivity, Discrete Appl. Math. 157 (2009) 1969 - 1973, https://doi.org/10.1016/j.dam.2008.12.009
[12] M. A. Henning and L. C. van der Merwe, Properties of total domination edge critical graphs, Discrete Appl. Math. 158 (2010) 147- 153, https://doi.org/10.1016/j.dam.2009.09.004.
[13] N. Jafari Rad, On the diameter of a domination dot critical graph, Discrete Appl. Math. 157 (2009) 1647- 1649,
https://doi.org/10.1016/j.dam.2008.10.015.
[14] D. A. Mojdeh, A. Sayed-Khalkhali, H. Abdollahzadeh Ahangar and Y. Zhao, Total k-distance domination critical graphs, Trans. Comb. 5 (2016) 1 - 9, https://doi.org/10.22108/TOC.2016.11972.
[15] D. A. Mojdeh, S. R. Musawi and E. Nazari, Domination critical Knödel graphs, Iran. J. Sci. Technol. Trans. A Sci. 43 (2019) 2423- 2428, https://doi.org/10.1007/s40995-019-00710-8.
[16] D. P. Sumner and P. Blitch, Domination critical graphs, J. Combin. Theory Ser. B 34 (1983) 65 - 76, https://doi.org/10.1016/0095-8956(83)90007-2.
[17] C.Wang, Z. Hu and X. Li, A constructive characterization of total domination vertex critical graphs, Discrete Math. 309 (2009) 991 - 996.
Mathematics Interdisciplinary Research
Volume 10, Issue 4
In Progress
December 2025
Pages 397-406

Files

Share

How to cite

Statistics