Total dominating sequences in graphs

DOI10.1016/J.DISC.2016.01.017zbMATH Open1333.05214arXiv1601.07525OpenAlexW2283061813MaRDI QIDQ267175FDOQ267175

Authors: Boštjan Brešar, Michael A. Henning, Douglas F. Rall 

Publication date: 8 April 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A vertex in a graph totally dominates another vertex if they are adjacent. A sequence of vertices in a graph $G$ is called a total dominating sequence if every vertex $v$ in the sequence totally dominates at least one vertex that was not totally dominated by any vertex that precedes $v$ in the sequence, and at the end all vertices of $G$ are totally dominated. While the length of a shortest such sequence is the total domination number of $G$, in this paper we investigate total dominating sequences of maximum length, which we call the Grundy total domination number, $gamm{a}_{mgr}^t(G)$, of $G$. We provide a characterization of the graphs $G$ for which $gamm{a}_{mgr}^t(G)=|V(G)|$ and of those for which $gamm{a}_{mgr}^t(G)=2$. We show that if $T$ is a nontrivial tree of order~$n$ with no vertex with two or more leaf-neighbors, then $gamm{a}_{mgr}^t(T)gefrac23(n+1)$, and characterize the extremal trees. We also prove that for $kge3$, if $G$ is a connected $k$-regular graph of order~$n$ different from $K_{k,k}$, then $gamm{a}_{mgr}^t(G)ge(n+lceilfrack2ceil-2)/(k-1)$ if $G$ is not bipartite and $gamm{a}_{mgr}^t(G)ge(n+2lceilfrack2ceil-4)/(k-1)$ if $G$ is bipartite. The Grundy total domination number is proven to be bounded from above by two times the Grundy domination number, while the former invariant can be arbitrarily smaller than the latter. Finally, a natural connection with edge covering sequences in hypergraphs is established, which in particular yields the NP-completeness of the decision version of the Grundy total domination number.

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

Recommendations

• Total dominating sequences in trees, split graphs, and under modular decomposition
• Dominating sequences in graphs
• On graphs with equal total domination and Grundy total domination numbers
• On graphs all of whose total dominating sequences have the same length
• Grundy domination sequences in generalized corona products of graphs

zbMATH Keywords

edge coverGrundy total domination numbertotal domination

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12)

Cites Work

• Some perfect coloring properties of graphs
• Covering all cliques of a graph
• Small transversals in hypergraphs
• Domination game and an imagination strategy
• Total domination in graphs
• Title not available (Why is that?)
• Some remarks on domination
• Semistrong edge coloring of graphs
• The domination game played on unions of graphs
• Induced matchings in subcubic planar graphs
• Total domination in graphs
• Edge weighting functions on dominating sets
• Total version of the domination game
• Induced matchings in subcubic graphs
• Extremal problems for game domination number
• Dominating sequences in graphs
• Total domination of graphs and small transversals of hypergraphs

Cited In (27)

• Grundy domination and zero forcing in Kneser graphs
• Grundy domination of forests and the strong product conjecture
• On graphs with equal total domination and Grundy total domination numbers
• Degree sequences of graphs and dominance order
• Dominating sequences in graphs
• Grundy domination and zero forcing in regular graphs
• Facets of the polytope of legal sequences
• On the L-Grundy domination number of a graph
• On the Grundy bondage numbers of graphs
• A new approach on locally checkable problems
• Computation of Grundy dominating sequences in (co-)bipartite graphs
• Total domination versus domination in cubic graphs
• Bounds on zero forcing using (upper) total domination and minimum degree
• On Grundy total domination number in product graphs
• On upper total domination versus upper domination in graphs
• An integer programming approach for solving a generalized version of the Grundy domination number
• On graphs all of whose total dominating sequences have the same length
• Total dominating sequences in trees, split graphs, and under modular decomposition
• Graphs with equal Grundy domination and independence number
• Uniform length dominating sequence graphs
• On the length of L-Grundy sequences
• Dominating sequences in grid-like and toroidal 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
• The variety of domination games

This page was built for publication: Total dominating sequences in graphs

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