Star Graph (original) (raw)

Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology

Alphabetical Index New in MathWorld

StarGraphs

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 onn 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 are also dominating unique.

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

pi_(s_n)(z)=z(z-1)^(n-1),

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). The simplex graph of S_n is the book graph B_(n-1)=S_n square P_2.

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

References

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." Electronic J. Combinatorics, Dynamic Survey DS6, Oct. 30, 2025. https://doi.org/10.37236/27.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.House of Graphs. Star Graphs. S5, S6,S7, S8,S9, S10,S11, ....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." FromMathWorld--A Wolfram Resource. https://mathworld.wolfram.com/StarGraph.html

Subject classifications