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

Pebbling Glossary Page

2-Connected
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
Book
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
Complete
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
Configuration
a function that indicates the number of pebbles per vertex
Connectivity
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|}}$
Cube
a graph that has all binary $d$-tuples as vertices and edges between that differ in exactly one coordinate
Cycle
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
Diameter
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$
Fuse
the graph on $n$ vertices composed of a path on $l$ vertices with $n-l$ independent vertices incident to one of its endpoints
Girth
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
Majorize
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 Path 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$vq$-Pebbling Step consists of removing$q$pebbles from a vertex$u$, and placing one pebble on a neighbor$v$of$ur$-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 r-Solvable 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 r-Unsolvable the property that for a given graph, it is not possible to place a pebble on the root through a sequence of pebbling moves Root the pebbling target Semi-greedy 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 Solvable a configuration that is$r$-solvable for every root$r$Star a graph made up of one vertex adjacent to each of$n$independent vertices Support the set of all vertices that have at least one pebble Threshold 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_phas\mathbf{P}] \rightarrow 0$as$n \rightarrow \infty$, and$p \ll t$implies that$Pr[S_phas\mathbf{P}] \rightarrow 1$as$n \rightarrow \infty$Tree a connected graph with no cycles Tree-Solvable 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\$