Estrella (teoría de grafos)

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

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

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 $S_{3}$, $S_{4}$, $S_{5}$ y $S_{6}$.

Referencias

• Weisstein, Eric W. «Star Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q2589168
• Multimedia: Star graphs / Q2589168