A periodic graph \(\mathcal {G}=(G_0, G_1, G_2, \dots )\) with period p is an infinite periodic sequence of graphs \(G_i = G_{i + p} = (V,E_i)\) , where \(i \geq 0\) . The graph \(G=(V,\cup _i E_i)\) is called the footprint of \(\mathcal {G}\) . Recently, the arena where the Cops and Robber game is played has been extended from a graph to a periodic graph; in this case, the cop number is also the minimum number of cops sufficient for capturing the robber. We study the connections and distinctions between the cop number \(c(\mathcal {G})\) of a periodic graph \(\mathcal {G}\) and the cop number \(c(G)\) of its footprint G and establish several facts. For instance, we show that the smallest periodic graph with \(c(\mathcal {G}) = 3\) has at most 8 nodes; in contrast, the smallest graph G with \(c(G) = 3\) has 10 nodes. We push this investigation by generating multiple examples showing how the cop numbers of a periodic graph \(\mathcal {G}\) , the subgraphs \(G_i\) and its footprint G can be loosely tied. Based on these results, we derive upper bounds on the cop number of a periodic graph from properties of its footprint such as its treewidth.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

COP Numbers of Periodic Graphs

  • Jean-Lou De Carufel,
  • Paola Flocchini,
  • Nicola Santoro,
  • Frédéric Simard

摘要

A periodic graph \(\mathcal {G}=(G_0, G_1, G_2, \dots )\) with period p is an infinite periodic sequence of graphs \(G_i = G_{i + p} = (V,E_i)\) , where \(i \geq 0\) . The graph \(G=(V,\cup _i E_i)\) is called the footprint of \(\mathcal {G}\) . Recently, the arena where the Cops and Robber game is played has been extended from a graph to a periodic graph; in this case, the cop number is also the minimum number of cops sufficient for capturing the robber. We study the connections and distinctions between the cop number \(c(\mathcal {G})\) of a periodic graph \(\mathcal {G}\) and the cop number \(c(G)\) of its footprint G and establish several facts. For instance, we show that the smallest periodic graph with \(c(\mathcal {G}) = 3\) has at most 8 nodes; in contrast, the smallest graph G with \(c(G) = 3\) has 10 nodes. We push this investigation by generating multiple examples showing how the cop numbers of a periodic graph \(\mathcal {G}\) , the subgraphs \(G_i\) and its footprint G can be loosely tied. Based on these results, we derive upper bounds on the cop number of a periodic graph from properties of its footprint such as its treewidth.