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: African American women are one of the least active demographic groups in the US, with only 36% meeting the national physical activity recommendations in comparison to 46% of White women. Physical activity begins to decline in African American women in adolescence and continues to decline into young adulthood. Yet, few interventions have been developed to promote physical activity in African American women during this critical period of life. The purpose of this article was to evaluate the acceptability and feasibility of a culturally-relevant Internet-enhanced physical activity pilot intervention for overweight/obese African American college females and to examine psychosocial and behavioral characteristics associated with intervention adherence and completion.

Methods: A 6-month single group pre-posttest design was used. Participants (n = 27) accessed a culturally-relevant Social Cognitive Theory-based physical activity promotion website while engaging in a minimum of four moderate-intensity physical activity sessions each week. Acceptability and feasibility of the intervention was assessed by participant retention and a consumer satisfaction survey completed by participants.

Results: Fifty-six percent of participants (n = 15) completed the intervention. Study completers were more physically active at baseline (P = 0.05) and had greater social support for exercise from family members (P = 0.04). Sixty percent of study completers (n = 9) reported the website as “enjoyable” or “very enjoyable” to use and 60% (n = 9) reported increased motivation from participation in the physical activity program. Moreover, 87% (n = 13) reported they would recommend the website to a friend.

Conclusions: Results provide some preliminary support for the acceptability and feasibility of an Internet-enhanced physical activity program for overweight/obese African American women, while highlighting important limitations of the approach. Successful promotion of physical activity in college aged African American women as they emerge into adulthood may result in the development of life-long healthy physical activity patterns which may ultimately reduce physical activity-related health disparities in this high risk underserved population. Future studies with larger samples are needed to further explore the use of Internet-based programs to promote physical activity in this population.