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

摘要

For a connected graph G and any non-empty S C V(G), S is calleda weakly connected dominating set of G if the subgraph obtained fromG by removing all edges each joining any two vertices in V(G) S isconnected. The weakly connected domination number γ_w(G)is definedto be the minimum integer k with |S|=kfor some weakly connecteddominating set S of G. In this note, we extend a result on the lowerbound for the weakly connected domination number γ_w(G) on trees tocycle-e-disjoint graphs, i.e., graphs in which no cycles share a commonedge. More specifically, we show that if G is a connected cycle-e-disjointgraph, then γ_w(G)≥(|V(G)| - v_1(G) n_c(n_(oc)(+1)/2, wheren_c(G)is the number of cycles inG, n_(oc)(odd cyclesin G and vi(G) is the number of vertices of degree 1 in G. The graphsfor which equality holds are also characterised.