Digrafos localmente transitivos

Abstract

Un grafo simple es un par G=(V,A) donde V es un conjunto no vació de elementos llamados vértices y A es un conjunto de pares ordenados de elementos de V llamados aristas (ordenados o no ordenados). En particular un dígrafo simple, aquí lo llamaremos simplemente dígrafo, es un grafo simple dirigido, es decir las aristas son pares de vértices ordenados. Los dígrafos localmente transitivos son nuestro tema central y calcular específicamente cuantos de estos dígrafos existen para un determinado número de vértices, en la tesis doctoral de la Profesora Sofía Pinzón aparece el cálculo para n=2,3,4, nuestro objetivo es calcularlos para 5 vértices. La condición para que un digrafo sea localmente transitivo es que no contenga alguno de los seis 4-digrafos que aparecen en la figura 4.5, para ello nuestro primer trabajo consistió en encontrar las clases de isomorfismos existen para 5 vértices para lo cual estudiamos el programa Nauty del profesor Brendan McKay de la Universidad de Australia y que es de uso libre y plataforma Unix. Luego por observación clasificamos cuales eran o no localmente transitivos. Un ejemplo de digrafos son los torneos, los cuales se han estudiado ampliamente. La inquietud que nos queda es si es posible encontrar una fórmula como la que existe para los torneos localmente transitivos.