Containment game played on random graphs: another zig-zag theorem (Q2346471)

From MaRDI portal
Revision as of 03:37, 10 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Containment game played on random graphs: another zig-zag theorem
scientific article

    Statements

    Containment game played on random graphs: another zig-zag theorem (English)
    0 references
    0 references
    2 June 2015
    0 references
    Summary: We consider a variant of the game of Cops and Robbers, called Containment, in which cops move from edge to adjacent edge, the robber moves from vertex to adjacent vertex (but cannot move along an edge occupied by a cop). The cops win by ``containing'' the robber, that is, by occupying all edges incident with a vertex occupied by the robber. The minimum number of cops, \(\xi(G)\), required to contain a robber played on a graph \(G\) is called the containability number, a natural counterpart of the well-known cop number \(c(G)\). This variant of the game was recently introduced by \textit{N. Komarov} and \textit{J. Mackey} [``Containment: a variation of cops and robbers'', Preprint], who proved that for every graph \(G\), \(c(G) \leq \xi(G) \leq \gamma(G) \Delta(G)\), where \(\gamma(G)\) and \(\Delta(G)\) are the domination number and the maximum degree of \(G\), respectively. They conjecture that an upper bound can be improved and, in fact, \(\xi(G) \leq c(G) \Delta(G)\). (Observe that, trivially, \(c(G) \leq \gamma(G)\).) This seems to be the main question for this game at the moment. By investigating expansion properties, we provide asymptotically almost sure bounds on the containability number of binomial random graphs \(\mathcal{G}(n,p)\) for a wide range of \(p=p(n)\), showing that it forms an intriguing zigzag shape. This result also proves that the conjecture holds for some range of \(p\) (or holds up to a constant or an \(O(\log n)\) multiplicative factors for some other ranges).
    0 references
    containment
    0 references
    cops and robbers
    0 references
    vertex-pursuit games
    0 references
    random graphs
    0 references

    Identifiers