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
degree
and the other
having vertex degree 1. The star graph is therefore isomorphic to the complete
bipartite graph
(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).
Star graphs can be constructed in the Wolfram Language using StarGraph[n].
Precomputed properties of star graphs are available via GraphData["Star", n].
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.
Akers, S.; Harel, D.; and Krishnamurthy, B. "The Star Graph: An Attractive Alternative to the -Cube." In Proc. International Conference of Parallel
Processing, pp. 393-400, 1987.Chiang, W.-K. and Chen, R.-J.
"The -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. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Harary,
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.