Page 1 Next

Displaying 1 – 20 of 51

Showing per page

A tandem version of the cops and robber game played on products of graphs

Nancy E. Clarke, Richard J. Nowakowski (2005)

Discussiones Mathematicae Graph Theory

In this version of the Cops and Robber game, the cops move in tandems, or pairs, such that they are at distance at most one from each other after every move. The problem is to determine, for a given graph G, the minimum number of tandems sufficient to guarantee a win for the cops. We investigate this game on three graph products, the Cartesian, categorical and strong products.

Colouring game and generalized colouring game on graphs with cut-vertices

Elżbieta Sidorowicz (2010)

Discussiones Mathematicae Graph Theory

For k ≥ 2 we define a class of graphs 𝓗 ₖ = {G: every block of G has at most k vertices}. The class 𝓗 ₖ contains among other graphs forests, Husimi trees, line graphs of forests, cactus graphs. We consider the colouring game and the generalized colouring game on graphs from 𝓗 ₖ.

Conway's Games and Some of their Basic Properties

Robin Nittka (2011)

Formalized Mathematics

We formulate a few basic concepts of J. H. Conway's theory of games based on his book [6]. This is a first step towards formalizing Conway's theory of numbers into Mizar, which is an approach to proving the existence of a FIELD (i.e., a proper class that satisfies the axioms of a real-closed field) that includes the reals and ordinals, thus providing a uniform, independent and simple approach to these two constructions that does not go via the rational numbers and hence does for example not need...

Discrepancy games.

Alon, Noga, Krivelevich, Michael, Spencer, Joel, Szabó, Tibor (2005)

The Electronic Journal of Combinatorics [electronic only]

Domination Game: Extremal Families for the 3/5-Conjecture for Forests

Michael A. Henning, Christian Löwenstein (2017)

Discussiones Mathematicae Graph Theory

In the domination game on a graph G, the players Dominator and Staller alternately select vertices of G. Each vertex chosen must strictly increase the number of vertices dominated. This process eventually produces a dominating set of G; Dominator aims to minimize the size of this set, while Staller aims to maximize it. The size of the dominating set produced under optimal play is the game domination number of G, denoted by γg(G). Kinnersley, West and Zamani [SIAM J. Discrete Math. 27 (2013) 2090-2107]...

Edge-disjoint odd cycles in graphs with small chromatic number

Claude Berge, Bruce Reed (1999)

Annales de l'institut Fourier

For a simple graph, we consider the minimum number of edges which block all the odd cycles and the maximum number of odd cycles which are pairwise edge-disjoint. When these two coefficients are equal, interesting consequences appear. Similar problems (but interchanging “vertex-disjoint odd cycles” and “edge-disjoint odd cycles”) have been considered in a paper by Berge and Fouquet.

Guessing secrets.

Chung, Fan, Graham, Ronald, Leighton, Tom (2001)

The Electronic Journal of Combinatorics [electronic only]

How Long Can One Bluff in the Domination Game?

Boštan Brešar, Paul Dorbec, Sandi Klavžar, Gašpar Košmrlj (2017)

Discussiones Mathematicae Graph Theory

The domination game is played on an arbitrary graph G by two players, Dominator and Staller. The game is called Game 1 when Dominator starts it, and Game 2 otherwise. In this paper bluff graphs are introduced as the graphs in which every vertex is an optimal start vertex in Game 1 as well as in Game 2. It is proved that every minus graph (a graph in which Game 2 finishes faster than Game 1) is a bluff graph. A non-trivial infinite family of minus (and hence bluff) graphs is established. minus graphs...

Modeling shortest path games with Petri nets: a Lyapunov based theory

Julio Clempner (2006)

International Journal of Applied Mathematics and Computer Science

In this paper we introduce a new modeling paradigm for shortest path games representation with Petri nets. Whereas previous works have restricted attention to tracking the net using Bellman's equation as a utility function, this work uses a Lyapunov-like function. In this sense, we change the traditional cost function by a trajectory-tracking function which is also an optimal cost-to-target function. This makes a significant difference in the conceptualization of the problem domain, allowing the...

Currently displaying 1 – 20 of 51

Page 1 Next