TOPICS
Search

Spoke Graph

SpokeGraph

Consider a star graph S_(n+1) consisting of a central hub vertex and n spokes, but instead of placing a single point at the end of each spoke, place k 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 (n,k) spoke graph and notation S(n,k) are used.

Special cases are summarized in the following table.

(n,k) graph
(1,k) path graph P_(k+1)
(2,k) path graph P_(2k+1)
(3,1) claw graph K_(1,3)
(n,1) star graph S_(n+1)

Considering vertices by their distance from the central vertex shows that the bipartition classes of S(n,k) have sizes 1+nk/2 and nk/2 for even k, and sizes 1+n(k-1)/2 and n(k+1)/2 for odd k. Therefore the bipartition sizes differ by 1 for even k and by n-1 for odd k. In particular, for odd k and n>2, S(n,k) is an untraceable graph; for even k, the same bipartition-size obstruction shows that S(n,k) is nonhamiltonian. For n>=3, S(n,k) is also untraceable since a traceable tree must be a path graph.

AltStyle によって変換されたページ (->オリジナル) /