vértice universal
En la teoría de grafos , un vértice universal es un vértice de un gráfico no dirigido que es adyacente a todos los demás vértices del gráfico. También puede llamarse vértice dominante , ya que forma un conjunto dominante de un elemento en el gráfico. (No debe confundirse con un vértice universalmente cuantificado en la lógica de los gráficos ).
Un gráfico que contiene un vértice universal puede llamarse cono . En este contexto, el vértice universal también puede llamarse vértice del cono. [1] Sin embargo, esta terminología entra en conflicto con la terminología de los gráficos de vértice , en los que un vértice es un vértice cuya eliminación deja un subgrafo plano.
Las estrellas son exactamente los árboles que tienen un vértice universal y pueden construirse agregando un vértice universal a un conjunto independiente . Los gráficos de rueda , de manera similar, pueden formarse agregando un vértice universal a un gráfico de ciclo . [2] En geometría, las pirámides tridimensionales tienen gráficos de ruedas como sus esqueletos y, de manera más general, el gráfico de cualquier pirámide de dimensiones superiores tiene un vértice universal como vértice de la pirámide.
Los grafos trivialmente perfectos (los grafos de comparabilidad de árboles teóricos del orden ) siempre contienen un vértice universal, la raíz del árbol, y más fuertemente se pueden caracterizar como grafos en los que cada subgrafo inducido conectado contiene un vértice universal. [3] Los gráficos de umbral conectados forman una subclase de los gráficos trivialmente perfectos, por lo que también contienen un vértice universal; pueden definirse como los gráficos que se pueden formar mediante la adición repetida de un vértice universal o un vértice aislado (uno sin bordes incidentes). [4]
Cada gráfico con un vértice universal es un gráfico desmontable , lo que significa que se puede reducir a un solo vértice eliminando repetidamente los vértices cuyos vecindarios cerrados son subconjuntos de los vecindarios cerrados de otros vértices. Cualquier secuencia de eliminación que deje el vértice universal en su lugar, eliminando todos los demás vértices, se ajusta a esta definición. Casi todos los gráficos desarmables tienen un vértice universal, en el sentido de que la fracción de gráficos desarmables de -vértice que tienen un vértice universal tiende a uno en el límite que tiende a infinito. [5]
Como un caso especial de la observación de que el número de dominación aumenta multiplicativamente como máximo en productos fuertes de grafos , [6] un producto fuerte tiene un vértice universal si y solo si ambos factores lo hacen.
