Sé que un grafo k-degenerado es un grafo no dirigido en el que cada subgrafo tiene un vértice de grado como máximo k. ¿En qué se diferencia de un grafo k-degenerado "máximo"? He oído que los grafos k-degenerados máximos son "grafos k-monocore extremos superiores". ¿Qué es un grafo k-monocore?
Respuesta
¿Demasiados anuncios?
En general, una "propiedad máxima $X$ grafo" es un grafo con la propiedad $X$ que tenga tantas aristas como sea posible en el sentido débil de que añadir cualquier arista que no esté ya presente destruiría la propiedad $X$ .
Por ejemplo, un grafo acíclico máximo es un árbol, un grafo bipartito máximo es un grafo bipartito completo y un grafo bipartito máximo es un árbol. $k$ -es un grafo completo $k$ -Gráfico parcial.
Por tanto, un máximo $k$ -grafo degenerado es un grafo con la propiedad de que si se le añade cualquier otra arista, deja de ser $k$ -degenerar. No es necesario saber qué es un $k$ -gráfico monocore es entender esta definición.
Sin embargo, parece que $k$ -El gráfico monocore es un $k$ -con grado mínimo $k$ . Para grafos con al menos $k+1$ vértices, podemos demostrar que un máximo $k$ -es un grafo $k$ -gráfico monocore:
En primer lugar $G$ sea un máximo $k$ -y $v_1, v_2, \dots, v_n$ sea una ordenación de vértices tal que $v_i$ tiene como máximo $k$ bordes a $v_{i+1}, \dots, v_n$ . (Tener tal ordenación de vértices equivale a ser $k$ -degenerada). Entonces los vértices $v_{n-k}, v_{n-k-1}, \dots, v_n$ deben formar una camarilla (y por tanto tener grado $\ge k$ ), por maximalidad: cualquier arista que falte entre ellos podría añadirse sin arruinar el ordenamiento de los vértices. Para cualquier otro vértice $v_i$ si tuviera un grado inferior a $k$ podríamos elevar su grado a $k$ añadiendo bordes a algunos de los últimos $k+1$ vértices sin arruinar el ordenamiento; por lo tanto, por maximalidad, $G$ tiene una titulación mínima de $k$ . De hecho, tiene un grado mínimo exactamente $k$ porque el grado de $v_1$ es $k$ .
No sé qué hace que $k$ -los gráficos monocore son "extremo superior".
