Estrella (teoría de grafos)

En teoría de grafos , la estrella S _k es el grafo bipartito completo K _{1, k} , es decir, es un árbol con un nodo interno y k hojas ^{[ a ]} ​​. 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 puntas se llama garra .

La estrella S _k es elegante en los bordes cuando k es par y no cuando k es impar. Es un grafo de cerillas transitivo en los bordes y tiene diámetro 2 (cuando k > 1 ), circunferencia${\displaystyle \infty }$(no tiene ciclos), índice cromático k y número cromático 2 (cuando k > 0 ). Además, la estrella tiene un grupo de automorfismos grande, a saber, el grupo simétrico en k letras.

Las estrellas también pueden describirse como los únicos grafos conexos 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 libres de 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 de líneas isomorfos son ellos mismos isomorfos, con la excepción de la garra y el triángulo K ₃ . ^{[ 3 ]}

Una estrella es un tipo especial de árbol . Al igual que 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 ]}

Se definen varios invariantes de grafos en términos de estrellas. La arboricidad estelar es el número mínimo de bosques en los que se puede particionar un grafo de manera que cada árbol en cada bosque sea una estrella, ^{[ 5 ]} y el número cromático estelar de un grafo es el número mínimo de colores necesarios para colorear sus vértices de tal manera que cada par de clases de color juntas formen un subgrafo en el que todos los componentes conexos sean estrellas. ^{[ 6 ]} Los grafos de ancho de rama 1 son precisamente los grafos en los que cada componente conexo 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 de un grafo en estrella, es importante en la computación distribuida .

En geometría tropical, se utiliza una representación geométrica del grafo estrellado, formada al identificar las aristas con intervalos de longitud fija, como modelo local de curvas . Una curva tropical se define como un espacio métrico localmente isomorfo a un grafo métrico estrellado.

• Árbol estrellado : un árbol con como máximo un vértice de grado mayor que 2; una subdivisión de una estrella.
• Estrella (complejo simplicial) : una generalización del concepto de estrella de un grafo a un complejo simplicial arbitrario.