Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/103519
Title: Lower bound on the weakly connected domination number of a cycle-disjoint graph
Authors: Koh, K.M. 
Ting, T.S.
Xu, Z.L.
Dong, F.M.
Issue Date: Feb-2010
Citation: 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
URI: http://scholarbank.nus.edu.sg/handle/10635/103519
ISSN: 10344942
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

38
checked on Nov 2, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.