On the monotonicity of games generated by symmetric submodular functions Original Research Article

Submodular functions have appeared to be a key tool for proving the monotonicity of several graph searching games. In this paper, we provide a general game theoretic framework able to unify old and new monotonicity results in a unique min–max theorem. Our theorem provides a game theoretic analogue to a wide number of graph theoretic parameters such as linear-width and cutwidth.