4 research outputs found
Maker-Breaker games on random geometric graphs
No full textIn a Maker-Breaker game on a graph G, Breaker and Maker alternately claim edges of G. Maker wins if, after all edges have been claimed, the graph induced by his edges has some desired property. We consider four Maker-Breaker games played on random geometric graphs. For each of our four games we show that if we add edges between n points chosen uniformly at random in the unit square by order of increasing edge-length then, with probability tending to one as n ∞, the graph becomes Maker-win the very moment it satisfies a simple necessary condition. In particular, with high probability, Maker wins the connectivity game as soon as the minimum degree is at least two; Maker wins the Hamilton cycle game as soon as the minimum degree is at least four; Maker wins the perfect matching game as soon as the minimum degree is at least two and every edge has at least three neighbouring vertices; and Maker wins the H-game as soon as there is a subgraph from a finite list of “minimal graphs.” These results also allow us to give precise expressions for the limiting probability that G(n, r) is Maker-win in each case, where G(n, r) is the graph on n points chosen uniformly at random on the unit square with an edge between two points if and only if their distance is at most r.</p
Cops and Robbers on Geometric Graphs
No full textCops and robbers is a turn-based pursuit game played on a graph G. One robber is pursued by a set of cops. In each round, these agents move between vertices along the edges of the graph. The cop number c(G) denotes the minimum number of cops required to catch the robber in finite time. We study the cop number of geometric graphs. For points x 1, . . ., xn ∈ ℝ2, and r ∈ ℝ+, the vertex set of the geometric graph G(x 1, . . ., xn; r) is the graph on these npoints, with xi, xj adjacent when ∥xi − xj ∥ ≤ r. We prove that c(G) ≤ 9 for any connected geometric graph G in ℝ2 and we give an example of a connected geometric graph with c(G) = 3. We improve on our upper bound for random geometric graphs that are sufficiently dense. Let (n,r) denote the probability space of geometric graphs with nvertices chosen uniformly and independently from [0,1]2. For G ∈ (n,r), we show that with high probability (w.h.p.), ifr ≥ K 1 (log n/n)1/4 then c(G) ≤ 2, and if r ≥ K 2(log n/n)1/5 then c(G) = 1, where K 1, K 2 > 0 are absolute constants. Finally, we provide a lower bound near the connectivity regime of (n,r): if r ≤ K 3 log n/ then c(G) > 1 w.h.p., where K 3 > 0 is an absolute constant.</p
Figure 12 in Aeolidia papillosa (Linnaeus, 1761) (Mollusca: Heterobranchia: Nudibranchia), single species or a cryptic species complex? A morphological and molecular study
No full textFigure 12. Photographs of live Aeolidia loui sp. nov. specimens: A, holotype, specimen from USA, California, photo by Terrence M. Gosliner (CASIZ 182214); B, specimen from USA, California, photo by Patricia Alvarez-Campos and Greg Rouse; C, specimen from USA, Oregon, photo by Nancy Treneman; C, specimen from USA, California, photo by Gary McDonald; E, detail of the rhinophores of the specimen from USA, California, photo by Dave Behrens.Published as part of Kienberger, Karen, Carmona, Leila, Pola, Marta, Padula, Vinicius, Gosliner, Terrence M. & Cervera, Juan Lucas, 2016, Aeolidia papillosa (Linnaeus, 1761) (Mollusca: Heterobranchia: Nudibranchia), single species or a cryptic species complex? A morphological and molecular study, pp. 481-506 in Zoological Journal of the Linnean Society 177 (3) on page 500, DOI: 10.1111/zoj.12379, http://zenodo.org/record/536518
