Gráfico de indiferencia
En la teoría de grafos , una rama de las matemáticas, un gráfico de indiferencia es un gráfico no dirigido que se construye asignando un número real a cada vértice y conectando dos vértices por un borde cuando sus números están dentro de una unidad entre sí. [1] Los gráficos de indiferencia son también los gráficos de intersección de conjuntos de intervalos unitarios , o de intervalos correctamente anidados (intervalos ninguno de los cuales contiene otro). Con base en estos dos tipos de representaciones de intervalo, estas gráficas también se denominan gráficas de intervalo unitario o gráficas de intervalo adecuado ; forman una subclase de los gráficos de intervalo .
Debido a que son casos especiales de gráficos de intervalo , los gráficos de indiferencia tienen todas las propiedades de los gráficos de intervalo; en particular, son un caso especial de los gráficos cordales y de los gráficos perfectos . También son un caso especial de los gráficos circulares , algo que no es cierto en los gráficos de intervalo en general.
En el modelo Erdős-Rényi de gráficos aleatorios , un gráfico -vertex cuyo número de aristas sea significativamente menor que será un gráfico de indiferencia con alta probabilidad, mientras que un gráfico cuyo número de aristas sea significativamente mayor que no será un gráfico de indiferencia con alta probabilidad. [9]
El ancho de banda de un gráfico arbitrario es uno menos que el tamaño de la camarilla máxima en un gráfico de indiferencia que contiene como subgráfico y se elige para minimizar el tamaño de la camarilla máxima. [10] Esta propiedad es paralela a relaciones similares entre el ancho de ruta y los gráficos de intervalo , y entre los gráficos de ancho de árbol y cordales . Una noción más débil de ancho, el ancho de la camarilla , puede ser arbitrariamente grande en los gráficos de indiferencia. [11] Sin embargo, cada subclase propia de los gráficos de indiferencia que se cierra bajo los subgrafos inducidos tiene un ancho de camarilla limitado. [12]
Cada gráfico de indiferencia conectado tiene un camino hamiltoniano . [13] Un gráfico de indiferencia tiene un ciclo hamiltoniano si y solo si está biconectado . [14]
Los gráficos de indiferencia obedecen a la conjetura de reconstrucción : están determinados de forma única por sus subgráficos con vértice eliminado. [15]
