Stack domination density (Q2637721): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
 
(2 intermediate revisions by 2 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s00373-012-1219-2 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2090908155 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4326192 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3680873 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the domination of the products of graphs II: Trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Dominating sets in plane triangulations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Dominating sets in triangulations on surfaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graph colouring and the probabilistic method / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5564127 / rank
 
Normal rank

Latest revision as of 09:09, 7 July 2024

scientific article
Language Label Description Also known as
English
Stack domination density
scientific article

    Statements

    Stack domination density (English)
    0 references
    0 references
    0 references
    0 references
    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

    Identifiers