Dominating sequences in grid-like and toroidal graphs

zbMATH Open1353.05105arXiv1607.00248MaRDI QIDQ504964FDOQ504964

Authors: Boštjan Brešar, Csilla Bujtás, T. Gologranc, Sandi Klavžar, Gašper Košmrlj, Balázs Patkós, Zsolt Tuza, Máté Vizer 

Publication date: 18 January 2017

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

Abstract: A longest sequence $S$ of distinct vertices of a graph $G$ such that each vertex of $S$ dominates some vertex that is not dominated by its preceding vertices, is called a Grundy dominating sequence; the length of $S$ is the Grundy domination number of $G$. In this paper we study the Grundy domination number in the four standard graph products: the Cartesian, the lexicographic, the direct, and the strong product. For each of the products we present a lower bound for the Grundy domination number which turns out to be exact for the lexicographic product and is conjectured to be exact for the strong product. In most of the cases exact Grundy domination numbers are determined for products of paths and/or cycles.

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

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
• Grundy domination sequences in generalized corona products of graphs
• Grundy domination of forests and the strong product conjecture
• Dominating sequences in graphs
• scientific article; zbMATH DE number 2188349

zbMATH Keywords

isoperimetric inequalitygraph productedge clique coverGrundy domination

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

• Topics in Intersection Graph Theory
• Title not available (Why is that?)
• Total dominating sequences in graphs
• Handbook of product graphs
• Dominating sequences in graphs
• An Ordering on the Even Discrete Torus
• Compressions and isoperimetric inequalities
• Title not available (Why is that?)
• Associative graph products and their independence, domination and coloring numbers
• Dominating Cartesian products of cycles
• The domination number of grids
• Vizing's conjecture: a survey and recent results
• Perfect codes in direct products of cycles-a complete characterization
• The Representation of a Graph by Set Intersections
• An almost complete description of perfect codes in direct products of cycles
• Perfect \(r\)-codes in lexicographic products of graphs.
• Title not available (Why is that?)
• Dominating sequences under atomic changes with applications in Sierpiński and interval graphs
• A note on the domination number of the Cartesian products of paths and cycles

Cited In (17)

• Grundy domination and zero forcing in Kneser graphs
• Grundy domination of forests and the strong product conjecture
• Dominating sequences in graphs
• Grundy domination and zero forcing in regular graphs
• On the L-Grundy domination number of a graph
• On the Grundy bondage numbers of graphs
• Bounds on zero forcing using (upper) total domination and minimum degree
• On Grundy total domination number in product graphs
• Stack domination density
• On graphs all of whose total dominating sequences have the same length
• Graphs with equal Grundy domination and independence number
• Grundy dominating sequences on \(X\)-join product
• Dominating sequences under atomic changes with applications in Sierpiński and interval graphs
• Zero forcing number, Grundy domination number, and their variants
• Grundy dominating sequences and zero forcing sets
• Grundy domination sequences in generalized corona products of graphs
• Vertex sequences in graphs

This page was built for publication: Dominating sequences in grid-like and toroidal graphs

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