CONNECTED CERTIFIED DOMINATION STABLE AND CRITICAL GRAPHS UPON EDGE ADDITION

CONNECTED CERTIFIED DOMINATION STABLE AND CRITICAL GRAPHS UPON EDGE ADDITION

A. Ilyass, N. Mani, V. Goswami

[PDF]

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 γc cer(Γ). 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.

Keywords

Connected certified dominating set, Connected certified domination edge stable graphs, Connected certified domination edge critical graphs.