Grundy domination of forests and the strong product conjecture

DOI10.37236/9507MaRDI QIDQ831340zbMATH OpenOpenAlexWikidataFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3284071 (Why is no real title available?)
• Dominating sequences in graphs
• 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
• Total dominating sequences in graphs
• Vizing's conjecture: a survey and recent results

Cited in

(8)

• Graphs with equal Grundy domination and independence number
• Grundy dominating sequences on \(X\)-join product
• On the length of L-Grundy sequences
• Computation of Grundy dominating sequences in (co-)bipartite graphs
• The pseudoforest analogue for the strong nine dragon tree conjecture is true
• Strong Chang's conjecture and the tree property at \(\omega_{2}\)
• Dominating sequences in grid-like and toroidal graphs
• scientific article; zbMATH DE number 1122855 (Why is no real title available?)

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)