Stack domination density (Q2637721): Difference between revisions

Consider the domination number \(\gamma(P_n \times G)\) of a path \(P_n\) in a finite graph \(G\). The authors show that the stack domination density \(\overline{\gamma}(G)\) defined by \(\lim_{n \to \infty} \gamma(P_n \times G)/n\) exists and is equal to \(\min_{m \leq 3^{|G|}}\gamma(C_m \times G)/m\), where \(C_m\) denotes a cycle of length \(m\). It is shown that \(\gamma(C_n \times G^*) \geq 2n\) for the Grötzsch graph \(G^*\). ``For several other sequences \(\{G_n\}\), the limit of the stack domination density are proved to exist; in other cases the ratio \(\gamma(G_n \times H)/\gamma(G_n)\) proves to be of greater interest, and also exists for several families of graphs.''