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 gráfico. (No debe confundirse con un vértice cuantificado universalmente en la lógica de los gráficos ).
Una gráfica que contiene un vértice universal se puede llamar cono . En este contexto, el vértice universal también puede denominarse 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 subgráfico plano.
En familias especiales de gráficos
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, se pueden formar 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 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.
Las gráficas trivialmente perfectas (las gráficas de comparabilidad de los árboles teóricos del orden ) siempre contienen un vértice universal, la raíz del árbol, y con más fuerza pueden caracterizarse como las gráficas en las 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 y casi todos los gráficos desmontables tienen un vértice universal. [5]
Otras propiedades
En una gráfica con n vértices, un vértice universal es un vértice cuyo grado es exactamente n - 1 . Por lo tanto, al igual que los gráficos divididos , los gráficos con un vértice universal pueden reconocerse simplemente por sus secuencias de grados , sin tener que mirar la estructura del gráfico.
Referencias
- ^ Larrión, F .; de Mello, CP; Morgana, A .; Neumann-Lara, V .; Pizaña, MA (2004), "The clique operator on cographs and serial graphs", Discrete Mathematics , 282 (1-3): 183-191, doi : 10.1016 / j.disc.2003.10.023 , MR 2059518.
- ^ Bonato, Anthony (2008), Un curso sobre el gráfico web , Estudios de Posgrado en Matemáticas, 89 , Asociación Atlántica para la Investigación en Ciencias Matemáticas (AARMS), Halifax, NS, p. 7, doi : 10.1090 / gsm / 089 , ISBN 978-0-8218-4467-0, MR 2389013.
- ^ Wolk, ES (1962), "El gráfico de comparabilidad de un árbol", Proceedings of the American Mathematical Society , 13 : 789–795, doi : 10.2307 / 2034179 , MR 0172273.
- ^ Chvátal, Václav ; Hammer, Peter Ladislaw (1977), "Agregación de desigualdades en la programación de enteros", en Hammer, PL; Johnson, EL; Korte, BH; Nemhauser, GL (eds.), Studies in Integer Programming (Proc. Worksh. Bonn 1975) , Annals of Discrete Mathematics, 1 , Amsterdam: North-Holland, págs. 145-162.
- ^ Bonato, Anthony; Kemkes, Graeme; Prałat, Paweł (2012), "Casi todas las gráficas cop-win contienen un vértice universal", Discrete Mathematics , 312 (10): 1652–1657, doi : 10.1016 / j.disc.2012.02.018 , MR 2901161.
enlaces externos
- Weisstein, Eric W. , "Cone Graph" , MathWorld