Estrella (teoría de grafos)

En teoría de grafos, una estrella S_k es el grafo bipartito completo K_1,k, un árbol con un vértice interno y k hojas. Una estrella con 3 aristas se conoce en inglés como claw (garra o garfio).

Estrella Sk
Grafo estrella S7. (Algunos autores lo llaman S8.)
Vértices	k+1
Aristas	k
Diámetro	mínimo de (2,k)
Cintura	${\displaystyle \infty }$
Número cromático	mínimo de (2,k+1)
Índice cromático	k
Propiedades	bipartito, árbol transitivo por aristas distancia unitaria

La estrella S_k es transitiva en aristas, tiene una distancia de 1 y un diámetro de 2, girth ∞, índice cromático k y número cromático 2.

Las estrellas pueden también describirse como los únicos grafos conexos en que a lo más un vértice tiene grado mayor que uno.

Las estrellas ${\displaystyle S_{3}}$, ${\displaystyle S_{4}}$, ${\displaystyle S_{5}}$ y ${\displaystyle S_{6}}$.