Sobre conjuntos de separación completa en grafos

Varios tipos diferentes de problemas de identificación ya han sido estudiados en la literatura, donde el objetivo es distinguir cualquier par de vértices de un grafo por sus vecindarios únicos en un conjunto dominante o totalmente dominante del grafo, a menudo denominado código. Para estudiar tales problemas desde un punto de vista unificador, se han proporcionado reformulaciones de los problemas ya estudiados en términos de problemas de cobertura en hipergrafos construidos adecuadamente. Al analizar estas representaciones de hipergrafos, introducimos una nueva propiedad de separación, llamada separación completa, que aún no se ha considerado en la literatura hasta ahora. La estudiamos en combinación con dominación y total-dominación, y llamamos a los códigos resultantes códigos dominantes de separación completa (o códigos FD para abreviar) y códigos totalmente dominantes de separación completa (o códigos FTD para abreviar), respectivamente. Abordamos las condiciones para la existencia de códigos FD y FTD, límites para su tamaño y su relación con códigos de otros tipos. Demostramos que los problemas de determinar un código FD o un código FTD de cardinalidad mínima en un grafo son NP-duros. También mostramos que las cardinalidades de los códigos FD y FTD mínimos difieren en, como máximo, uno, pero que es NP-completo decidir si son iguales para un grafo dado en general. Encontramos los valores exactos de las cardinalidades mínimas de los códigos FD y FTD en algunas clases de grafos familiares como caminos, ciclos, grafo a la mitad y arañas. Esto nos ayuda a comparar los dos códigos con otros códigos en estas familias de grafos, exponiendo casos extremos para varios límites inferiores.