Search
Abstract
A vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V(G)D is independent. The double outer-independent domination number of a graph G, denoted by gamma_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We prove that for every nontrivial tree T of order n, with l leaves and s support vertices we have gamma_d^{oi}(T) >= (2n+l-s+2)/3, and we characterize the trees attaining this lower bound. We also give a constructive characterization of trees T such that gamma_d^{oi}(T) = (2n+2)/3.
Citations
-
1
CrossRef
-
0
Web of Science
-
1
Scopus
Cite as
Full text
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1515/dema-2013-0358
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Published in:
-
Demonstratio Mathematica
no. 45,
pages 17 - 23,
ISSN: 0420-1213 - Language:
- English
- Publication year:
- 2012
- Bibliographic description:
- Krzywkowski M.: A lower bound on the double outer-independent domination number of a tree// Demonstratio Mathematica. -Vol. 45., iss. 1 (2012), s.17-23
- DOI:
- Digital Object Identifier (open in new tab) 10.1515/dema-2013-0358
- Verified by:
- Gdańsk University of Technology
seen 114 times