Localization Game for Random Graphs
| Autor: | Andrzej Dudek, Sean English, Alan Frieze, Calum MacRury, Paweł Prałat |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
010201 computation theory & mathematics
Applied Mathematics 010102 general mathematics FOS: Mathematics Discrete Mathematics and Combinatorics Mathematics - Combinatorics 0102 computer and information sciences Combinatorics (math.CO) 0101 mathematics 16. Peace & justice 01 natural sciences MathematicsofComputing_DISCRETEMATHEMATICS |
| Popis: | We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The corresponding graph parameter $\zeta(G)$ for a given graph $G$ is called the localization number. In this paper, we improve the bounds for dense random graphs determining an asymptotic behaviour of $\zeta(G)$. Moreover, we extend the argument to sparse graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|