In graph theory, a starSk is the complete bipartite graphK1,k : a tree with one internal node and k leaves (but no internal nodes and k + 1 leaves when k ≤ 1). Alternatively, some authors define Sk to be the tree of orderk with maximum diameter 2; in which case a star of k > 2 has k − 1 leaves.
A star is a special kind of tree. As with any tree, stars may be encoded by a Prüfer sequence; the Prüfer sequence for a star K1,k consists of k − 1 copies of the center vertex.[4]
Several graph invariants are defined in terms of stars. Star arboricity is the minimum number of forests that a graph can be partitioned into such that each tree in each forest is a star,[5] and the star chromatic number of a graph is the minimum number of colors needed to color its vertices in such a way that every two color classes together form a subgraph in which all connected components are stars.[6] The graphs of branchwidth 1 are exactly the graphs in which each connected component is a star.[7]
The star graphs S3, S4, S5 and S6.
Other applications
The set of distances between the vertices of a claw provides an example of a finite metric space that cannot be embedded isometrically into a Euclidean space of any dimension.[8]
A geometric realization of the star graph, formed by identifying the edges with intervals of some fixed length, is used as a local model of curves in tropical geometry. A tropical curve is defined to be a metric space that is locally isomorphic to a star-shaped metric graph.
See also
Star (simplicial complex) - a generalization of the concept of a star from a graph to an arbitrary simplicial complex.
References
Wikimedia Commons has media related to Star graphs.