Caminos y Ciclos Hamiltonianos en Grafos Bipartitos Balanceados

Abstract

Sea G = (X ∪ Y,E) un grafo bipartito balanceado simple de orden 2n. G es hamilton conectado si por cada dos vértices uno a cada lado de la bipartición existe un camino hamiltoniano que los conecta. El orden de un ciclo C, es el número de vértices del ciclo, c(G) denota el orden del ciclo de máxima longitud en el grafo. En este trabajo, establecemos condiciones para que el grafo G sea hamiltoniano o hamilton conectado, en función de algunos parametros, tales como: la conectividad, el orden del ciclo maximo, cardinalidad de unión de vecindades y mínimo grado de un vértice.