Please use this identifier to cite or link to this item:
|Title:||Lower bound on the weakly connected domination number of a cycle-disjoint graph|
|Authors:||Koh, K.M. |
|Source:||Koh, K.M.,Ting, T.S.,Xu, Z.L.,Dong, F.M. (2010-02). Lower bound on the weakly connected domination number of a cycle-disjoint graph. Australasian Journal of Combinatorics 46 : 157-166. ScholarBank@NUS Repository.|
|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.|
|Source Title:||Australasian Journal of Combinatorics|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Mar 9, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.