Estrella (teoría de grafos)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Estrella Sk
Star network 7.svg
Grafo estrella S7. (Algunos autores lo llaman S8.)
Vértices k+1
Aristas k
Diámetro mínimo de (2,k)
Cintura (girth) \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 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 S_3, S_4, S_5 y S_6.

Referencias[editar]