Warning: jsMath requires JavaScript to process the mathematics on this page.
If your browser supports JavaScript, be sure it is enabled.

Pebbling Glossary Page

the property that a graph cannot be disconnected by removing only one vertex
2-Pebbling Property
two pebbles can be moved to any specified vertex when the initial configuration $C$ has size $2\pi(G)-s(C)+1$, where $s(C)$ is the size of the support
Bipartite Graph
a graph whose vertices can be covered by two sets of pairwise nonadjacent vertices
the graph $S_{p+1} \times P_q$, having $p$ pages, $q$ vertices per page, and $q$ vertices on the binding.
Cartesian Product
G1 x G2 has vertex set $V(G_1 \times G_2) = \{(v_1,v_2) | v_1 \in V(G_1), v_2 \in V(G_2) \}$ and edge set $E(G_1 \times G_2) = \{\{(v_1,v_2),(w_1,w_2)\} | (v_1=w_1$ $and$ $(v_2,w_2) \in E(G_2))$ $or$ $(v_2=w_2$ $and$ $(v_1,w_1) \in E(G_1))\}$
Class 0
the property that a graph has pebbling number equal to its number of vertices
the property that a graph has every vertex adjacent to all other vertices
Complete Bipartite Graph
a bipartite graph in which every pair of vertices not belonging to the same partite set is adjacent
a function that indicates the number of pebbles per vertex
the minimum number of vertices whose deletion disconnects the graph or reduces it to one vertex
Cover Pebbling Number
the minimum number of pebbles needed so that from any initial configuration of the pebbles, after a series of pebbling moves, it is possible to have at least $1$ pebble on every vertex of a graph
Cover Pebbling Ratio
for a graph $G$, the cover pebbling number of $G$ divided by the pebbling number of $G$
Cross Number
for a sequence $S$ in a group, the value: $\displaystyle{\sum_{g \in S}\frac{1}{|g|}}$
a graph that has all binary $d$-tuples as vertices and edges between that differ in exactly one coordinate
a simple graph whose vertices can be placed on a circle so that vertices are adjacent if and only if they appear consecutively on the circle
Davenport's Constant
the smallest $D$ such that every sequence of $D$ elements contains a zero-sum subsequence
the maximum distance between two vertices of a graph
Dominating Set
a subset $S$ of the vertex set of a graph such that every vertex outside of $S$ has a neighbor in $S$
Domination Number
the minimum size of a dominating set of vertices
Fractional Pebbling Number
$\liminf_{k \rightarrow \infty} \pi(G)/k$
the graph on $n$ vertices composed of a path on $l$ vertices with $n-l$ independent vertices incident to one of its endpoints
the length of a shortest cycle in a graph
Greedy Graph
a graph $G$ for which every configuration of size $\pi(G)$ has a greedy slolution
Greedy Solution
a pebbling solution in which every step is greedy
Greedy Step
a pebbling step from a vertex $u$ to a vertex $v$ such that ${\rm dist}(v,r)<{\rm dist}(u,r)$, where $r$ is the root vertex
H-Sum Sequence
for a subgroup $H$ of a group $G$, a sequence of elements of $G$ that sums to an element of $H$
Kneser Graph
the graph with vertices ${[m] \choose t}$ and edges $\{A,B\}$ whenever $A$ and $B$ are disjoint
the sequence $(s_1,\ldots,s_k)$ majorizes the sequence $(t_1,\ldots,t_k)$ if $s_i > t_i$ when $s_j=t_j$ for all $j
Maximum Path Partition
a path partition of a tree $T$ such that no other path partition majorizes it
Optimal Pebbling Number
the size of the smallest solvable configuration in a graph
a sequence of vertices, each adjacent to its successor
Path Partition
an $r$-path partition for some $r$
Pebbling Number
the fewest number of pebbles that gurantee that a specific graph is solvable
Pebbling Threshold
a threshold for the solvability of random pebbling configurations on graph sequences
Petersen Graph
the disjointness graph of the $2$-sets in a $5$-element set
Positive Weight Function
$w(v)>0$ for every vertex $v$, where $w(v)$ is the number of pebbles on vertex $v$
$q$-Pebbling Step
consists of removing $q$ pebbles from a vertex $u$, and placing one pebble on a neighbor $v$ of $u$
$r$-Maximum Path Partition
an $r$-path partition of a tree $T$ such that no other $r$-path partition majorizes it
$r$-Path Partition
a partition $Q=(Q_1,\ldots,Q_m)$ of the edges of a tree $T$ into paths such that each path $Q_i$ is well $r$-directed
the property that there is a sequence of pebbling moves for a given graph such that it is possible to place a pebble on the root
the property that for a given graph, it is not possible to place a pebble on the root through a sequence of pebbling moves
the pebbling target
a pebbling step from a vertex $u$ to a vertex $v$ such that ${\rm dist}(v,r) \leq {\rm dist}(u,r)$, where $r$ is the root vertex
Simple Configuration
all pebbles are concentrated on a single vertex
a configuration that is $r$-solvable for every root $r$
a graph made up of one vertex adjacent to each of $n$ independent vertices
the set of all vertices that have at least one pebble
for a property $\mathbf{P}$ of a random structure $S_p$, the set of functions $t$ for which $p \gg t$ implies that $Pr[S_p$ $has$ $\mathbf{P}] \rightarrow 0$ as $n \rightarrow \infty$, and $p \ll t$ implies that $Pr[S_p$ $has$ $\mathbf{P}] \rightarrow 1$ as $n \rightarrow \infty$
a connected graph with no cycles
the property that every configuration of size at least $\pi(G)$ has a solution in which the edges traversed by pebbling steps form an acyclic subgraph
Weighted Cover Pebbling Number
the minimum number of pebbles needed to place, after a sequence of pebbling steps, $w(v)$ pebbles on vertex $v$, for all $v$, regardless of the initial configuration
Weighted Pebbling Number
the minimum number $t$ so that, for every weight function $w$ with $|w|=\mathbf{w}$, every configuration of $t$ pebbles is $w$-solvable
Well $r$-Directed
An orientatiuon of the edges of a path $P$ with one endpoint $r$ for which every edge points to $r$
Zero-Sum Sequence
a sequence of elements of a finite group $G$ that sums to the identity of $G$