pith. sign in

arxiv: 1804.08991 · v2 · pith:TN6PNNGKnew · submitted 2018-04-24 · 🧮 math.CO

Domination game and minimal edge cuts

classification 🧮 math.CO
keywords dominationgameedgecutsgraphsminimalconnectedgamma
0
0 comments X
read the original 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 $\gamma_g(G) \le \gamma_g(G\setminus C) + 2\kappa'(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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.