Star (graph theory)

Star
The star S7. (Some authors index this as S8.)
Verticesk + 1
Edgesk
Diameter2
Girth
Chromatic number2
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 l > 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.