The star graph
of order ,
sometimes simply known as an "-star" (Harary 1994, pp. 17-18; Pemmaraju and Skiena
2003, p. 248; Tutte 2005, p. 23), is a tree on
nodes with one node having vertex
and the other
having vertex degree 1. The star graph is therefore isomorphic to the complete
(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 denotes the star graph on nodes.
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).
Note that -stars
should not be confused with the "permutation" -star graph (Akers et al. 1987) and their generalizations
known as -star
graphs (Chiang and Chen 1995) encountered in computer science and information processing.
A different generalization of the star graph in which points are placed along each of the arms of the star (as opposed to 1 for the usual star graph)
might be termed the -spoke graph.