
arXiv: 2304.11795
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 $γ_{\,\textit{f}}^{\infty}(G)$. We study the behaviour of $γ_{\,\textit{f}}^{\infty}(G)$ as it relates to other domination parameters. We also determine bounds on, and in some cases exact values for, $γ_{\,\textit{f}}^{\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.
32 pages, including appendix
FOS: Computer and information sciences, fractional domination, Discrete Mathematics (cs.DM), Games on graphs (graph-theoretic aspects), Fractional graph theory, fuzzy graph theory, Graphs and abstract algebra (groups, rings, fields, etc.), eternal domination, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), 05C57, 05C69, 05C72, 05C21, 90C05, 91A24, 49N75, Linear programming, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Games involving graphs, Flows in graphs, Mathematics, Positional games (pursuit and evasion, etc.), Computer Science - Discrete Mathematics
FOS: Computer and information sciences, fractional domination, Discrete Mathematics (cs.DM), Games on graphs (graph-theoretic aspects), Fractional graph theory, fuzzy graph theory, Graphs and abstract algebra (groups, rings, fields, etc.), eternal domination, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), 05C57, 05C69, 05C72, 05C21, 90C05, 91A24, 49N75, Linear programming, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Games involving graphs, Flows in graphs, Mathematics, Positional games (pursuit and evasion, etc.), Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
