Grundy domination and zero forcing in Kneser graphs

Boštjan Brešar, Tim Kos, Pablo Daniel Torres

Abstract


In this paper, we continue the investigation of different types of (Grundy) dominating sequences. We consider four different types of Grundy domination numbers and the related zero forcing numbers, focusing on these numbers in the well-known class of Kneser graphs Kn, r. In particular, we establish that the Grundy total domination number γgrt(Kn, r) equals (2r choose r) for any r ≥ 2 and n ≥ 2r + 1. For the Grundy domination number of Kneser graphs we get γgr(Kn, r) = α(Kn, r) whenever n is sufficiently larger than r. On the other hand, the zero forcing number Z(Kn, r) is proved to be (n choose r) − (2r choose r) when n ≥ 3r + 1 and r ≥ 2, while lower and upper bounds are provided for Z(Kn, r) when 2r + 1 ≤ n ≤ 3r. Some lower bounds for different types of minimum ranks of Kneser graphs are also obtained along the way.


Keywords


Grundy domination number, Grundy total domination number, Kneser graph, zero forcing number, minimum rank

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.1881.384

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications