Geodesic
Fractional eternal domination: securely distributing resources across a network
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1395-1428 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 γ_f^∞(G). We study the behaviour of γ_f^∞(G) as it relates to other domination parameters. We also determine bounds on, and in some cases exact values for, γ_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 
@article{DMGT_2024_44_4_a9,
     author = {Devvrit, Fnu and Krim-Yee, Aaron and Kumar, Nithish and MacGillivray, Gary and Seamone, Ben and Virgile, Virg\'elot and Xu, AnQi},
     title = {Fractional eternal domination: securely distributing resources across a network},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1395--1428},
     year = {2024},
     volume = {44},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a9/}
}
TY  - JOUR
AU  - Devvrit, Fnu
AU  - Krim-Yee, Aaron
AU  - Kumar, Nithish
AU  - MacGillivray, Gary
AU  - Seamone, Ben
AU  - Virgile, Virgélot
AU  - Xu, AnQi
TI  - Fractional eternal domination: securely distributing resources across a network
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1395
EP  - 1428
VL  - 44
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a9/
LA  - en
ID  - DMGT_2024_44_4_a9
ER  - 
%0 Journal Article
%A Devvrit, Fnu
%A Krim-Yee, Aaron
%A Kumar, Nithish
%A MacGillivray, Gary
%A Seamone, Ben
%A Virgile, Virgélot
%A Xu, AnQi
%T Fractional eternal domination: securely distributing resources across a network
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1395-1428
%V 44
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a9/
%G en
%F DMGT_2024_44_4_a9
Devvrit, Fnu; Krim-Yee, Aaron; Kumar, Nithish; MacGillivray, Gary; Seamone, Ben; Virgile, Virgélot; Xu, AnQi. Fractional eternal domination: securely distributing resources across a network. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1395-1428. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a9/

[1] 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

[2] 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.

[3] 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.

[4] G.S. Domke, S.T. Hedetniemi and R.C. Laskar, Fractional packings, coverings and irredundance in graphs, Congr. Numer. 66 (1988) 227–238.

[5] 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

[6] W. Goddard, S.M. Hedetniemi and S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput 52 (2005) 169–180.

[7] D.L. Grinstead and P.J. Slater, Fractional domination and fractional packing in graphs, Congr. Numer. 71 (1990) 153–172.

[8] T.W. Haynes, S.T. Hedetniemi and P. Slater, Domination in Graphs: Advanced Topics (Routledge, New York, 1998). https://doi.org/10.1201/9781315141428

[9] 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

[10] R. Hill, A First Course in Coding Theory (Oxford University Press, 1986).

[11] W.F. Klostermeyer and G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. 68 (2009) 97–111.

[12] 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

[13] W.C. Shiu, \textrm{On 3-regular and 4-regular Cayley graphs of abelian groups}, Tech. Rep. (Hong Kong Baptist University, Dept. of Mathematics, 1995).