Connected certified domination stable and critical graphs upon edge addition

Abstract

A set of vertices Dc in a connected graph Γ = (VΓ, EΓ) is called a certified dominating set if |NΓ(u) ∩ (VΓ − Dc)| is either 0 or at least 2, ∀u ∈ Dc. The set Dc is called as connected certified dominating set if |N(u) ∩ (VΓ − Dc)| is either 0 or at least 2, ∀u ∈ Dc and the subgraph Γ[Dc] induced by Dc is connected. The cardinality of the smallest connected certified dominating set is called connected certified domination number of the graph Γ denoted by γccer(Γ). In this article, we examine and characterize those graphs that exhibit both connected certified domination stable and critical behavior when an edge is added to them. Also we will discuss characterization of connected certified domination stable trees.