En teoría de grafos , una estrella S k es el grafo bipartito completo K 1, k : un árbol con un nodo interno y k hojas (pero sin nodos internos y k + 1 hojas cuando k ≤ 1 ). Alternativamente, algunos autores definen S k como el árbol de orden k con diámetro máximo 2; en cuyo caso una estrella de k > 2 tiene k − 1 hojas.
Una estrella con tres aristas se llama garra .
La estrella S k tiene aristas elegantes cuando k es par y no cuando k es impar. Es un grafo de cerillas transitivo de aristas y tiene diámetro 2 (cuando l > 1 ), circunferencia ∞ (no tiene ciclos), índice cromático k y número cromático 2 (cuando k > 0 ). Además, la estrella tiene un gran grupo de automorfismos, es decir, el grupo simétrico de k letras.
Las estrellas también pueden describirse como los únicos gráficos conexos en los que como máximo un vértice tiene grado mayor que uno.
Las garras son notables en la definición de grafos sin garras , grafos que no tienen ninguna garra como subgrafo inducido . [1] [2] También son uno de los casos excepcionales del teorema de isomorfismo de grafos de Whitney : en general, los grafos con grafos lineales isomorfos son en sí mismos isomorfos, con la excepción de la garra y el triángulo K 3 . [3]
Una estrella es un tipo especial de árbol . Como cualquier árbol, las estrellas pueden codificarse mediante una secuencia de Prüfer ; la secuencia de Prüfer para una estrella K 1, k consta de k − 1 copias del vértice central. [4]
Varios invariantes de grafos se definen en términos de estrellas. La arboricidad de estrellas es el número mínimo de bosques en los que se puede dividir un grafo de manera que cada árbol de cada bosque sea una estrella [5] , y el número cromático de estrellas de un grafo es el número mínimo de colores necesarios para colorear sus vértices de manera que cada dos clases de color juntas formen un subgrafo en el que todos los componentes conectados sean estrellas [6] . Los grafos con ancho de rama 1 son exactamente los grafos en los que cada componente conectado es una estrella [7] .
El conjunto de distancias entre los vértices de una garra proporciona un ejemplo de un espacio métrico finito que no puede integrarse isométricamente en un espacio euclidiano de cualquier dimensión. [8]
La red en estrella , una red informática modelada según el gráfico en estrella, es importante en la computación distribuida .
Una realización geométrica del grafo estrella, formada mediante la identificación de los bordes con intervalos de cierta longitud fija, se utiliza como modelo local de curvas en geometría tropical . Una curva tropical se define como un espacio métrico que es localmente isomorfo a un grafo métrico en forma de estrella.
