Zobrazeno 1 - 10
of 363
pro vyhledávání: '"Eternal Domination"'
Dominating sets in graphs are often used to model some monitoring of the graph: guards are posted on the vertices of the dominating set, and they can thus react to attacks occurring on the unguarded vertices by moving there (yielding a new set of gua
Externí odkaz:
http://arxiv.org/abs/2401.10584
Autor:
Devvrit, Fnu, Krim-Yee, Aaron, Kumar, Nithish, MacGillivray, Gary, Seamone, Ben, Virgile, Virgélot, Xu, AnQi
This paper initiates the study of fractional eternal domination in graphs, a natural relaxation of the well-studied eternal domination problem. We study the connections to flows and linear programming in order to obtain results on the complexity of d
Externí odkaz:
http://arxiv.org/abs/2304.11795
In m-eternal domination attacker and defender play on a graph. Initially, the defender places guards on vertices. In each round, the attacker chooses a vertex to attack. Then, the defender can move each guard to a neighboring vertex and must move a g
Externí odkaz:
http://arxiv.org/abs/2301.05155
We study the m-eternal domination problem from the perspective of the attacker. For many graph classes, the minimum required number of guards to defend eternally is known. By definition, if the defender has less than the required number of guards, th
Externí odkaz:
http://arxiv.org/abs/2204.02720
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 guar
Externí odkaz:
http://arxiv.org/abs/2112.03107
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
We study the relationship between the eternal domination number of a graph and its clique covering number using both large-scale computation and analytic methods. In doing so, we answer two open questions of Klostermeyer and Mynhardt. We show that th
Externí odkaz:
http://arxiv.org/abs/2110.09732
Given a graph $G$, guards are placed on vertices of $G$. Then vertices are subject to an infinite sequence of attacks so that each attack must be defended by a guard moving from a neighboring vertex. The m-eternal domination number is the minimum num
Externí odkaz:
http://arxiv.org/abs/1907.07910
An eternal dominating set of a graph $G$ is a set of vertices (or "guards") which dominates $G$ and which can defend any infinite series of vertex attacks, where an attack is defended by moving one guard along an edge from its current position to the
Externí odkaz:
http://arxiv.org/abs/1902.00799
Publikováno v:
AKCE International Journal of Graphs and Combinatorics, Vol 17, Iss 3, Pp 708-712 (2020)
We show sharp Vizing-type inequalities for eternal domination. Namely, we prove that for any graphs G and H, where is the eternal domination function, α is the independence number, and is the strong product of graphs. This addresses a question of Kl
Externí odkaz:
https://doaj.org/article/c7bda301a7e64f2a925baca3982acfa4
