TOPICS
Search

Spoke Graph


SpokeGraph

The term (n,k) spoke graph and notation S(n,k) are used in this work for the graph obtained from a star graph S_(n+1) by placing k vertices along each of its n spokes, in addition to the shared central vertex. While this graph has been considered by various authors, it apparently has not been given a standard name. This terminology avoids confusion with star graphs and permutation star graphs.

Special cases are summarized in the following table.

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.


See also

Bipartite Graph, Hamiltonian Path, Helm Graph, Nonhamiltonian Graph, Star Graph, Untraceable Graph, Web Graph, Wheel Graph

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Spoke Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SpokeGraph.html

Subject classifications