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 NP-complete, even for diameter 2 graphs, and that deciding whether the pebbling number has a prescribed upper bound is Π[P over 2]-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[superscript β]) time, where β = 2ω/(ω + 1) [= over ∼] 1.41 and ω [= over ∼] 2.376 is the exponent of matrix multiplication. Furthermore we determine that all split graphs with minimum degree at least 3 are Class 0.

The aim of this study was to evaluate the effects of moderate aerobic exercise training on sleep, depression, cortisol, and markers of immune function in patients with chronic primary insomnia. Twenty-one sedentary participants (16 women aged 44.7 ± 9 years) with chronic primary insomnia completed a 4-month intervention of moderate aerobic exercise. Compared with baseline, polysomnographic data showed improvements following exercise training. Also observed were reductions in depression symptoms and plasma cortisol. Immunologic assays revealed a significant increase in plasma apolipoprotein A (140.9 ± 22 to 151.2 ± 22 mg/dL) and decreases in CD4 (915.6 ± 361 to 789.6 ± 310 mm[superscript 3]) and CD8 (532.4 ± 259 to 435.7 ± 204 mm[superscript 3]). Decreases in cortisol were significantly correlated with increases in total sleep time (r = -0.51) and REM sleep (r = -0.52). In summary, long-term moderate aerobic exercise training improved sleep, reduced depression and cortisol, and promoted significant changes in immunologic variables.