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
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 Sk es el grafo bipartito completo K1,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 Sk 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 , , y .

Referencias