Zobrazeno 1 - 10
of 798
pro vyhledávání: '"05c57"'
Autor:
Vilkas, Timo
We consider the following combinatorial two-player game: On the random tree arising from a branching process, each round one player (Breaker) deletes an edge and by that removes the descendant and all its progeny, while the other (Maker) fixates an e
Externí odkaz:
http://arxiv.org/abs/2412.08334
We study a discrete-time model for the spread of information in a graph, motivated by the idea that people believe a story when they learn of it from two different origins. Similar to the burning number, in this problem, information spreads in rounds
Externí odkaz:
http://arxiv.org/abs/2411.02050
Chip-firing is a combinatorial game played on a graph in which we place and disperse chips on vertices until a stable state is reached. We study a chip-firing variant played on an infinite rooted directed $k$-ary tree, where we place $k^\ell$ chips o
Externí odkaz:
http://arxiv.org/abs/2410.23265
Deduction is a recently introduced graph searching process in which searchers clear the vertex set of a graph with one move each, with each searcher's movement determined by which of its neighbors are protected by other searchers. In this paper, we s
Externí odkaz:
http://arxiv.org/abs/2410.22962
Zero forcing is a graph propagation process for which vertices fill-in (or propagate information to) neighbor vertices if all neighbors except for one, are filled. The zero-forcing number is the smallest number of vertices that must be filled to begi
Externí odkaz:
http://arxiv.org/abs/2410.17440
Brushing of graphs is a graph searching process in which the searching agents are called brushes. We focus on brushing directed graphs based on a new model in which the brushes can only travel in the same direction as the orientation of the arcs that
Externí odkaz:
http://arxiv.org/abs/2410.04559
Chip-firing is a combinatorial game played on an undirected graph in which we place chips on vertices. We study chip-firing on an infinite binary tree in which we add a self-loop to the root to ensure each vertex has degree 3. A vertex can fire if th
Externí odkaz:
http://arxiv.org/abs/2410.00039
Autor:
Barnett, Andrea, Bond, Robert, Macias, Anthony, Mattman, Thomas W., Parnell, Bill, Schoenfield, Ely
We use Hartnell's model for virus spread on a graph, also known as firefighting. For rooted trees, we propose an Unburning Algorithm, a type of greedy algorithm starting from the leaves and working back towards the root. We show that the algorithm sa
Externí odkaz:
http://arxiv.org/abs/2409.14303
Given a graph $G$ and a family of graphs $\cal F$, an $\cal F$-isolating set, as introduced by Caro and Hansberg, is any set $S\subset V(G)$ such that $G - N[S]$ contains no member of $\cal F$ as a subgraph. In this paper, we introduce a game in whic
Externí odkaz:
http://arxiv.org/abs/2409.14180
We introduce the game of Cat Herding, where an omnipresent herder slowly cuts down a graph until an evasive cat player has nowhere to go. The number of cuts made is the score of a game, and we study the score under optimal play. In this paper, we beg
Externí odkaz:
http://arxiv.org/abs/2409.13685