Opuscula Math. 28, no. 3 (2008), 325-330

Opuscula Mathematica

# Weakly connected domination critical graphs

Magdalena Lemańska
Agnieszka Patyk

Abstract. A dominating set $$D \subset V(G)$$ is a weakly connected dominating set in $$G$$ if the subgraph $$G[D]_w = (N_{G}[D],E_w)$$ weakly induced by $$D$$ is connected, where $$E_w$$ is the set of all edges with at least one vertex in $$D$$. The weakly connected domination number $$\gamma_w(G)$$ of a graph $$G$$ is the minimum cardinality among all weakly connected dominating sets in $$G$$. The graph is said to be weakly connected domination critical ($$\gamma_w$$-critical) if for each $$u, v \in V(G)$$ with $$v$$ not adjacent to $$u$$, $$\gamma_w(G + vu) \lt \gamma_w (G)$$. Further, $$G$$ is $$k$$-$$\gamma_w$$-critical if $$\gamma_w(G) = k$$ and for each edge $$e \not\in E(G)$$, $$\gamma_w(G + e) \lt k$$. In this paper we consider weakly connected domination critical graphs and give some properties of $$3$$-$$\gamma_w$$-critical graphs.

Keywords: weakly connected domination number, tree, critical graphs.

Mathematics Subject Classification: 05C05, 05C69.

Full text (pdf)

• Magdalena Lemańska
• Gdańsk University of Technology, Department of Technical Physics and Applied Mathematics, Narutowicza 11/12, 80–952 Gdańsk, Poland
• Agnieszka Patyk
• Gdańsk University of Technology, Department of Technical Physics and Applied Mathematics, Narutowicza 11/12, 80–952 Gdańsk, Poland
• Revised: 2008-03-05.
• Accepted: 2008-03-26.