## Abstract

Let G = (V, E) be a connected graph. A dominating set S of G is a weakly connected dominating set of G if the subgraph (V, E ∩ (S × V)) of G with vertex set V that consists of all edges of G incident with at least one vertex of S is connected. The minimum cardinality of a weakly connected dominating set of G is the weakly connected domination number, denoted γ_{wc} (G). A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_{t} (G) of G. In this paper, we show that frac(1, 2) (γ_{t} (G) + 1) ≤ γ_{wc} (G) ≤ frac(3, 2) γ_{t} (G) - 1. Properties of connected graphs that achieve equality in these bounds are presented. We characterize bipartite graphs as well as the family of graphs of large girth that achieve equality in the lower bound, and we characterize the trees achieving equality in the upper bound. The number of edges in a maximum matching of G is called the matching number of G, denoted α^{′} (G). We also establish that γ_{wc} (G) ≤ α^{′} (G), and show that γ_{wc} (T) = α^{′} (T) for every tree T.

Original language | English |
---|---|

Pages (from-to) | 3086-3093 |

Number of pages | 8 |

Journal | Discrete Applied Mathematics |

Volume | 157 |

Issue number | 14 |

DOIs | |

Publication status | Published - 28 Jul 2009 |

Externally published | Yes |

## Keywords

- Bounds
- Matching number
- Total domination
- Weakly connected domination

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics