Graph pebbling is a network optimization model for transporting discrete resources that are consumed in transit: the movement of 2 pebbles across an edge consumes one of the pebbles. The pebbling number of a graph is the fewest number of pebbles $t$ so that, from any initial configuration of $t$ pebbles on its vertices, one can place a pebble on any given target vertex via such pebbling steps. It is known that deciding whether a given configuration on a particular graph can reach a specified target is \sf NP-complete, even for diameter $2$ graphs, and that deciding whether the pebbling number has a prescribed upper bound is $\Pi_2^{\sf P}$-complete. On the other hand, for many families of graphs there are formulas or polynomial algorithms for computing pebbling numbers; for example, complete graphs, products of paths (including cubes), trees, cycles, diameter $2$ graphs, and more. Moreover, graphs having minimum pebbling number are called Class 0, and many authors have studied which graphs are Class 0 and what graph properties guarantee it, with no characterization in sight. In this paper we investigate an important family of diameter 3 chordal graphs called split graphs; graphs whose vertex set can be partitioned into a clique and an independent set. We provide a formula for the pebbling number of a split graph, along with an algorithm for calculating it that runs in $O(n^\beta)$ time, where $\beta=2\omega/(\omega+1)\cong 1.41$ and $\omega\cong 2.376$ is the exponent of matrix multiplication. Furthermore we determine that all split graphs with minimum degree at least 3 are Class 0.

Universal cycles are generalizations of de Bruijn cycles and Gray codes that were introduced originally by Chung, Diaconis, and Graham in 1992. They have been developed by many authors since, for various combinatorial objects such as strings, subsets, permutations, partitions, vector spaces, and designs. One generalization of universal cycles, which require almost complete overlap of consecutive words, is $s$-overlap cycles, which relax such a constraint. In this paper we study weak orders, which are relations that are transitive and complete. We prove the existence of universal and $s$-overlap cycles for weak orders, as well as for fixed height and/or weight weak orders, and apply the results to cycles for ordered partitions.

Let S be a cyclic n-ary sequence. We say that S is a universal cycle ($(n,k)$-Ucycle) for k-subsets of $[n]$ if every such subset appears exactly once contiguously in S, and is a Ucycle packing if every such subset appears at most once. Few examples of Ucycles are known to exist, so the relaxation to packings merits investigation. A family $\{S_n\}$ of $(n,k)$-Ucycle packings for fixed k is a near-Ucycle if the length of $S_n$ is $(1-o(1))\binom{n}{k}$. In this paper we prove that near-$(n,k)$-Ucycles exist for all k.

The pebbling number of a graph is the smallest number t such that from any initial configuration of t pebbles one can move a pebble to any prescribed vertex by a sequence of pebbling steps. It is known that graphs whose connectivity is high compared to their diameter have a pebbling number as small as possible. We will use the above result to prove two related theorems. First, answering a question of the second author, we show that there exist graphs of arbitrarily high constant girth and least possible pebbling number. In the second application, we prove that the product of two graphs of high minimum degree has a pebbling number equal to the number of vertices of the product. This shows that Graham's product conjecture is true in the case of high minimum degree graphs. In addition, we consider a probabilistic variant of the pebbling problem and establish a pebbling threshold result for products of paths. The last result shows that the sequence of paths satisfies the probabilistic analogue of Graham's product conjecture.

A universal cycle, or Ucycle, for k-subsets of $[ n ] = \{ 1, \ldots ,n \}$ is a cyclic sequence of $\begin{pmatrix} n \\ k \end{pmatrix}$ integers with the property that each subset of $[ n ]$ of size k appears exactly once consecutively in the sequence. Chung, Diaconis, and Graham have conjectured their existence for fixed k and large n when $n| \begin{pmatrix} n \\ k \end{pmatrix}$. Here the Ucycles for $k = 3,4,6$ and large n relatively prime to k are exhibited.