On graphs with equal total domination and Grundy total domination numbers (Q2118158)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On graphs with equal total domination and Grundy total domination numbers |
scientific article |
Statements
On graphs with equal total domination and Grundy total domination numbers (English)
0 references
22 March 2022
0 references
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}\).
0 references
total domination number
0 references
Grundy total domination number
0 references
bipartite graphs
0 references
orthogonal array
0 references
finite projective planes
0 references