Connected tree-width and connected cops and robber game
Abstract
The node search game against a lazy/agile invisible robber has been introduced as a search-game analogue of the graph parameters of treewidth/pathwidth. In the "connected" variants of the above two games, we additionally demand that, at each moment of the search, the "clean" territories are connected.
The connected search game against an agile and invisible robber has been extensively examined. The monotone variant (where we also demand that the clean territories are progressively increasing) of this game, corresponds to the graph parameter of connected path width. It has been shown that its value cannot be more than the double (plus some constant) of its non-connected counterpart. This implied that the "price of connectivity" is bounded by 2 for the case of an agile robber.
In this talk, we consider the connected variant of this search game where the robber is lazy. We introduce two alternative graph-theoretical formulations of this game, one in terms of connected tree decompositions, and one in terms of (connected) layouts, leading to the graph parameter of connected tree width. We first show that in contrast to the "agile-robber" variant, the price of connectivity for the "lazy-robber" game is unbounded. To that aim, we observe that the connected treewidth parameter is closed under contraction and prove that the set of contraction obstruction is infinite for every integer k ≥ 2.
Domains
Discrete Mathematics [cs.DM]Origin | Files produced by the author(s) |
---|