Star (graph theory)

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

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 \leq 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 $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.

Star
The star $S 7$ . (Some authors index this as $S 8$ .)
Vertices	$k + 1$
Edges	$k$
Diameter	2
Girth	∞
Chromatic number	2
Chromatic index	$k$
Properties	Edge-transitive Tree Unit distance Bipartite
Notation	$S k$
Table of graphs and parameters