Stack domination density (Q2637721)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Stack domination density |
scientific article |
Statements
Stack domination density (English)
0 references
14 February 2014
0 references
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.''
0 references
domination number
0 references
asymptotic density
0 references
additive graph
0 references