Dominating sequences in grid-like and toroidal graphs

MaRDI QIDQ504964zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1607.00248, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i4p34

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

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)

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.

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

Cites work

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

Cited in

(17)

• Grundy domination of forests and the strong product conjecture
• Grundy domination and zero forcing in Kneser graphs
• 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)