On local edge connected domination critical graphs

Abstract

Let γ(G) and γ_c(G) denote the domination number and connected domination number of G, respectively. For positive integers k, t with t ≥ 2, a graph G is k-{γ, t)-critical (k-{γ_c, t)-critical) if γ(G) = k (γ_c(G) = k) but γ(G + uv) < k (γ_c(G + uv) < k) for every pair of non-adjacent vertices u and v of G with d(u,v) ≤ t. fc-(γ, t)-critical graphs were first studied by Henning et al. [5] but k-(γ_c, t)-critical graphs have never been investigated. In this paper, we initiate an investigation of k-(γ_c, t)-critical graphs and extend results on k-(γ, t)-critical graphs. More precisely, we show that the diameter of k-(γ_c, t)-critical graphs for k > 2 and í > 2 is at most k + 1 and provide a characterization of such graphs having diameter k + 1 for 2 ≤ t ≤ k. We also characterize 2-(γ_c, t)-critical graphs for ť ≥ 2 and 3-(γ_c, t)-critical graphs for t ≥ 3. Finally, we establish that k-(γ, t)-critical graphs for k = 2, 3 and t ≥ 3 are k-γ-critical.