Fractional eternal domination: securely distributing resources across a network

MaRDI QIDQ6434055zbMATH OpenFDO

Authors Fnu Devvrit, Aaron Krim-Yee, Nithish Kumar, Gary MacGillivray, Ben Seamone, Virgélot Virgile, Anqi Xu

Publication date 23 April 2023

Mathematics Subject Classification ID

Flows in graphs (05C21) Games on graphs (graph-theoretic aspects) (05C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Fractional graph theory, fuzzy graph theory (05C72) Pursuit and evasion games (49N75) Linear programming (90C05) Positional games (pursuit and evasion, etc.) (91A24)

Abstract: 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 determining the fractional eternal domination number of a graph $G$, which we denote $gamm{a}_{,extitf}^{infty}(G)$. We study the behaviour of $gamm{a}_{,extitf}^{infty}(G)$ as it relates to other domination parameters. We also determine bounds on, and in some cases exact values for, $gamm{a}_{,extitf}^{infty}(G)$ when $G$ is a member of one of a variety of important graph classes, including trees, split graphs, strongly chordal graphs, Kneser graphs, abelian Cayley graphs, and graph products.

This page was built for publication: Fractional eternal domination: securely distributing resources across a network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6434055)