# Star (graph theory)

(Redirected from Star graph)
Star The star S7. (Some authors index this as S8.)
Verticesk+1
Edgesk
Diameterminimum of (2, k)
Girth
Chromatic numberminimum of (2, k + 1)
Chromatic indexk
PropertiesEdge-transitive
Tree
Unit distance
Bipartite
NotationSk
Table of graphs and parameters

In graph theory, a star Sk is the complete bipartite graph K1,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 order k with maximum diameter 2; in which case a star of k > 2 has k − 1 leaves.

A star with 3 edges is called a claw.

The star Sk is edge-graceful when k is even and not when k is odd. It is an edge-transitive matchstick graph, and has diameter 2 (when k > 1), girth ∞ (it has no cycles), chromatic index k, and chromatic number 2 (when k > 0). Additionally, the star has large automorphism group, namely, the symmetric group on k letters.

Stars may also be described as the only connected graphs in which at most one vertex has degree greater than one.

## Relation to other graph families

Claws are notable in the definition of claw-free graphs, graphs that do not have any claw as an induced subgraph. They are also one of the exceptional cases of the Whitney graph isomorphism theorem: in general, graphs with isomorphic line graphs are themselves isomorphic, with the exception of the claw and the triangle K3.

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.

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, 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. The graphs of branchwidth 1 are exactly the graphs in which each connected component is a star.

## 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.

The star network, a computer network modeled after the star graph, is important in distributed computing.

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.