El problema de reconstrucción de las gráficas de fichas.

Abstract: Sea $G$ una gráfica simple de orden $n\ge 2$ y $k$ un entero tal que $n>k\ge 1$. La \emph{gráfica de $k$-fichas $F_k(G)$ de $G$} es la gráfica cuyos vértices son todos los $k$-conjuntos de vértices de $G$, y donde dos $k$-conjuntos son adyacentes si su diferencia simétrica es un par de vértices adyacentes en $G$. Las gráficas de fichas han sido definidas cuatro veces, de manera independiente, desde 1988, y tienen relación con otras gráficas bien conocidas, tales como las gráficas de Johnson y las gráficas de Johnson duplicadas. En las últimas dos décadas se han descubierto varias aplicaciones de las gráficas de fichas, por ejemplo, en Teoría de Códigos y Mecánica Cuántica; además, se han utilizado para estudiar el Problema de Isomorfismo en gráficas.

El problema de reconstrucción de las gráficas de fichas puede enunciarse como sigue: “Dada una gráfica $F$ isomorfa a $F_k(G)$, para alguna gráfica $G$, determinar si $G$ es única (salvo isomorfismos), y de ser así, construir una gráfica isomorfa a $G$”. En esta plática hablaremos de algunas propiedades de las gráficas de fichas y sus antecedentes. Además ,hablaremos del problema de reconstrucción de las gráficas de fichas y las familias de gráficas conocidas que pueden reconstruirse a partir de sus gráficas de fichas.

Posted on Sep 10, 2021 in Seminario de Grafos, Seminars