On pebbling threshold functions for graph sequences (Q1598791)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On pebbling threshold functions for graph sequences |
scientific article |
Statements
On pebbling threshold functions for graph sequences (English)
0 references
28 May 2002
0 references
A threshold function for a sequence of graphs \({\mathcal G}= (G_1,G_2,\dots, G_n,\dots)\), where \(G_n\) has \(n\) vertices, is any function \(t_0(n)\) such that almost all distributions of \(t\) pebbles are solvable when \(t/t_0\to 0\) for \(n\to\infty\), and such that almost none are solvable when \(t_0/t\to 0\) for \(n\to\infty\). The authors give bounds on pebbling threshold functions for sequences of several types of graphs.
0 references
peppling number
0 references
threshold function
0 references