Star Graph


The star graph S_n of order n, sometimes simply known as an "n-star" (Harary 1994, pp. 17-18; Pemmaraju and Skiena 2003, p. 248; Tutte 2005, p. 23), is a tree on n nodes with one node having vertex degree n-1 and the other n-1 having vertex degree 1. The star graph S_n is therefore isomorphic to the complete bipartite graph K_(1,n-1) (Skiena 1990, p. 146).

Note that there are two conventions for the indexing for star graphs, with some authors (e.g., Gallian 2007), adopting the convention that S_n denotes the star graph on n+1 nodes.

S_4 is isomorphic to "the" claw graph. A star graph is sometimes termed a "claw" (Hoffman 1960) or a "cherry" (Erdős and Rényi 1963; Harary 1994, p. 17).

Star graphs S_n are always graceful and star graphs on n>=4 nodes are series-reduced trees.

Star graphs can be constructed in the Wolfram Language using StarGraph[n]. Precomputed properties of star graphs are available via GraphData[{"Star", n}].

The chromatic polynomial of S_n is given by


and the chromatic number is 1 for n=1, and chi(S_n)=2 otherwise.

The line graph of the star graph S_n is the complete graph K_(n-1).

Note that n-stars should not be confused with the "permutation" n-star graph (Akers et al. 1987) and their generalizations known as (n,k)-star graphs (Chiang and Chen 1995) encountered in computer science and information processing.

A different generalization of the star graph in which k points are placed along each of the n-1 arms of the star (as opposed to 1 for the usual star graph) might be termed the (n,k)-spoke graph.

See also

Banana Tree, Cayley Tree, Claw Graph, Firecracker Graph, Nauru Graph, Permutation Star Graph, Shuffle-Exchange Graph, Spoke Graph, Tree

Explore with Wolfram|Alpha


Akers, S.; Harel, D.; and Krishnamurthy, B. "The Star Graph: An Attractive Alternative to the n-Cube." In Proc. International Conference of Parallel Processing, pp. 393-400, 1987.Chiang, W.-K. and Chen, R.-J. "The (n,k)-Star Graph: A Generalized Star Graph." Information Proc. Lett. 56, 259-264, 1995.Erdős, P. and Rényi, A. "Asymmetric Graphs." Acta Math. Acad. Sci. Hungar. 14, 295-315, 1963.Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018., F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Hoffman, A. J. "On the Uniqueness of the Triangular Association Scheme." Ann. Math. Stat. 31, 492-497, 1960.Pemmaraju, S. and Skiena, S. "Cycles, Stars, and Wheels." §6.2.4 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 248-249, 2003.Skiena, S. "Cycles, Stars, and Wheels." §4.2.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 83 and 144-147, 1990.Tutte, W. T. Graph Theory. Cambridge, England: Cambridge University Press, 2005.

Referenced on Wolfram|Alpha

Star Graph

Cite this as:

Weisstein, Eric W. "Star Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications