Lower bound on the weakly connected domination number of a cycle-disjoint graph

Abstract

For a connected graph G and any non-empty S C V(G), S is called a weakly connected dominating set of G if the subgraph obtained from G by removing all edges each joining any two vertices in V(G) \ S is connected. The weakly connected domination number γw(G) is defined to be the minimum integer k with \S\ = k for some weakly connected dominating set S of G. In this note, we extend a result on the lower bound for the weakly connected domination number γw (G) on trees to cycle-e-disjoint graphs, i.e., graphs in which no cycles share a common edge. More specifically, we show that if G is a connected cycle-e-disjoint graph, then γw(G) ≥ (\V(G)\- v1(G) - nc(G) - noc(G) + l)/2, where n c(G) is the number of cycles in G, noc(G) is the number of odd cycles in G and u1(G) is the number of vertices of degree 1 in G. The graphs for which equality holds are also characterised.