Star (graph theory)

Star
The star S7. (Some authors index this as S8.)
Vertices	k+1
Edges	k
Diameter	minimum of (2, k)
Girth	∞
Chromatic number	minimum of (2, k + 1)
Chromatic index	k
Properties	Edge-transitive Tree Unit distance Bipartite
Notation	Sk

In graph theory, a star S_k is the complete bipartite graph K_1,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 S_k 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 S_k 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.

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 K₃.

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 K_1,k consists of k − 1 copies of the center vertex.