Vértice universal

En teoría de grafos, un vértice universal se define como aquel vértice de un grafo que es adyacente a todos los demás vértices del grafo. También puede llamarse vértice dominante, ya que forma un conjunto dominante de un elemento en el grafo. Un grafo que contiene un vértice universal puede llamarse cono, y su vértice universal puede llamarse ápice del cono.^[1] Esta terminología debe distinguirse del uso no relacionado de estas palabras para el cuantificador universal en lógica de grafos, y para el grafo de ápice.

Los grafos que contienen un vértice universal incluyen las estrellas, el grafo trivialmente perfecto y grafo de la amistad. Para los grafos rueda (los grafos de las pirámides) y los grafos de politopos piramidales de dimensiones superiores, el vértice en el ápice de la pirámide es universal. Cuando un grafo contiene un vértice universal, es un grafo de victoria del policía, y casi todos los grafos de este tipo contienen un vértice universal.

El número de grafos etiquetados que contienen un vértice universal se puede contar mediante el principio de inclusión-exclusión, lo que demuestra que existe un número impar de dichos grafos para cualquier número par de vértices. Esto, a su vez, se puede usar para demostrar que la propiedad de tener un vértice universal es evasiva: probar esta propiedad puede requerir verificar la adyacencia de todos los pares de vértices. Sin embargo, un vértice universal se puede reconocer inmediatamente por su grado: en un grafo con ${\displaystyle n}$ vértices, tiene grado ${\displaystyle n-1}$. Los vértices universales se pueden describir mediante una fórmula lógica corta, que se ha utilizado en algoritmos de grafos para analizar propiedades relacionadas.

Las estrellas son precisamente los árboles que tienen un vértice universal, y se pueden construir agregando un vértice universal a un conjunto independiente. Los grafos rueda se pueden formar añadiendo un vértice universal a un grafo ciclo.^[2] Los grafos trivialmente perfectos se obtienen a partir de un árbol enraizado añadiendo una arista que conecta cada par ancestro-descendiente en el árbol. Estos siempre contienen un vértice universal, la raíz del árbol. De forma más precisa, se pueden caracterizar como los grafos finitos en los que cada subgrafo inducido conexo contiene un vértice universal.^[3] Los grafos umbral conexos forman una subclase de los grafos trivialmente perfectos, por lo que también contienen un vértice universal. Se pueden definir como los grafos que se pueden formar mediante la adición repetida de un vértice universal o un vértice aislado (uno sin aristas incidentes).^[4]

En geometría, las pirámides tridimensionales tienen como grafos rueda sus esqueletos,^[5] y, de forma más general, una pirámide de mayor dimensión es un politopo cuyas caras de todas las dimensiones conectan un vértice apical con todas las caras de una base de menor dimensión, incluyendo todos los vértices de la base. Se dice que el politopo es piramidal en su vértice, y puede tener más de uno. Sin embargo, la existencia de politopo vecino implica que el grafo de un politopo puede tener un vértice universal, o todos sus vértices universales, sin que el politopo en sí sea una pirámide.^[6]

El teorema de la amistad establece que, si cada dos vértices en un grafo finito tienen exactamente un vecino común, entonces el grafo contiene un vértice universal. Los grafos descritos por este teorema son los grafos de la amistad, formados por sistemas de triángulos conectados entre sí en un vértice común, el vértice universal.^[7] Es importante la suposición de que el grafo es finito, dado que existen grafos infinitos en los que cada dos vértices tienen un vecino común, pero sin un vértice universal.^[8]

Todo grafo finito con un vértice universal es un grafo desmantelable, lo que significa que puede reducirse a un solo vértice eliminando repetidamente un vértice cuyo entorno cerrado sea un subconjunto del entorno cerrado de otro vértice. En un grafo con un vértice universal, cualquier secuencia de eliminación que deje el vértice universal en su lugar, eliminando todos los demás vértices, cumple con esta definición. Casi todos los grafos desmantelables tienen un vértice universal, en el sentido de que la fracción de los grafos desmantelables de ${\displaystyle n}$ vértices que poseen un vértice universal tiende a uno en el límite cuando ${\displaystyle n}$ tiende a infinito. Estos grafos también se denominan grafos de victoria del policía, ya que el bando que actúa como policía gana un determinado juego de policías y ladrones definido en dichos grafos. ^[9]

