Vulnerabilidad del diámetro de ciertas familias de grafos

Abstract

En este trabajo hemos realizado un estudio completo sobre la vulnerabilidad del diámetro de dos familias de grafos:<br/><br/>Los grafos impares y los n-cubo plegados. En el caso de los grafos impares, hemos probado que la eliminación de cualquier conjunto de vértices o ramas de cardinalidad k menor que el grado incrementa el diámetro de los subgrafos resultantes a lo sumo en dos unidades.<br/><br/>Asimismo, hemos estudiado como varían los parámetros d'k y d'k' cuando eliminamos k vértices o ramas del grafo.<br/><br/>Análogamente, para los grafos cubo plegado hemos estudiado como varían estos parámetros cuando eliminamos k vértices o ramas del grafo, para valores de k inferiores al grado del grafo. Por los resultados obtenidos podemos afirmar que ambas familias de grafos son adecuadas para la implementación de redes de interconexión tolerantes a fallos.<br/><br/>Otro estudio que hemos realizado en esta tesis trata sobre el diseño de redes densas fiables. Y hemos obtenido cuatro grafos (A,D,D,1) que mejoran cinco cotas presentadas en la tabla de grandes grafos (A,D,D,1).