Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/103519
DC Field | Value | |
---|---|---|
dc.title | Lower bound on the weakly connected domination number of a cycle-disjoint graph | |
dc.contributor.author | Koh, K.M. | |
dc.contributor.author | Ting, T.S. | |
dc.contributor.author | Xu, Z.L. | |
dc.contributor.author | Dong, F.M. | |
dc.date.accessioned | 2014-10-28T02:38:14Z | |
dc.date.available | 2014-10-28T02:38:14Z | |
dc.date.issued | 2010-02 | |
dc.identifier.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. | |
dc.identifier.issn | 10344942 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/103519 | |
dc.description.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. | |
dc.source | Scopus | |
dc.type | Article | |
dc.contributor.department | MATHEMATICS | |
dc.description.sourcetitle | Australasian Journal of Combinatorics | |
dc.description.volume | 46 | |
dc.description.page | 157-166 | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.