Grundy domination of forests and the strong product conjecture

DOI10.37236/9507zbMATH Open1466.05156arXiv2104.05665OpenAlexW4231320854WikidataQ113693634 ScholiaQ113693634MaRDI QIDQ831340FDOQ831340

Authors: Kayla Bell, Keith Driscoll, Elliot Krop, Kimber Wolff 

Publication date: 11 May 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: A maximum sequence $S$ of vertices in a graph $G$, so that every vertex in $S$ has a neighbor which is independent, or is itself independent, from all previous vertices in $S$, is called a Grundy dominating sequence. The Grundy domination number, $gamm{a}_{gr}(G)$, is the length of $S$. We show that for any forest $F$, $gamm{a}_{gr}(F)=|V(T)|-|mathcalP|$ where $mathcalP$ is a minimum partition of the non-isolate vertices of $F$ into caterpillars in which if two caterpillars of $mathcalP$ have an edge between them in $F$, then such an edge must be incident to a non-leaf vertex in at least one of the caterpillars. We use this result to show the strong product conjecture of B. Brev{s}ar, Cs. Bujt'{a}s, T. Gologranc, S. Klavv{z}ar, G. Kov{s}mrlj, B. Patk'{o}s, Zs. Tuza, and M. Vizer, Dominating sequences in grid-like and toroidal graphs, Electron. J. Combin. 23(4): P4.34 (2016), for all forests. Namely, we show that for any forest $G$ and graph $H$, $$. We also show that every connected graph $G$ has a spanning tree $T$ so that $gamm{a}_{gr}(G)legamm{a}_{gr}(T)$ and that every non-complete connected graph contains a Grundy dominating set $S$ so that the induced subgraph of $S$ contains no isolated vertices.

Full work available at URL: https://arxiv.org/abs/2104.05665

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On Grundy total domination number in product graphs
• Dominating sequences in grid-like and toroidal graphs
• On the domination of the products of graphs II: Trees
• scientific article; zbMATH DE number 975402
• A note on the Grundy number and graph products

zbMATH Keywords

foreststrong product of graphsGrundy domination numberGrundy dominating sequence

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Total dominating sequences in graphs
• Dominating sequences in graphs
• Title not available (Why is that?)
• Vizing's conjecture: a survey and recent results
• Dominating sequences in grid-like and toroidal graphs
• Dominating sequences under atomic changes with applications in Sierpiński and interval graphs
• Grundy dominating sequences and zero forcing sets
• On Grundy total domination number in product graphs

Cited In (7)

• Computation of Grundy dominating sequences in (co-)bipartite graphs
• Title not available (Why is that?)
• Graphs with equal Grundy domination and independence number
• The pseudoforest analogue for the strong nine dragon tree conjecture is true
• On the length of L-Grundy sequences
• Strong Chang's conjecture and the tree property at \(\omega_{2}\)
• Dominating sequences in grid-like and toroidal graphs

This page was built for publication: Grundy domination of forests and the strong product conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831340)