A note on domination and total domination in prisms (Q1698053): Difference between revisions

Let \(G=(V,E)\) be a simple graph. A subset \(S \subseteq V\) is a dominating set if every vertex \(v \in V\setminus S\) is adjacent to a vertex in S. The minimum cardinality of a dominating set, denoted by \(\gamma(G)\), called the domination number of graph \(G\). A subset \(D \subseteq V\) is a total dominating set if every vertex \(u \in V\) is adjacent to a vertex in \(D\). The minimum cardinality of a total dominating set, denoted by \(\gamma_t(G)\), called the total domination number of graph \(G\). For a graph \(G\), the prism of \(G\) is defined by taking two disjoint copies of \(G1\) and \(G2\) of \(G\), and adding an edge between each pair of corresponding vertices. \textit{J. Azarija} et al. [Electron. J. Comb. 24, No. 1, Research Paper P1.19, 11 p. (2017; Zbl 1355.05181)] considered the prism \(G\Box K_2\) of a bipartite graph \(G\) and posed a problem of bounding the total domination number of \(G\Box K_2\) in terms of domination number of graph \(G\). In the paper under review, the authors prove \(\gamma_t(G \Box K_2) \geq \frac{4}{3}\gamma(G)\) for any graph \(G\) and show that this bound is tight.