Grafos bipartitos balanceados hamiltoniano y conjuntos independientes balanceados | Hamiltonian balanced bipartite graphs and balanced independent sets

Resumen

Sea G un grafo bipartito balanceado de orden 2n, es decir, un grafo con una bipartición en dos conjuntos de vértices independientes cada uno de ellos con n vértices, y mínimo grado, es decir, el menor número de lados incidentes a un vértice, al menos cuatro. Si para cada conjunto independiente balanceado de cuatro vértices, es decir, un conjunto independiente conteniendo dos vértices de cada lado de la bipartición, su número de vecinos es al menos n + 1, entonces G es hamiltoniano.

Palabras clave: Unión de vecindades.

ABSTRACT

Let G be a balanced bipartite graph of order 2n, i.e. a graph with a bipartition into two independent vertex sets of the same cardinality n, and minimum degree, i.e. at least number of edges incidents on a vertex, the least four. If for every balanced independent set of four vertices, i.e. an independent set containing two vertices from each side of the bipartition, the number of neighbors is at least n + 1, then G is Hamiltonian.

Key words: Neighborhood union.