On graphs with equal total domination and Grundy total domination numbers
A sequence \((v_1,v_2,\dots,v_k)\) of vertices in a graph \(G\) without isolated vertices is called a total dominating sequence if every vertex \(v_i\) in the sequence totally dominates at least one vertex that was not totally dominated by \(\{v_1,\dots, v_{i-1}\}\) and \(\{v_1,\dots,v_k\}\) is a total dominating set of \(G\). The length of a shortest such sequence is the total domination number of \(G\) (\(\gamma_t(G)\)), while the length of a longest such sequence is the Grundy total domination number of \(G\) (\(\gamma^t_{gr}(G)\)). In this paper, the authors first characterize bipartite graphs with both total and Grundy total dominations number equal to 4 and then show that there is no connected chordal graph \(G\) with \(\gamma_t(G)=\gamma^t_{gr}(G) = 4\). Finally, they characterize bipartite graphs with \(\gamma_t(G) =\gamma^t_{gr}(G) = 6\). To state the main results of the paper, we recall some definitions. Two distinct vertices \(u\) and \(v\) of a graph \(G\) are said to be false twins if \(N(u) = N(v)\). A graph is false twin-free (also known as thin) if it has no false twins. For a bipartite graph \(G\) with bipartition sets \(A\) and \(B\), the bipartite complement of \(G\) is the bipartite graph \(G^{bc}\) with the same bipartition sets, where \(a \in A\) is adjacent to \(b\in B\) in \(G^{bc}\) if and only if \(a\) is not adjacent to \(b\) in \(G\). The main results of this paper are: \par 1.) Let \(G\) be a bipartite false twin-free graph. Then \(\gamma_t(G) =\gamma^t_{gr}(G) = 4\) if and only if \(G\) is isomorphic to the graph \(K_{n,n}-M\), \(n \ge 2\), where \(M\) denotes an arbitrary perfect matching of \(K_{n,n}\). \par 2.) There is no connected chordal graph \(G\) with \(\gamma_t(G) = \gamma^t_{gr}(G) = 4\). \par 3.) Let \(G\) be a connected bipartite false twin-free graph. Then \(\gamma_t(G) = \gamma^t_{gr}(G) = 6\) if and only if the bipartite complement of \(G\) is the incidence graph of a projective plane. The authors posed the following interesting conjecture. Conjecture. Let \(G\) be a connected false twin-free graph. Then \(\gamma_t(G) =\gamma^t_{gr}(G) = 4\) if and only if \(G\) is isomorphic to the graph \(K_{n,n}-M\), \(n\geq 3\), where \(M\) denotes an arbitrary perfect matching of \(K_{n,n}\).
- Characterisation of forests with trivial game domination numbers
- Combinatorial Designs
- On Grundy total domination number in product graphs
- On rigid circuit graphs
- Total dominating sequences in graphs
- Total dominating sequences in trees, split graphs, and under modular decomposition
- Total domination in graphs
- Total domination in graphs
- Total version of the domination game
- Trees with equal total domination and game total domination numbers
- On graphs with equal domination and connected domination numbers
- On graphs with equal domination and covering numbers
- Total dominating sequences in trees, split graphs, and under modular decomposition
- On graphs all of whose total dominating sequences have the same length
- Equality in a linear Vizing-like relation that relates the size and total domination number of a graph
- Total dominating sequences in graphs
- Grundy domination sequences in generalized corona products of graphs
- Graphs with equal Grundy domination and independence number
- Paired-domination game played on paths
- A class of threshold and domishold graphs: Equistable and equidominating graphs
This page was built for publication: On graphs with equal total domination and Grundy total domination numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118158)
