WorksMathematics
Unbounded strong-product ratios for the Grundy domination number
Abstract · v2
A sequence of vertices of a graph is legal when every vertex in it dominates some vertex that none of the earlier ones dominated, and the Grundy domination number of the graph is the length of its longest legal sequence. In the strong product of two graphs, two vertices are adjacent when each coordinate is equal or adjacent in its factor. It has been known since 2016 that the Grundy domination number of a strong product is at least the product of the Grundy domination numbers of the two factors, and it was conjectured, by Brešar, Bujtás, Gologranc, Klavžar, Košmrlj, Patkós, Tuza and Vizer, that equality always holds. We show that the conjecture is false, and false by an unbounded factor: for every number there are graphs whose strong product has Grundy domination number more than times the product of the two factors. The graphs are built on the five-element subsets of an -element set, with adjacency decided by the size of the intersection; incidence matrices over the fields with two and three elements bound the two factors by and , while the diagonal of the product is an independent set of size . We also compute the Grundy domination number of the graph on in which and are adjacent when : it is for every . Its strong product with the octahedron has a legal sequence of length , so the conjecture already fails for , on a graph with vertices, and for every . Every statement is proved by hand.
Review conversation
Reviews are not available for this work yet.