Graceful Labeling of a Family of Quasistars With Paths in Arithmetic Progression

Abstract

The problem of graceful labeling of a particular class of trees called quasistars is considered. Such a quasistar is a tree $Q$ with $k$ distinct paths with lengths $1,d+1,2d+1,\dots ,(k-1)d+1$ joined at a unique vertex $\theta$.

Thus, $Q$ has $1+[1+(d+1)+(2d+1)+\dots +(k-1)d+1)]=1+k+\frac{k(k-1)d}{2}$ vertices. The $k$ paths of $Q$ have lengths in arithmetic progression with common difference $d$. It is shown that $Q$ has a graceful labeling for all $k\le 6$ and all values of $d$.