Bounding the Eviction Number of a Graph in Terms of its Independence Number

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Authors

Department of Mathematics and Statistics, University of Victoria, Victoria, Canada

Abstract

An eternal dominating family of a graph $G$ in the eviction game is a collection $\mathcal{D}_{k}=\{D_{1},D_{2},\dots,D_{l}\}$ of dominating sets of $G$ such that (a) $|D_{i}|=|D_{j}|$ for all $i,j\in\{1,2,\dots,l\}$, and (b) for any $i\in \{1,2,\dots,l\}$ and any $v\in D_{i}$, either all neighbours of $v$ belong to $D_{i}$, or there are a neighbour $w$ of $v$ not in $D_{i}$ and an integer $j\in\{1,2,\dots,l\}\setminus\{i\}$ such that $D_{i}\cup\{w\}\setminus \{v\}=D_{j}$. The eviction number of $G$, denoted by $e^{\infty}(G)$, is the smallest cardinality of the sets in such an eternal dominating family.
We compare $e^{\infty}$ to the independence number $\alpha$. We show that the ratio $\alpha/e^{\infty}$ is unbounded and construct an infinite class of connected graphs for which $e^{\infty}/\alpha \approx 4/3$. As our main result, we use Ramsey numbers to show that for any integer $k\geq1$, there exists a function $f(k)$ such that any graph with independence number$k$ has eviction number at most $f(k)$.

Keywords

Main Subjects

References

[1] A.P. Burger, E.J. Cockayne, W.R. Gründlingh, C.M. Mynhardt, J.H. Van Vuuren, and W. Winterbach, Finite order domination in graphs, J. Combin. Math. Combin. Comput. 49 (2004), 159–175.
[2] 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.
[3] G. Chartrand, L. Lesniak, and P. Zhang, Graphs and Digraphs, 6th ed., Chapman and Hall/CRC, Boca Raton, 2016.
[4] D.G. Corneil, H. Lerchs, and L.S. Burlingham, Complement reducible graphs, Discrete Appl. Math. 3 (1981), no. 3, 163–174. https://doi.org/10.1016/0166-218X(81)90013-5
[5] D.G. Corneil, Y. Perl, and L.K. Stewart, A linear recognition algorithm for cographs, SIAM J. Comput. 14 (1985), no. 4, 926–934. https://doi.org/10.1137/0214065
[6] W.F. Klostermeyer, M. Lawrence, and G. MacGillivray, Dynamic dominating sets: the eviction model for eternal domination, J. Combin. Math. Combin. Comput. 97 (2016), 247–269.
[7] W.F. Klostermeyer and G. MacGillivray, Eternal security in graphs of fixed independence number, J. Combin. Math. Combin. Comput. 63 (2007), 97–101.
[8] W.F. Klostermeyer and C. M. Mynhardt, Protecting a graph with mobile guards, Appl. Anal. Discrete Math. 10 (2016), no. 1, 1–29.
[9] W.F. Klostermeyer and C.M. Mynhardt, Eternal and secure domination in graphs, Topics in domination in graphs, Dev. Math., vol. 64, Springer, Cham, 2020, pp. 445–478.
[10] F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1929), no. 1, 264–286. https://doi.org/10.1112/plms/s2-30.1.264
[11] V. Virgile, Mobile guards’ strategies for graph surveillance and protection, Ph.D. thesis, University of Victoria, 2024.
[12] D.B. West, Introduction to Graph Theory, Prentice-Hall, Upper Saddle River, NJ, 1996.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 18 May 2026

Files

Share

How to cite

Statistics