En teoría de grafos , una estrella S k es el gráfico 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 3 aristas se llama garra .
La estrella S k tiene bordes elegantes cuando k es par y no cuando k es impar. Es un gráfico de cerilla de borde transitivo 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 automorfismo, es decir, el grupo simétrico en k letras.
Las estrellas también pueden describirse como los únicos gráficos conectados en los que como máximo un vértice tiene un grado mayor que uno.
Las garras son notables en la definición de grafos sin garras , gráficos que no tienen ninguna garra como subgrafo inducido . [1] [2] También son uno de los casos excepcionales del teorema de isomorfismo del gráfico de Whitney : en general, los gráficos con gráficos lineales isomórficos son en sí mismos isomórficos, con la excepción de la garra y el triángulo K 3 . [3]
Una estrella es un tipo especial de árbol . Como ocurre con cualquier árbol, las estrellas pueden estar codificadas 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]
Varias invariantes gráficas se definen en términos de estrellas. La arboricidad de las estrellas es el número mínimo de bosques en los que se puede dividir un gráfico de modo que cada árbol de cada bosque sea una estrella, [5] y el número cromático de estrellas de un gráfico es el número mínimo de colores necesarios para colorear sus vértices de tal una forma en que cada dos clases de colores juntas forman un subgrafo en el que todos los componentes conectados son estrellas. [6] Las gráficas de ancho de rama 1 son exactamente las gráficas en las 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 incrustarse isométricamente en un espacio euclidiano de ninguna dimensión. [8]
La red en estrella , una red informática modelada a partir del gráfico estelar, es importante en la informática distribuida .
Una realización geométrica del gráfico estelar, formada identificando las aristas 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 gráfico métrico en forma de estrella.
