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.

Background: The National Health Interview Survey (NHIS) was used to ascertain whether increases in inadequate sleep differentially affected black and white Americans. We tested the hypothesis that prevalence estimates of inadequate sleep were consistently greater among blacks, and that temporal changes have affected these two strata differentially.

Methods: NHIS is an ongoing cross-sectional study of non-institutionalized US adults (≥18 years) providing socio-demographic, health risk, and medical factors. Sleep duration was coded as very short sleep [VSS] (<5 h), short sleep [SS] (5–6 h), or long sleep [LS] (>8 h), referenced to 7–8 h sleepers. Analyses adjusted for NHIS’ complex sampling design using SAS-callable SUDAAN.

Results: Among whites, the prevalence of VSS increased by 53 % (1.5 % to 2.3 %) from 1977 to 2009 and the prevalence of SS increased by 32 % (19.3 % to 25.4 %); prevalence of LS decreased by 30 % (11.2 % to 7.8 %). Among blacks, the prevalence of VSS increased by 21 % (3.3 % to 4.0 %) and the prevalence of SS increased by 37 % (24.6 % to 33.7 %); prevalence of LS decreased by 42 % (16.1 % to 9.4 %). Adjusted multinomial regression analysis showed that odds of reporting inadequate sleep for whites were: VSS (OR = 1.40, 95 % CI = 1.13-1.74, p < 0.001), SS (OR = 1.34, 95 % CI = 1.25-1.44, p < 0.001), and LS (OR = 0.94, 95 % CI = 0.85-1.05, NS). For blacks, estimates were: VSS (OR = 0.83, 95 % CI = 0.60-1.40, NS), SS (OR = 1.21, 95 % CI = 1.05-1.50, p < 0.001), and LS (OR = 0.84, 95 % CI = 0.64-1.08, NS).

Conclusions: Blacks and whites are characteristically different regarding the prevalence of inadequate sleep over the years. Temporal changes in estimates of inadequate sleep seem dependent upon individuals’ race/ethnicity.