vértice universal

En teoría de grafos , un vértice universal es un vértice de un grafo no dirigido que es adyacente a todos los demás vértices del grafo. También se le puede llamar 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 estos términos para cuantificadores universales en la lógica de grafos y para grafos de ápice .

Los grafos que contienen un vértice universal incluyen las estrellas , los grafos trivialmente perfectos y los grafos de amistad . En los grafos de rueda (los grafos de pirámides ) y en 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, se denomina grafo de victoria de policía , y casi todos los grafos de victoria de policía contienen un vértice universal.

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

Las estrellas son precisamente los árboles que tienen un vértice universal, y pueden construirse añadiendo un vértice universal a un conjunto independiente . Los grafos rueda pueden formarse añadiendo un vértice universal a un grafo ciclo . ^{[ 2 ]} Los grafos trivialmente perfectos se obtienen a partir de árboles con raíz 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 estricta, pueden caracterizarse 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. Pueden definirse como los grafos que pueden formarse 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 esqueletos grafos de rueda ^{[ 5 ]} y , de forma más general, una pirámide de dimensiones superiores es un politopo cuyas caras de todas las dimensiones conectan un vértice del ápice con todas las caras de una base de dimensiones inferiores, incluyendo todos los vértices de la base. Se dice que el politopo es piramidal en su ápice, y puede tener más de un ápice. Sin embargo, la existencia de politopos vecinos implica que el grafo de un politopo puede tener un vértice universal, o todos los vértices universales, sin que el politopo en sí sea una pirámide ^{[ 6 ] .}

El teorema de la amistad establece que, si cada par de vértices en un grafo finito tiene exactamente un vecino común, entonces el grafo contiene un vértice universal. Los grafos descritos por este teorema son los grafos de amistad , formados por sistemas de triángulos conectados entre sí en un vértice común, el vértice universal. ^{[ 7 ]} La suposición de que el grafo es finito es importante; existen grafos infinitos en los que cada par de vértices tiene un vecino común, pero sin 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 vecindario cerrado sea un subconjunto del vecindario 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, se ajusta a esta definición. Casi todos los grafos desmantelables tienen un vértice universal, en el sentido de que la fracción de${\displaystyle n}$-grafos desmantelables de vértice que tienen un vértice universal tienden a uno en el límite cuando${\displaystyle n}$va al infinito. Los grafos desmantelables también se denominan grafos de victoria del policía, porque el bando que juega de policía gana un determinado juego de policías y ladrones definido en estos 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 llamarse 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)}$obedecer 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 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 gráficos etiquetados con${\displaystyle n}$Los vértices, de los cuales al menos uno es universal (o equivalentemente aislado, en el grafo complemento ), se pueden 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 sobreconteo restando los recuentos de los grafos con dos vértices universales elegidos, luego sumando los recuentos de los grafos con tres vértices universales elegidos, etc. Esto produce la fórmula

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

En cada término de la suma,${\displaystyle k}$es el número de vértices elegidos para ser universales, y${\displaystyle {\tbinom {n}{k}}}$es el número de maneras de hacer esta elección.${\displaystyle {\tbinom {nk}{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 exponente de una potencia de dos se cuenta el número de grafos con los vértices elegidos como universales. ^{[ 12 ]}

A partir de${\displaystyle n=1}$, estos números de gráficos son:

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

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

La propiedad de tener un vértice universal se puede expresar mediante una fórmula en la lógica de primer orden de los grafos .${\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 universales y existenciales , puede utilizarse en un algoritmo manejable de parámetros fijos para probar si todos los componentes de un grafo pueden hacerse tener vértices universales mediante${\displaystyle k}$pasos para eliminar 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 probar si un grafo etiquetado tiene una propiedad, dado el acceso al grafo solo a través de una subrutina que puede probar si dos vértices dados son adyacentes. En un grafo con${\displaystyle n}$vértices, se puede determinar todo el grafo y probar cualquier propiedad, utilizando${\displaystyle {\tbinom {n}{2}}}$consultas. Una propiedad de un grafo es evasiva si ningún algoritmo puede probarla garantizando menos 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 tal manera que queda un número impar de grafos restantes que tienen 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 ]}