Note on a pursuit game played on graphs

In [1] Aigner and Fromme considered a game played on a finite graph G where m pursuers try to catch one evader. They introduced c(G) as the minimal number m of pursuers that are sufficient to catch the evader and, among other things, they asked if it is true that c(G) ≤ k whenever the maximal degree of G is at most k. In the present note we give a negative answer to this question by showing that, for all positive integers k, n (k ≥ 3), there exists a k-regular graph G with c(G) ≥ n.     

On a pursuit game on cayley graphs

The game cops and robbers is considered on Cayley graphs of abelian groups. It is proved that if the graph has degreed, then [(d+1)/2] cops are sufficient to catch one robber. This bound is often best possible.     

The domination game played on diameter 2 graphs

Aequationes mathematicae - Let $$\gamma _g(G)$$ be the game domination number of a graph G. It is proved that if $$\mathrm{diam}(G) = 2$$ , then $$\gamma _g(G) \le \left\lceil \frac{n(G)}{2}...     

A solitaire game played on 2-colored graphs

We introduce a solitaire game played on a graph. Initially one disk is placed at each vertex, one face green and the other red, oriented with either color facing up. Each move of the game consists of selecting a vertex whose disk shows green, flipping over the disks at neighboring vertices, and deleting the selected vertex. The game is won if all vertices are eliminated. We derive a simple parity-based necessary condition for winnability of a given game instance. By studying graph operations that construct new graphs from old ones, we obtain broad classes of graphs where this condition also suffices, thus characterizing the winnable games on such graphs. Concerning two familiar (but narrow) classes of graphs, we show that for trees a game is winnable if and only if the number of green vertices is odd, and for n-cubes a game is winnable if and only if the number of green vertices is even and not all vertices have the same color. We provide a linear-time algorithm for deciding winnability for games on maximal outerplanar graphs. We reduce the decision problem for winnability of a game on an arbitrary graph G to winnability of games on its blocks, and to winnability on homeomorphic images of G obtained by contracting edges at 2-valent vertices.     

On the max-min pursuit game

The max-min linear pursuit game with quadratic performance measure is examined by means of an approximation by a finite sequence of ‘open-loop’ max-min control stages. It is shown that under mild conditions the finite approximation provides a satisfactory representation of the actual game. The limiting behaviour (as the number of stages approaches infinity) is also discussed.     

On a linear pursuit game with an unknown trap

A linear pursuit game with a trap, the location of which is unknown to the evader, is defined and investigated. The cases in which one of the players has complete energy dominance over his adversary are solved completely. In the general case, when no player dominates, the solution is indicated for the two-stage game.This research was supported in part by the Technion Fund for promotion of research.     

An excluded minor theorem for the octahedron

In this article it is shown that every 4‐connected graph that does not contain a minor isomorphic to the octahedron is isomorphic to the square of an odd cycle. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 95–100, 1999     

Note on a compactness characterization via a pursuit game

In (Alexander et?al. Geom Dedicata 149:275?C290, 2010), the authors study a pursuit-evasion game in CAT(0) spaces and arrive at the following topological characterization of the underlying CAT(0) space: the space is compact if and only if the pursuer always wins. In the present note, we, however, give an example of an unbounded CAT(0) space where the pursuer always wins, and hence strongly disprove the above statement on compactness.     

Four problems on graphs with excluded minors

The four problems we consider are the Chinese postman, odd cut, co-postman, and odd circuit problems. Seymour's characterization of matroids having the max-flow min-cut property can be specialized to each of these four problems to show that the property holds whenever the graph has no certain excluded minor. We develop a framework for characterizing graphs not having these excluded minors and use the excluded minor characterizations to solve each of the four optimization problems. In this way, a constructive proof of Seymour's theorem is given for these special cases. We also show how to solve the Chinese postman problem on graphs having no four-wheel minor, where the max-flow min-cut property need not hold.     

Bicyclic graphs for which the least eigenvalue is minimum

The spread of a graph is defined to be the difference between the greatest eigenvalue and the least eigenvalue of the adjacency matrix of the graph. In this paper we determine the unique graph with minimum least eigenvalue among all connected bicyclic graphs of order n. Also, we determine the unique graph with maximum spread in this class for each n?28.     

On the minor-minimal 2-connected graphs having a fixed minor

Let H be a graph with κ₁ components and κ₂ blocks, and let G be a minor-minimal 2-connected graph having H as a minor. This paper proves that |E(G)|−|E(H)|(κ₁−1)+β(κ₂−1) for all (,β) such that +β5,2+5β20, and β3. Moreover, if one of the last three inequalities fails, then there are graphs G and H for which the first inequality fails.     

On a game of optimal pursuit of an object by two others

A game problem of the simple pursuit of one object by two others, the former having a speed advantage, is analyzed. The duration of the game is fixed. The payoff functional is the distance between the object being pursued and the pursuer closest to it when the game terminates. Similar problems were examined in /1–7/.     

On cubic graphs which are irreducible for nonorientable surfaces

Let ∑?_n denote the nonorientable surface of nonorientable genus n. A graph G is irreducible for ∑?_n if G does not embed in ∑?_n but any proper subgraph does embed. Let I₃∑?_n) denote the set of cubic irreducible graphs for ∑?_n. This note provesTheorem. I₃(∑?_n) is finite for eachn.     

On graphs for which the connected domination number is at most the total domination number

In this note, we give a finite forbidden subgraph characterization of the connected graphs for which any non-trivial connected induced subgraph has the property that the connected domination number is at most the total domination number. This question is motivated by the fact that any connected dominating set of size at least 2 is in particular a total dominating set. It turns out that in this characterization, the total domination number can equivalently be substituted by the upper total domination number, the paired-domination number and the upper paired-domination number, respectively. Another equivalent condition is given in terms of structural domination.     

A short note about pursuit games played on a graph with a given genus

On a finite simple graph G = (X,E), p players pursuers $\text{A}{}_1\text{, ∴, A}{}_{\mathrm{p}}$ and one player evader B who move in turn along the edges of G are considered. The p pursuers $\text{A}{}_1\text{, ∴, A}{}_{\mathrm{p}}$ want to catch B who tries to escape. R. Nowakowski and P. Winkler [Discrete Math.43 (1983), 235–240] and A. Quilliot [“Thèse de 3° cycle,” pp. 131–145, Université de Paris VI, 1978] already characterized the graphs such that one pursuer is sufficient to catch the evader B. Very recently, M. Aigner and M. Fromme [Appl. Discrete Math., in press] proved that if G is a planar graph, three pursuers are sufficient to catch the evader B. This result is extended, showing that if G is a graph with a given genus k, then 3 + 2k pursuers are enough to “arrest” the evader B.