Article in press
Authors:
Title:
Fractional eternal domination: securely distributing resources across a network
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-06-15 , Revised: 2023-05-31 , Accepted: 2023-06-03 , Available online: 2023-07-12 , https://doi.org/10.7151/dmgt.2503
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 $\gamma^{\infty}_{f}(G)$. We study the behaviour of $\gamma^{\infty}_{f}(G)$ as
it relates to other domination parameters. We also determine bounds on, and in
some cases exact values for, $\gamma^{\infty}_{f}(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.
Keywords:
eternal domination, fractional domination
References:
- J. Azarija, M. Henning and S. Klavžar, $( $Total$)$ domination in prisms, Electron. J. Combin. 24(1) (2017) #P1.19.
https://doi.org/10.37236/6288 - S. Bard, C. Duffy, M. Edwards, G. MacGillivray and F. Yang, Eternal domination in split graphs, J. Combin. Math. Combin. Comput. 101 (2017) 121–130.
- A.P. Burger, E.J. Cockayne, W.R. Gründlingh, C.M. Mynhardt, J.H. van Vuuren and W. Winterbach, Infinite order domination in graphs, J. Combin. Math. Combin. Comput. 50 (2004) 179–194.
- G.S. Domke, S.T. Hedetniemi and R.C. Laskar, Fractional packings, coverings and irredundance in graphs, Congr. Numer. 66 (1988) 227–238.
- M. Farber, Domination, independent domination, and duality in strongly chordal graphs, Discrete Appl. Math. 7 (1984) 115–130.
https://doi.org/10.1016/0166-218X(84)90061-1 - W. Goddard, S.M. Hedetniemi and S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput 52 (2005) 169–180.
- D.L. Grinstead and P.J. Slater, Fractional domination and fractional packing in graphs, Congr. Numer. 71 (1990) 153–172.
- T.W. Haynes, S.T. Hedetniemi and P. Slater, Domination in Graphs: Advanced Topics (Routledge, New York, 1998).
https://doi.org/10.1201/9781315141428 - T.W. Haynes, S.T. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (CRC Press, Boca Raton, 1998).
https://doi.org/10.1201/9781482246582 - R. Hill, A First Course in Coding Theory (Oxford University Press, 1986).
- W.F. Klostermeyer and G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. 68 (2009) 97–111.
- W.F. Klostermeyer and C.M. Mynhardt, Protecting a graph with mobile guards, Appl. Anal. Discrete Math. 10 (2016) 1–29.
https://doi.org/10.2298/AADM151109021K - W.C. Shiu, On $3$-regular and $4$-regular Cayley graphs of abelian groups, Tech. Rep. (Hong Kong Baptist University, Dept. of Mathematics, 1995).
Close