Cuando un grafo tiene un vértice universal, el conjunto de vértices que consta únicamente de ese vértice es un conjunto dominante, un conjunto que incluye o es adyacente a cada vértice. Por esta razón, en el contexto de los problemas de conjuntos dominantes, un vértice universal también puede denominarse vértice dominante.^[10] Para el producto fuerte de grafos ${\displaystyle G\boxtimes H}$, los números de dominación ${\displaystyle \gamma (G)}$ y ${\displaystyle \gamma (H)}$ cumplen las desigualdades

$${\displaystyle \max\{\gamma (G),\gamma (H)\}\leq \gamma (G\boxtimes H)\leq \gamma (G)\gamma (H).}$$

Esto implica que un producto fuerte tiene un vértice dominante si y solo si ambos de sus factores lo tienen. En este caso, el límite superior de su número dominante es uno, y en cualquier otro caso, el límite inferior es mayor que uno.^[11]

El número de grafos etiquetados con ${\displaystyle n}$ vértices, de los cuales al menos uno es universal (o equivalentemente aislado, en el grafo complemento), se puede contar mediante el principio de inclusión-exclusión, en el que se cuentan los grafos en los que un vértice elegido es universal, luego se corrige el conteo excesivo restando los conteos de los grafos con dos vértices universales elegidos, y luego se suman los conteos de los grafos con tres vértices universales elegidos. Esto produce la fórmula:

${\displaystyle \displaystyle \sum _{k=1}^{n}(-1)^{k+1}{\binom {n}{k}}2^{\tbinom {n-k}{2}}.}$

En cada término de la suma, ${\displaystyle k}$ representa el número de vértices elegidos como universales, y ${\displaystyle {\tbinom {n}{k}}}$ representa el número de maneras de realizar esta elección. ${\displaystyle {\tbinom {n-k}{2}}}$ es el número de pares de vértices que no incluyen un vértice universal elegido, y al tomar este número como el exponente de una potencia de dos, se cuenta el número de grafos con los vértices elegidos como universales.^[12]

Partiendo de ${\displaystyle n=1}$, estos números de grafos son:

1, 1, 4, 23, 256, 5319, 209868, 15912975, 2343052576, 675360194287, ... (sucesión A327367 en OEIS).^[13]

Para ${\displaystyle n>1}$, estos números son impares cuando ${\displaystyle n}$ es par, y viceversa.^[12] La versión sin etiquetas de este problema de enumeración de grafos es trivial, en el sentido de que el número de grafos sin etiquetas con ${\displaystyle n}$ vértices y un vértice universal es el mismo que el número de grafos con ${\displaystyle (n-1)}$ vértices.^[13]

En un grafo con ${\displaystyle n}$ vértices, un vértice universal es aquel cuyo grado es exactamente ${\displaystyle n-1}$.^[10]

La propiedad de tener un vértice universal se puede expresar mediante una fórmula de primer orden en lógica de grafos. Al usar ${\displaystyle \sim }$ para indicar la relación de adyacencia en un grafo, un grafo ${\displaystyle G}$ tiene un vértice universal si y solo si modela la fórmula $${\displaystyle \exists u\forall v{\bigl (}(u\neq v)\Rightarrow (u\sim v){\bigr )}.}$$ La existencia de esta fórmula, y su pequeño número de alternancias entre cuantificadores existenciales y universales, se puede usar en un algoritmo manejable de parámetros fijos para comprobar si todos los componentes de un grafo pueden tener vértices universales mediante ${\displaystyle k}$ pasos de eliminación de un vértice de cada componente.^[14]

La propiedad de tener un vértice universal (o equivalentemente un vértice aislado) se ha considerado con respecto a la conjetura de Aanderaa-Karp-Rosenberg sobre cuántas consultas (llamadas a subrutinas) se necesitan para comprobar si un grafo etiquetado tiene una propiedad, dado el acceso al grafo solo a través de una subrutina que puede comprobar si dos vértices dados son adyacentes. En un grafo con ${\displaystyle n}$ vértices, se puede determinar el grafo completo y comprobar cualquier propiedad usando ${\displaystyle {\tbinom {n}{2}}}$ consultas. Una propiedad de un grafo es evasiva si ningún algoritmo puede probarla garantizando un menor número de consultas. Probar la existencia de un vértice universal es evasivo en grafos con un número par de vértices. Hay un número impar de estos grafos que tienen un vértice universal. Un algoritmo de prueba puede verse obligado a consultar todos los pares de vértices mediante una subrutina de adyacencia que siempre responde de forma que quede un número impar de grafos restantes con un vértice universal. Hasta que se prueben todas las aristas, el número total de grafos restantes será par, por lo que el algoritmo no podrá determinar si el grafo que está consultando tiene un vértice universal.^[12]