Connected certified domination edge critical and stable graphs

Azham Ilyass Lone; Vishwajeet Goswami

doi:10.2478/ausi-2023-0003

Abstract

In an isolate-free graph 𝒵 = (V_𝒵, E_𝒵), a set C of vertices is termed as a connected certified dominating set of 𝒵 if, |N_𝒵(u) ∩ (V_𝒵\C)| = 0 or |N_𝒵(u) ∩ (V_𝒵\C)| ≥ 2 ∀u ∈C, and the subgraph 𝒵[C] induced by C is connected. The cardinality of the minimal connected certified dominating set of graph 𝒵 is called the connected certified domination number of 𝒵 denoted by γ_cer^c (Z). In graph 𝒵, if the deletion of any arbitrary edge changes the connected certified domination number, then we call it a connected certified domination edge critical. If the deletion of any random edge does not a ect the connected certified domination number, then we refer to it as a connected certified domination edge stable graph. In this paper, we investigate those graphs which are connected certified domination edge critical and stable upon edge removal. We then study some properties of connected certified domination edge critical and stable graphs.

References

S. B. Akers, D. Harel, B. Krishnamurthy, The star graph: An attractive alternative to the n-cube, Interconnection networks for high-performance parallel computers, 1994. pp. 145–152. ⇒28
Search in Google Scholar Back to article
V. Anithakumari, M. Padmini, Total domination number in graphs and graph modification, Tamilnadu: International Journal of Mathematics Trends and Technology (IJMTI), (2020). ⇒26
Search in Google Scholar Back to article
F. T. Boesch, S. Chen,J. A. M. McHugh, On covering the points of a graph with point disjoint paths, In Graphs and Combinatorics:Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University, Springer Berlin Heidelberg (1974) 201–212. ⇒28
Search in Google Scholar Back to article
M. Chellali, N. Jafari Rad, S. M. Sheikholeslami, L. Volkmann, Roman domination in graphs, In: Topics in Domination in Graphs Vol. 64. Springer, Cham. 2020, pp. 365–409 ⇒26
Search in Google Scholar Back to article
X. G. Chen, L. Sun, D. Xiang Ma, Connected domination critical graphs, Applied Mathematics Letter 17, 5 (2004) 503–507. ⇒26
Search in Google Scholar Back to article
W. J. Desormeaux, T. W Haynes, M. A. Henning, Total domination critical and stable graphs upon edge removal, Discrete applied mathematics 158, 15 (2010) 1587–1592. ⇒26
Search in Google Scholar Back to article
W. J. Desormeaux, T. W. Haynes, L. van der Merwe, Connected domination stable graphs upon edge addition, Quaestiones Mathematicae 38, 6 (2015) 841–848. ⇒26
Search in Google Scholar Back to article
M. Dettla, M. Lemanska, J. Topp, R. l. Ziemann, P. Zylinski, Certified domination, AKCE International Journal of Graphs and Combinatorics 17, 1 (2020) 86–97. ⇒25, 26
Search in Google Scholar Back to article
M. Dettla, M. Lemanska, J. Topp, R. l. Ziemann, P. Zylinski, Graphs with equal domination and certified domination numbers, arXiv:1710.02059 (2017). ⇒26
Search in Google Scholar Back to article
R. D. Dutton, R. C. Brigham, An extremal problem for edge domination insensitive graphs, Discrete applied mathematics 20, 2 (1988) 113–125. ⇒26
Search in Google Scholar Back to article
J. A. Gallian, A dynamic survey of graph labeling, Electronic Journal of combinatorics, 1 (DynamicSurveys) (2018). ⇒28
Search in Google Scholar Back to article
E. Harris, Global Domination Stable Graphs, PhD thesis, East Tennessee State University, 2012. ⇒26
Search in Google Scholar Back to article
T. W. Haynes, S. Hedetniemi, P. Slater, Fundamentals of Domination in Graphs, CRC press, 2013. ⇒27
Search in Google Scholar Back to article
P. K. Jakkepalli, S. Arumugam, H. Khandelwal, Algorithmic aspects of certified domination in graphs, Communications in Combinatorics and Optimization 7, 2 (2022) 247–255. ⇒26
Search in Google Scholar Back to article
S. D. Raj, S. G. Shiji Kumari, Certified domination number in product of graphs, Turkish Journal of Computer and Mathematics Education (TURCOMAT) 11, 3 (2020) 1166–1170. ⇒26
Search in Google Scholar Back to article
S. D. Raj, S. G. Shiji Kumari, A. M. Anto, Certified domination number in corona product of graphs, Malaya Journal of Matematik 9, 1 (2021) 1080–1082. ⇒26
Search in Google Scholar Back to article
H. B, Walikar, B. D. Acharya, Domination Critical Graphs, National Academy Science Letters-India 2, 2 (1979) 70–72. ⇒26
Search in Google Scholar Back to article
D. B. West, Introduction to Graph Theory. Vol. 2. Prentice Hall, Upper Saddle River, 2001. ⇒27
Search in Google Scholar Back to article

Connected certified domination edge critical and stable graphs

Abstract

Paradigm

My account