The Experts below are selected from a list of 120 Experts worldwide ranked by ideXlab platform
Tal Orenshtein - One of the best experts on this subject based on the ideXlab platform.
-
Infinite excursions of router walks on regular trees
The Electronic Journal of Combinatorics, 2017Co-Authors: Sebastian Mueller, Tal OrenshteinAbstract:A router configuration on a graph contains in every Vertex an infinite ordered sequence of routers, each is pointing to a neighbor of the Vertex. After sampling a configuration according to some probability measure, a router walk is a deterministic process: at each step it chooses the next unused router in its current location, and uses it to jump to the Neighboring Vertex to which it points. Routers walks capture many aspects of the expected behavior of simple random walks. However, this similarity breaks down for the property of having an infinite excursion. In this paper we study that question for natural random configuration models on regular trees. Our results suggest that in this context the router model behaves like the simple random walk unless it is not "close to" the standard rotor-router model.
-
Infinite excursions of rotor walks on regular trees
arXiv: Probability, 2015Co-Authors: Sebastian Mueller, Tal OrenshteinAbstract:A rotor configuration on a graph contains in every Vertex an infinite ordered sequence of rotors, each is pointing to a neighbor of the Vertex. After sampling a configuration according to some probability measure, a rotor walk is a deterministic process: at each step it chooses the next unused rotor in its current location, and uses it to jump to the Neighboring Vertex to which it points. Rotor walks capture many aspects of the expected behavior of simple random walks. However, this similarity breaks down for the property of having an infinite excursion. In this paper we study that question for natural random configuration models on regular trees. Our results suggest that in this context the rotor model behaves like the simple random walk unless it is not "close to" the standard rotor-router model.
-
Greedy Random Walk
Combinatorics Probability and Computing, 2013Co-Authors: Tal Orenshtein, Igor ShinkarAbstract:We study a discrete time self interacting random process on graphs, which we call Greedy Random Walk. The walker is located initially at some Vertex. As time evolves, each Vertex maintains the set of adjacent edges touching it that have not been crossed yet by the walker. At each step, the walker being at some Vertex, picks an adjacent edge among the edges that have not traversed thus far according to some (deterministic or randomized) rule. If all the adjacent edges have already been traversed, then an adjacent edge is chosen uniformly at random. After picking an edge the walk jumps along it to the Neighboring Vertex. We show that the expected edge cover time of the greedy random walk is linear in the number of edges for certain natural families of graphs. Examples of such graphs include the complete graph, even degree expanders of logarithmic girth, and the hypercube graph. We also show that GRW is transient in $\Z^d$ for all $d \geq 3$.
Reza Zamani - One of the best experts on this subject based on the ideXlab platform.
-
Revolutionaries and spies: Spy-good and spy-bad graphs
arXiv: Discrete Mathematics, 2012Co-Authors: Jane Butterfield, Douglas B. West, Daniel W. Cranston, Gregory J. Puleo, Reza ZamaniAbstract:We study a game on a graph $G$ played by $r$ {\it revolutionaries} and $s$ {\it spies}. Initially, revolutionaries and then spies occupy vertices. In each subsequent round, each revolutionary may move to a Neighboring Vertex or not move, and then each spy has the same option. The revolutionaries win if $m$ of them meet at some Vertex having no spy (at the end of a round); the spies win if they can avoid this forever. Let $\sigma(G,m,r)$ denote the minimum number of spies needed to win. To avoid degenerate cases, assume $|V(G)|\ge r-m+1\ge\floor{r/m}\ge 1$. The easy bounds are then $\floor{r/m}\le \sigma(G,m,r)\le r-m+1$. We prove that the lower bound is sharp when $G$ has a rooted spanning tree $T$ such that every edge of $G$ not in $T$ joins two vertices having the same parent in $T$. As a consequence, $\sigma(G,m,r)\le\gamma(G)\floor{r/m}$, where $\gamma(G)$ is the domination number; this bound is nearly sharp when $\gamma(G)\le m$. For the random graph with constant edge-probability $p$, we obtain constants $c$ and $c'$ (depending on $m$ and $p$) such that $\sigma(G,m,r)$ is near the trivial upper bound when $r c'\ln n$. For the hypercube $Q_d$ with $d\ge r$, we have $\sigma(G,m,r)=r-m+1$ when $m=2$, and for $m\ge 3$ at least $r-39m$ spies are needed. For complete $k$-partite graphs with partite sets of size at least $2r$, the leading term in $\sigma(G,m,r)$ is approximately $\frac{k}{k-1}\frac{r}{m}$ when $k\ge m$. For $k=2$, we have $\sigma(G,2,r)=\bigl\lceil{\frac{\floor{7r/2}-3}5}\bigr\rceil$ and $\sigma(G,3,r)=\floor{r/2}$, and in general $\frac{3r}{2m}-3\le \sigma(G,m,r)\le\frac{(1+1/\sqrt3)r}{m}$.
-
Revolutionaries and spies: Spy-good and spy-bad graphs
Theoretical Computer Science, 2012Co-Authors: Jane Butterfield, Douglas B. West, Daniel W. Cranston, Gregory J. Puleo, Reza ZamaniAbstract:AbstractWe study a game on a graph G played by r revolutionaries and s spies. Initially, revolutionaries and then spies occupy vertices. In each subsequent round, each revolutionary may move to a Neighboring Vertex or not move, and then each spy has the same option. The revolutionaries win if m of them meet at some Vertex having no spy (at the end of a round); the spies win if they can avoid this forever.Let σ(G,m,r) denote the minimum number of spies needed to win. To avoid degenerate cases, assume |V(G)|≥r−m+1≥⌊r/m⌋≥1. The easy bounds are then ⌊r/m⌋≤σ(G,m,r)≤r−m+1. We prove that the lower bound is sharp when G has a rooted spanning tree T such that every edge of G not in T joins two vertices having the same parent in T. As a consequence, σ(G,m,r)≤γ(G)⌊r/m⌋, where γ(G) is the domination number; this bound is nearly sharp when γ(G)≤m.For the random graph with constant edge-probability p, we obtain constants c and c′ (depending on m and p) such that σ(G,m,r) is near the trivial upper bound when rc′lnn. For the hypercube Qd with d≥r, we have σ(G,m,r)=r−m+1 when m=2, and for m≥3 at least r−39m spies are needed.For complete k-partite graphs with partite sets of size at least 2r, the leading term in σ(G,m,r) is approximately kk−1rm when k≥m. For k=2, we have σ(G,2,r)=⌈⌊7r/2⌋−35⌉ and σ(G,3,r)=⌊r/2⌋, and in general 3r2m−3≤σ(G,m,r)≤(1+1/3)rm
Douglas B. West - One of the best experts on this subject based on the ideXlab platform.
-
Acquisition-extremal graphs
Discrete Applied Mathematics, 2013Co-Authors: Timothy D. Lesaulnier, Douglas B. WestAbstract:A total acquisition move in a weighted graph G moves all weight from a Vertex u to a Neighboring Vertex v, provided that before this move the weight on v is at least the weight on u. The total acquisition number, a"t(G), is the minimum number of vertices with positive weight that remain in G after a sequence of total acquisition moves, starting with a uniform weighting of the vertices of G. For n>=2, Lampert and Slater showed that a"t(G)@?n+13 when G has n vertices, and this is sharp. We characterize the graphs achieving equality: a"t(G)=|V(G)|+13 if and only if G@?T@?{P"2,C"5}, where T is the family of trees that can be constructed from P"5 by iteratively growing paths with three edges from neighbors of leaves.
-
Total Acquisition in Graphs
SIAM Journal on Discrete Mathematics, 2013Co-Authors: Timothy D. Lesaulnier, Douglas B. West, Noah Prince, Paul S. Wenger, Pratik WorahAbstract:Let $G$ be a weighted graph in which each Vertex initially has weight $1$. A total acquisition move transfers all the weight from a Vertex $u$ to a Neighboring Vertex $v$, under the condition that before the move the weight on $v$ is at least as large as the weight on $u$. The (total) acquisition number of $G$, written $a_{t}(G)$, is the minimum size of the set of vertices with positive weight after a sequence of total acquisition moves. Among connected $n$-Vertex graphs, $a_{t}(G)$ is maximized by trees. The maximum is $\Theta(\sqrt{n\lg n})$ for trees with diameter $4$ or $5$. It is $\left\lfloor{(n+1)/3}\right\rfloor$ for trees with diameter between $6$ and $\frac23(n+1)$, and it is $\left\lceil{(2n-1-D)/4}\right\rceil$ for trees with diameter $D$ when $\frac{2}{3}(n+1)\le D\le n-1$. We characterize trees with acquisition number 1, which permits testing $a_{t}(G)\le k$ in time $O(n^{k+2})$ on trees. If $G\ne C_5$, then $\min\{a_{t}(G),a_{t}(\overline{G})\}=1$. If $G$ has diameter $2$, then $a_{t}(G)\le...
-
Revolutionaries and spies: Spy-good and spy-bad graphs
arXiv: Discrete Mathematics, 2012Co-Authors: Jane Butterfield, Douglas B. West, Daniel W. Cranston, Gregory J. Puleo, Reza ZamaniAbstract:We study a game on a graph $G$ played by $r$ {\it revolutionaries} and $s$ {\it spies}. Initially, revolutionaries and then spies occupy vertices. In each subsequent round, each revolutionary may move to a Neighboring Vertex or not move, and then each spy has the same option. The revolutionaries win if $m$ of them meet at some Vertex having no spy (at the end of a round); the spies win if they can avoid this forever. Let $\sigma(G,m,r)$ denote the minimum number of spies needed to win. To avoid degenerate cases, assume $|V(G)|\ge r-m+1\ge\floor{r/m}\ge 1$. The easy bounds are then $\floor{r/m}\le \sigma(G,m,r)\le r-m+1$. We prove that the lower bound is sharp when $G$ has a rooted spanning tree $T$ such that every edge of $G$ not in $T$ joins two vertices having the same parent in $T$. As a consequence, $\sigma(G,m,r)\le\gamma(G)\floor{r/m}$, where $\gamma(G)$ is the domination number; this bound is nearly sharp when $\gamma(G)\le m$. For the random graph with constant edge-probability $p$, we obtain constants $c$ and $c'$ (depending on $m$ and $p$) such that $\sigma(G,m,r)$ is near the trivial upper bound when $r c'\ln n$. For the hypercube $Q_d$ with $d\ge r$, we have $\sigma(G,m,r)=r-m+1$ when $m=2$, and for $m\ge 3$ at least $r-39m$ spies are needed. For complete $k$-partite graphs with partite sets of size at least $2r$, the leading term in $\sigma(G,m,r)$ is approximately $\frac{k}{k-1}\frac{r}{m}$ when $k\ge m$. For $k=2$, we have $\sigma(G,2,r)=\bigl\lceil{\frac{\floor{7r/2}-3}5}\bigr\rceil$ and $\sigma(G,3,r)=\floor{r/2}$, and in general $\frac{3r}{2m}-3\le \sigma(G,m,r)\le\frac{(1+1/\sqrt3)r}{m}$.
-
Revolutionaries and spies: Spy-good and spy-bad graphs
Theoretical Computer Science, 2012Co-Authors: Jane Butterfield, Douglas B. West, Daniel W. Cranston, Gregory J. Puleo, Reza ZamaniAbstract:AbstractWe study a game on a graph G played by r revolutionaries and s spies. Initially, revolutionaries and then spies occupy vertices. In each subsequent round, each revolutionary may move to a Neighboring Vertex or not move, and then each spy has the same option. The revolutionaries win if m of them meet at some Vertex having no spy (at the end of a round); the spies win if they can avoid this forever.Let σ(G,m,r) denote the minimum number of spies needed to win. To avoid degenerate cases, assume |V(G)|≥r−m+1≥⌊r/m⌋≥1. The easy bounds are then ⌊r/m⌋≤σ(G,m,r)≤r−m+1. We prove that the lower bound is sharp when G has a rooted spanning tree T such that every edge of G not in T joins two vertices having the same parent in T. As a consequence, σ(G,m,r)≤γ(G)⌊r/m⌋, where γ(G) is the domination number; this bound is nearly sharp when γ(G)≤m.For the random graph with constant edge-probability p, we obtain constants c and c′ (depending on m and p) such that σ(G,m,r) is near the trivial upper bound when rc′lnn. For the hypercube Qd with d≥r, we have σ(G,m,r)=r−m+1 when m=2, and for m≥3 at least r−39m spies are needed.For complete k-partite graphs with partite sets of size at least 2r, the leading term in σ(G,m,r) is approximately kk−1rm when k≥m. For k=2, we have σ(G,2,r)=⌈⌊7r/2⌋−35⌉ and σ(G,3,r)=⌊r/2⌋, and in general 3r2m−3≤σ(G,m,r)≤(1+1/3)rm
-
Pebbling and Optimal Pebbling in Graphs
arXiv: Combinatorics, 2005Co-Authors: David P. Bunde, Erin Wolf Chambers, Daniel W. Cranston, Kevin G. Milans, Douglas B. WestAbstract:Given a distribution of pebbles on the vertices of a graph G, a {\it pebbling move} takes two pebbles from one Vertex and puts one on a Neighboring Vertex. The {\it pebbling number} \Pi(G) is the minimum k such that for every distribution of k pebbles and every Vertex r, it is possible to move a pebble to r. The {\it optimal pebbling number} \Pi_{OPT}(G) is the minimum k such that some distribution of k pebbles permits reaching each Vertex. We give short proofs of prior results on these parameters for paths, cycles, trees, and hypercubes, a new linear-time algorithm for computing \Pi(G) on trees, and new results on \Pi_{OPT}(G). If G is a connected n-Vertex graph, then \Pi_{OPT}(G)\le\ceiling{2n/3}, with equality for paths and cycles. If \bf{G} is the family of n-Vertex connected graphs with minimum degree k, then 2.4\le \max_{G\in \bf{G}} \Pi_{OPT}(G) \frac{k+1}{n}\le 4 when k>15 and k is a multiple of 3. Finally, \Pi_{OPT}(G)\le 4^tn/((k-1)^t+4^t) when G is a connected n-Vertex graph with minimum degree k and girth at least 2t+1. For t=2, a more precise version of this last bound is \Pi_{OPT}(G)\le 16n/(k^2+17).
William F. Klostermeyer - One of the best experts on this subject based on the ideXlab platform.
-
Bounds for the $m$-Eternal Domination Number of a Graph
Contributions to Discrete Mathematics, 2017Co-Authors: Michael A. Henning, William F. Klostermeyer, Gary MacgillivrayAbstract:Mobile guards on the vertices of a graph are used to defend the graph against an infinite sequence of attacks on vertices. A guard must move from a Neighboring Vertex to an attacked Vertex (we assume attacks happen only at vertices containing no guard and that each Vertex contains at most one guard). More than one guard is allowed to move in response to an attack. The $m$-eternaldomination number, $\edom(G)$, of a graph $G$ is the minimum number of guards needed to defend $G$ against any such sequence. We show that if $G$ is a connected graph with minimum degree at least~$2$ and of order~$n \ge 5$, then $\edom(G) \le \left\lfloor \frac{n-1}{2} \right\rfloor$, and this bound is tight. We also prove that if $G$ is a cubic bipartite graph of order~$n$, then $\edom(G) \le \frac{7n}{16}$.
-
Eternal Independent Sets in Graphs
Theory and Applications of Graphs, 2016Co-Authors: Yair Caro, William F. KlostermeyerAbstract:The use of mobile guards to protect a graph has received much attention in the literature of late in the form of eternal dominating sets, eternal Vertex covers and other models of graph protection. In this paper, eternal independent sets are introduced. These are independent sets such that the following can be iterated forever: a Vertex in the independent set can be replaced with a Neighboring Vertex and the resulting set is independent.
-
Trees with large m -eternal domination number
Discrete Applied Mathematics, 2016Co-Authors: Michael A. Henning, William F. KlostermeyerAbstract:Mobile guards on the vertices of a graph are used to defend the graph against an infinite sequence of attacks on vertices. A guard must move from a Neighboring Vertex to an attacked Vertex (we assume attacks happen only at vertices containing no guard and that each Vertex contains at most one guard). More than one guard is allowed to move in response to an attack. The m -eternal domination number, γ m ∞ ( G ) , of a graph G is the minimum number of guards needed to defend G against any such sequence. We characterize the class of trees of orderź n with maximum possible m -eternal domination number, which is ź n 2 ź .
-
Foolproof eternal domination in the all-guards move model
Mathematica Slovaca, 2012Co-Authors: William F. Klostermeyer, Gary MacgillivrayAbstract:The eternal domination problem requires a graph be protected against an infinitely long sequence of attacks at vertices, by guards located at vertices, with the requirement that the configuration of guards induces a dominating set at all times. An attack is defended by sending a guard from a Neighboring Vertex to the attacked Vertex. We allow all guards to move to Neighboring vertices in response to an attack, but allow the attacked Vertex to choose which Neighboring guard moves to the attacked Vertex. This is the all-guards move version of the “foolproof” eternal domination problem that has been previously studied. We present some results and conjectures on this problem.
-
Vertex covers and eternal dominating sets
Discrete Applied Mathematics, 2012Co-Authors: William F. Klostermeyer, C.m. MynhardtAbstract:AbstractThe eternal domination problem requires a graph to be protected against an infinitely long sequence of attacks on vertices by guards located at vertices, the configuration of guards inducing a dominating set at all times. An attack at a Vertex with no guard is defended by sending a guard from a Neighboring Vertex to the attacked Vertex. We allow any number of guards to move to Neighboring vertices at the same time in response to an attack. We compare the eternal domination number with the Vertex cover number of a graph. One of our main results is that the eternal domination number is less than the Vertex cover number of any graph of minimum degree at least two having girth at least nine
Alexander E. Holroyd - One of the best experts on this subject based on the ideXlab platform.
-
Escape of resources in distributed clustering processes
arXiv: Probability, 2010Co-Authors: Jacob Van Den Berg, Marcelo R. Hilario, Alexander E. HolroydAbstract:In a distributed clustering algorithm introduced by Coffman, Courtois, Gilbert and Piret \cite{coffman91}, each Vertex of $\mathbb{Z}^d$ receives an initial amount of a resource, and, at each iteration, transfers all of its resource to the Neighboring Vertex which currently holds the maximum amount of resource. In \cite{hlrnss} it was shown that, if the distribution of the initial quantities of resource is invariant under lattice translations, then the flow of resource at each Vertex eventually stops almost surely, thus solving a problem posed in \cite{berg91}. In this article we prove the existence of translation-invariant initial distributions for which resources nevertheless escape to infinity, in the sense that the the final amount of resource at a given Vertex is strictly smaller in expectation than the initial amount. This answers a question posed in \cite{hlrnss}.
-
Escape of resources in a distributed clustering process
Electronic Communications in Probability, 2010Co-Authors: Jacob Van Den Berg, Marcelo R. Hilario, Alexander E. HolroydAbstract:In a distributed clustering algorithm introduced by Coffman, Courtois, Gilbert and Piret [1], each Vertex of $\mathbb{Z}^d$ receives an initial amount of a resource, and, at each iteration, transfers all of its resource to the Neighboring Vertex which currently holds the maximum amount of resource. In [4] it was shown that, if the distribution of the initial quantities of resource is invariant under lattice translations, then the flow of resource at each Vertex eventually stops almost surely, thus solving a problem posed in [2]. In this article we prove the existence of translation-invariant initial distributions for which resources nevertheless escape to infinity, in the sense that the the final amount of resource at a given Vertex is strictly smaller in expectation than the initial amount. This answers a question posed in [4].
