Back to Search
Start Over
Domination game and minimal edge cuts.
- Source :
-
Discrete Mathematics . Apr2019, Vol. 342 Issue 4, p951-958. 8p. - Publication Year :
- 2019
-
Abstract
- Abstract In this paper a relationship is established between the domination game and minimal edge cuts. It is proved that the game domination number of a connected graph can be bounded above in terms of the size of minimal edge cuts. In particular, if C a minimum edge cut of a connected graph G , then γ g (G) ≤ γ g (G ∖ C) + 2 κ ′ (G). Double-Staller graphs are introduced in order to show that this upper bound can be attained for graphs with a bridge. The obtained results are used to extend the family of known traceable graphs whose game domination numbers are at most one-half their order. Along the way two technical lemmas, which seem to be generally applicable for the study of the domination game, are proved. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 342
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 134733782
- Full Text :
- https://doi.org/10.1016/j.disc.2018.12.001