¿Esta clase de gráfico tiene un nombre?

Está formulado extendiendo los gráficos de umbral . Dado un gráfico de umbral , donde es la camarilla y es el conjunto independiente, mi extensión es como sigue: Cada vértice puede ser reemplazado por un nuevo clique tal que los vértices de tienen el mismos vecinos de . $(C,I)$ $C$ $I$ $v\in I$ $K_v$ $K_v$ $v$

Supongo que esto debería haberse estudiado, pero es difícil buscarlo en graphclasses.org.

graph-theory graph-classes Yixin Cao
fuente

Parece ser un gráfico de intersección de intervalos anidados ( graphclasses.org/classes/gc_347.html ), pero necesito verificarlo.

Yixin Cao

Respuestas:

$C_4$ $P_4$ $2P_3$ $C_4$ $P_4$ $2K_2$ $C_4$ $P_4$ ) gráficos libres. No creo que tenga nombre; al menos, no parece estar listado en graphclasses.org.

Para ver que esta es la caracterización correcta, considere la representación de gráficos trivialmente perfectos como los cierres transitivos de los bosques enraizados. Un bosque da lugar a un gráfico de umbral (conectado) si y solo si tiene una ruta dirigida que contiene todos los nodos no hoja: agregar un nuevo vértice aislado corresponde, en el bosque, a agregar un nuevo árbol de un solo nodo, que no No cambie esta propiedad, y agregar un nuevo vértice conectado a todos los demás corresponde a agregar una nueva raíz conectada a todas las raíces del árbol anteriores, lo que nuevamente no cambia esta propiedad (la nueva raíz puede ser parte de la ruta) .

$2P_3$

$2K_2$ $P_4$ $2P_3$

David Eppstein
fuente

2 P_{3}

$2 P_3$

(C_{4}, P_{4})

$(C_4,P_4)$

2 P_{3}

$2P_3$

(2 P_{3}, C_{4}, P_{4})

$(2P_3,C_4,P_4)$