Consider a star graph consisting of a central hub vertex and
spokes, but instead of placing a single point at the end of
each spoke, place
points along it (in addition to the shared central point). While this graph has been
considered by various authors, it apparently has not been given a standard name.
In this work, to avoid confusion with star graphs and permutation
star graphs, the term
spoke graph and notation
are used.
Special cases are summarized in the following table.
Considering vertices by their distance from the central vertex shows that the bipartition classes of have sizes
and
for even
, and sizes
and
for odd
. Therefore the bipartition sizes differ by 1 for even
and by
for odd
. In particular, for odd
and
,
is an untraceable
graph; for even
,
the same bipartition-size obstruction shows that
is nonhamiltonian.
For
,
is also untraceable
since a traceable tree
must be a path graph.