Previous |  Up |  Next


weakly connected domination number; tree; stable graphs
A dominating set $D\subseteq V(G)$ is a {\it 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 having at least one vertex in $D$. {\it Weakly connected domination number} $\gamma _w(G)$ of a graph $G$ is the minimum cardinality among all weakly connected dominating sets in $G$. A graph $G$ is said to be {\it weakly connected domination stable} or just $\gamma _w$-{\it stable} if $\gamma _w(G)=\gamma _w(G+e)$ for every edge $e$ belonging to the complement $\overline G$ of $G.$ We provide a constructive characterization of weakly connected domination stable trees.
[1] Sumner, D. P., Blitch, P.: Domination critical graphs. J. Combin. Theory Ser. B 34 (1983), 65-76. DOI 10.1016/0095-8956(83)90007-2 | MR 0701172 | Zbl 0512.05055
[2] Dunbar, J. E., Grossman, J. W., Hattingh, J. H., Hedetniemi, S. T., McRae, A.: On weakly-connected domination in graphs. Discrete Mathematics 167-168 (1997), 261-269. MR 1446750 | Zbl 0871.05037
[3] Henning, M. A.: Total domination excellent trees. Discrete Mathematics 263 (2003), 93-104. DOI 10.1016/S0012-365X(02)00572-1 | MR 1955717 | Zbl 1015.05065
[4] Chen, X., Sun, L., Ma, D.: Connected domination critical graphs. Applied Mathematics Letters 17 (2004), 503-507. DOI 10.1016/S0893-9659(04)90118-8 | MR 2057342 | Zbl 1055.05110
[5] Lemańska, M.: Domination numbers in graphs with removed edge or set of edges. Discussiones Mathematicae Graph Theory 25 (2005), 51-56. DOI 10.7151/dmgt.1259 | MR 2152049
Partner of
EuDML logo