Domination game and minimal edge cuts
| Autor: | Sandi Klavžar, Douglas F. Rall |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Domination analysis 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Edge (geometry) 01 natural sciences Upper and lower bounds Theoretical Computer Science Combinatorics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Order (group theory) Connectivity Mathematics |
| Zdroj: | Discrete Mathematics. 342:951-958 |
| ISSN: | 0012-365X |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect