Source author record

William B. Kinnersley

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Computational Complexity

Catalog footprint

Research overview

11works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Catching an infinitely fast robber on a grid

We consider a variant of Cops and Robbers in which the robber may traverse as many edges as he likes in each turn, with the constraint that he cannot pass through any vertex occupied by a cop. We study this model on several classes of grid-like graphs. In particular, we determine the cop numbers for two-dimensional Cartesian grids and tori up to an additive constant, and we give asymptotic bounds for the cop numbers of higher-dimensional grids and hypercubes.

preprint2020arXiv

Bounds on the localization number

We consider the localization game played on graphs, wherein a set of cops attempt to determine the exact location of an invisible robber by exploiting distance probes. The corresponding optimization parameter for a graph $G$ is called the localization number and is written $ζ(G)$ . We settle a conjecture of \cite{nisse1} by providing an upper bound on the localization number as a function of the chromatic number. In particular, we show that every graph with $ζ(G) \le k$ has degeneracy less than $3^k$ and, consequently, satisfies $χ(G) \le 3^{ζ(G)}$ . We show further that this degeneracy bound is tight. We also prove that the localization number is at most 2 in outerplanar graphs, and we determine, up to an additive constant, the localization number of hypercubes.

preprint2016arXiv

Game Brush Number

We study a two-person game based on the well-studied brushing process on graphs. Players Min and Max alternately place brushes on the vertices of a graph. When a vertex accumulates at least as many brushes as its degree, it sends one brush to each neighbor and is removed from the graph; this may in turn induce the removal of other vertices. The game ends once all vertices have been removed. Min seeks to minimize the number of brushes played during the game, while Max seeks to maximize it. When both players play optimally, the length of the game is the game brush number of the graph $G$ , denoted $b_g(G)$ . By considering strategies for both players and modelling the evolution of the game with differential equations, we provide an asymptotic value for the game brush number of the complete graph; namely, we show that $b_g(K_n) = (1+o(1))n^2/e$ . Using a fractional version of the game, we couple the game brush numbers of complete graphs and the binomial random graph $\mathcal{G}(n,p)$ . It is shown that for $pn \gg \ln n$ asymptotically almost surely $b_g(\mathcal{G}(n,p)) = (1 + o(1))p b_g(K_n) = (1 + o(1))pn^2/e$ . Finally, we study the relationship between the game brush number and the (original) brush number.

preprint2016arXiv

To catch a falling robber

We consider a Cops-and-Robber game played on the subsets of an $n$ -set. The robber starts at the full set; the cops start at the empty set. On each turn, the robber moves down one level by discarding an element, and each cop moves up one level by gaining an element. The question is how many cops are needed to ensure catching the robber when the robber reaches the middle level. Aaron Hill posed the problem and provided a lower bound of $2^{n/2}$ for even $n$ and $\binom{n}{\lceil n/2 \rceil}2^{-\lfloor n/2 \rfloor}$ for odd $n$ . We prove an upper bound (for all $n$ ) that is within a factor of $O(\ln n)$ times this lower bound.

preprint2014arXiv

Cops and Robbers is EXPTIME-complete

We investigate the computational complexity of deciding whether k cops can capture a robber on a graph G. In 1995, Goldstein and Reingold conjectured that the problem is EXPTIME-complete when both G and k are part of the input; we prove this conjecture.

preprint2014arXiv

The Game Saturation Number of a Graph

Given a family ${\mathcal F}$ and a host graph $H$ , a graph $G\subseteq H$ is ${\mathcal F}$ -saturated relative to $H$ if no subgraph of $G$ lies in ${\mathcal F}$ but adding any edge from $E(H)-E(G)$ to $G$ creates such a subgraph. In the ${\mathcal F}$ -saturation game on $H$ , players Max and Min alternately add edges of $H$ to $G$ , avoiding subgraphs in ${\mathcal F}$ , until $G$ becomes ${\mathcal F}$ -saturated relative to $H$ . They aim to maximize or minimize the length of the game, respectively; $\textrm{sat}_g({\mathcal F};H)$ denotes the length under optimal play (when Max starts). Let ${\mathcal O}$ denote the family of all odd cycles and ${\mathcal T}$ the family of $n$ -vertex trees, and write $F$ for ${\mathcal F}$ when ${\mathcal F}=\{F\}$ . Our results include $\textrm{sat}_g({\mathcal O};K_{2k})=k^2$ , $\textrm{sat}_g({\mathcal T};K_n)=\binom{n-2}{2}+1$ for $n\ge6$ , $\textrm{sat}_g(K_{1,3};K_n)=2\lfloor n/2 \rfloor$ for $n\ge8$ , $\textrm{sat}_g(K_{1,r+1};K_n)=\frac{rn}{2}-\frac{r^2}{8}+O(1)$ , and $|\textrm{sat}_g(P_4;K_n)-(4n-1)/5|\le 1$ . We also determine $\textrm{sat}_g(P_4;K_{m,n})$ ; with $m\ge n$ , it is $n$ when $n$ is even, $m$ when $n$ is odd and $m$ is even, and $m+\lfloor n/2 \rfloor$ when $mn$ is odd. Finally, we prove the lower bound $\textrm{sat}_g(C_4;K_{n,n})\ge\frac{1}{10.4}n^{13/12}-O(n^{35/36})$ . The results are very similar when Min plays first, except for the $P_4$ -saturation game on $K_{m,n}$ .

preprint2013arXiv

The capture time of the hypercube

In the game of Cops and Robbers, the capture time of a graph is the minimum number of moves needed by the cops to capture the robber, assuming optimal play. We prove that the capture time of the $n$ -dimensional hypercube is $Θ(n\ln n).$ Our methods include a novel randomized strategy for the players, which involves the analysis of the coupon-collector problem.

preprint2013arXiv

The robber strikes back

We consider the new game of Cops and Attacking Robbers, which is identical to the usual Cops and Robbers game except that if the robber moves to a vertex containing a single cop, then that cop is removed from the game. We study the minimum number of cops needed to capture a robber on a graph $G$ , written $cc(G)$ . We give bounds on $cc(G)$ in terms of the cop number of $G$ in the classes of bipartite graphs and diameter two, $K_{1,m}$ -free graphs.

preprint2012arXiv

Game matching number of graphs

We study a competitive optimization version of $α'(G)$ , the maximum size of a matching in a graph $G$ . Players alternate adding edges of $G$ to a matching until it becomes a maximal matching. One player (Max) wants that matching to be large; the other (Min) wants it to be small. The resulting sizes under optimal play when Max or Min starts are denoted $\Max(G)$ and $\Min(G)$, respectively. We show that always $|\Max(G)-\Min(G)|\le 1$. We obtain a sufficient condition for $\Max(G)=α'(G)$ that is preserved under cartesian product. In general, $\Max(G)\ge \frac23α'(G)$, with equality for many split graphs, while $\Max(G)\ge\frac34α'(G)$ when $G$ is a forest. Whenever $G$ is a 3-regular $n$ -vertex connected graph, $\Max(G) \ge n/3$, and there are such examples with $\Max(G)\le 7n/18$. For an $n$ -vertex path or cycle, the answer is roughly $n/7$ .

preprint2011arXiv

Chain-making games in grid-like posets

We study the Maker-Breaker game on the hypergraph of chains of fixed size in a poset. In a product of chains, the maximum size of a chain that Maker can guarantee building is $k-\lfloor r/2\rfloor$ , where $k$ is the maximum size of a chain in the product, and $r$ is the maximum size of a factor chain. We also study a variant in which Maker must follow the chain in order, called the {\it Walker-Blocker game}. In the poset consisting of the bottom $k$ levels of the product of $d$ arbitrarily long chains, Walker can guarantee a chain that hits all levels if $d\ge14$ ; this result uses a solution to Conway's Angel-Devil game. When d=2, the maximum that Walker can guarantee is only 2/3 of the levels, and 2/3 is asymptotically achievable in the product of two equal chains.

preprint2011arXiv

New results in $t$ -tone coloring of graphs

A $t$ -tone $k$ -coloring of $G$ assigns to each vertex of $G$ a set of $t$ colors from $\{1,..., k\}$ so that vertices at distance $d$ share fewer than $d$ common colors. The {\it $t$ -tone chromatic number} of $G$ , denoted $τ_t(G)$ , is the minimum $k$ such that $G$ has a $t$ -tone $k$ -coloring. Bickle and Phillips showed that always $τ_2(G) \le [Δ(G)]^2 + Δ(G)$ , but conjectured that in fact $τ_2(G) \le 2Δ(G) + 2$ ; we confirm this conjecture when $Δ(G) \le 3$ and also show that always $τ_2(G) \le \ceil{(2 + \sqrt{2})Δ(G)}$. For general $t$ we prove that $τ_t(G) \le (t^2+t)Δ(G)$ . Finally, for each $t\ge 2$ we show that there exist constants $c_1$ and $c_2$ such that for every tree $T$ we have $c_1 \sqrt{Δ(T)} \le τ_t(T) \le c_2\sqrt{Δ(T)}$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

William B. Kinnersley

Research overview

Is this your work?

11 publications

Catching an infinitely fast robber on a grid

Bounds on the localization number

Game Brush Number

To catch a falling robber

Cops and Robbers is EXPTIME-complete

The Game Saturation Number of a Graph

The capture time of the hypercube

The robber strikes back

Game matching number of graphs

Chain-making games in grid-like posets

New results in $t$ -tone coloring of graphs

See the researcher in context

Building this map preview

William B. Kinnersley

Research overview

Is this your work?

11 publications

Catching an infinitely fast robber on a grid

Bounds on the localization number

Game Brush Number

To catch a falling robber

Cops and Robbers is EXPTIME-complete

The Game Saturation Number of a Graph

The capture time of the hypercube

The robber strikes back

Game matching number of graphs

Chain-making games in grid-like posets

New results in ttt-tone coloring of graphs

See the researcher in context

Building this map preview

New results in $t$ -tone coloring of graphs