2020/10/01 by Brešar, Boštjan, Brezovnik, Simon
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2010.00637
Given a finite graph G, the maximum length of a sequence (v1,…,vk) of vertices in G such that each vi dominates a vertex that is not dominated by any vertex in \v1,…,vi-1\ is called the Grundy domination number, γ\rm gr(G), of G. A small modification of the definition yields the Z-Grundy domination number, which is the dual invariant of the well-known zero forcing number. In this paper, we prove that γ\rm gr(G) ≥ (n + \lceil (k)/(2) \rceil - 2)/(k-1) holds for every connected k-regular graph of order n different from Kk+1 and 2C4. The bound in the case k=3 reduces to γ\rm gr(G) ≥ (n)/(2), and we characterize the connected cubic graphs with γ\rm gr(G)=(n)/(2). If G is different from K4 and K3,3, then (n)/(2) is also an upper bound for the zero forcing number of a connected cubic graph, and we characterize the connected cubic graphs attaining this bound.