Definition

Graphs whose pebbling number is equal to their number of vertices are said to be of Class 0.

Small Diameter

Because of the lower bound of $n(G)$ on the pebbling number $\pi(G)$, it is natural to try to classify Class 0 graphs, or at least give conditions which either guarantee or prohibit Class 0. This is of course extremely difficult, although some preliminary results have proved quite interesting. As argued in Cut Lower Bound, graphs of connectivity $1$ are not Class 0. In [PSV] we find the following theorem.

Diameter 2 Theorem.  If ${\rm diam}(G) = 2$ then $\pi(G) = n(G)$ or $n(G)+1.$

Class 0 graphs of diameter $2$ are classified in [CHH]. A particularly crucial graph in the characterization is the graph $G$, built from the bipartite graph $C_6$ by connecting all the vertices of one of the parts of the bipartition to each other. $G$ has connectivity $2$ and diameter $2$ but $\pi(G) > 6 = n(G)$, as witnessed by the configuration $C(a,b)=(3,3)$, where $a,b$, and the root $r$ are independent.

An upper bound for diameter $3$ graphs was recently obtained in [Buk].

Diameter 3 Theorem.  If ${\rm diam}(G) = 3$ then $\pi(G) \leq 3n/2$, which is best possible.

Connectivity

The connectivity of a graph equals the minimum number of vertices whose removal disconnects it. Denote the connectivity of a graph $G$ by $\kappa(G)$. The following corollary appears in [CHH].

D2C3 Theorem.  If $diam(G) = 2$, and $\kappa(G) \geq 3$ then $G$ is of Class 0.

From this it follows that almost all graphs (in the probabilistic sense) are of Class 0, since almost every graph is $3$-connected with diameter $2$. The following result, conjectured in [CHH], was proved in [CHKT]. This result was used to prove a number of other theorems, including the Min. Degree Product Theorem, the Girth Theorem, and [Theorem not yet on the site].

Diameter-Connectivity Theorem.  There is a smallest function $k(d)$ such that if $G$ is a graph with $diam(G) = d$ and $\kappa(G) \geq k(d)$ then $G$ is of Class 0. Moreover, $2^d/d \leq k(d) \leq 2^{2d+3}.$

Kneser Graphs

A nice family of graphs in relation to the Diameter-Connectivity Theorem is the following. For $m \geq 2t+1$, the Kneser graph, $K(m,t)$, is the graph with vertices $[m] \choose t$ and edges $\{A,B\}$ whenever $A$ and $B$ are disjoint.

The case $t=1$ yields the complete graph $K_m$ and the case $m=5$ and $t=2$ yields the Petersen graph $P$, both of which are Class 0. When $t \geq 2$ and $m \geq 3t-1$ we have ${\rm diam}(K(m,t))=2$. Also, $\kappa(K(m,t)) \geq 3$ in this range, implying that $K(m,t)$ is Class 0 by the D2C3 Theorem.

Furthermore, combining results of Chen and Lih [ChLi] ($K(m,t)$ is connected, edge transitive, and regular) and Lovasz [Lov] (such a graph has connectivity equal to its degree) with the Diameter-Connectivity Theorem, Hurlbert [Hurl2] proved the following.

Kneser Graph Theorem. For any constant $c > 0$, there is an integer $t_0$ such that, for $t > t_0,$ $s \geq c(t/\log_2t)^{1/2}$ and $m = 2t+s,$ we have $K(m,t)$ is Class 0.

Girth

The girth of a graph is the length of its shortest cycle. Regarding conditions which prohibit Class 0 membership, one can easily show that if ${\rm girth}(G) > 2\log n$ then $\pi(G) > n(G)$. The following question was asked in [Hurl2]: Is there a constant $g$ so that ${\rm girth}(g) > g$ implies $\pi(G) > n(G)$? This question was answered in the negative in [CzHu3] by using the Diameter-Connectivity Theorem, along with a probabilistic (deletion) method analogous to Erdos's construction [Erd2] of graphs of arbitrarily high girth and chromatic number.

Let $g_0(n)$ denote the maximum number $g$ such that there exists a Class 0 graph $G$ on at most $n$ vertices with finite ${\rm girth}(G) \geq G$. Then for all $n \geq 3$ we have the following theorem.

Girth Theorem.  $\lfloor\sqrt{\log n/2+1/4}-1/2\rfloor \leq g_0(n) \leq 1+2\log(n)$.

Bipartite Graphs

Denote by $B(m,k)$ the family of all connected, bipartite graphs on $n=2m$ vertices with minimum degree at least $k$. The only graph in $B(m,2)$ is $C_{2m}$, having pebbling number $2^m$. The only graph in $B(m,m)$ is $K_{m,m}$ having pebbling number $n=2m$. [Cla]. Also shown in [Cla] is that every graph in $B(m,m-1)$ is of Class 0. In [Hur1] we find that if $k \geq 2m/3$ (and $m \geq 6$) then every $G \in B(m,k)$ is of Class 0. Define $b(m)$ to be the smallest $k$ such that every graph in $B(m,k)$ is of Class 0. Czygrinow and Hurlbert. [CzHu2] proved the following.

Class 0 - Bipartite - Min Degree Theorem.  For all $m \geq 7$ we have $b(m) \geq \lfloor m/2 \rfloor + 1.$ For all $m \geq 336$ we have $b(m) = \lfloor m/2 \rfloor + 1.$

One can consider the same question for all graphs instead of bipartite graphs. In [CzHu2] is proved an analogous result. Let $g(n)$ be the minimum $k$ such that every graph in $G(n,k)$ is Class 0.

Class 0 - Min Degree Theorem.  For all $n \geq 6$ we have $g(n) \leq \lfloor n/2 \rfloor.$ For all $n \geq 9$ we have $g(n) = \lfloor n/2 \rfloor.$

References

B.L. Chen and K.W. Lih Hamiltonian uniform subset graphs J. Combin. Theory Ser. B 42 (1987), 257--263

P. Erdos Applications of probabilistic methods to graph theory A Seminar on Graph Theory, Holt, Rinehart and Winston, New York (1967) 60--61

L. Lovasz Combinatorial Problems and Exercises North Holland Pub., Amsterdam, New York, Oxford (1979)