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 | |
[editar datos en Wikidata] |
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/Star_graphs.svg/600px-Star_graphs.svg.png)
Referencias
- Weisstein, Eric W. «Star Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
Datos: Q2589168
Multimedia: Star graphs / Q2589168