En teoría de grafos, un isomorfismo de grafos es una biyección de los vértices de un grafo sobre otro, de modo que se preserva la adyacencia de los vértices. Más formalmente, el isomorfismo entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices que preserva la relación de adyacencia.1 Es decir, cualquier par de vértices ...
El estudio de dominancia en grafos se basa en la noción de que un vértice domina a todos aquellos vértices adyacentes con el. El número de dominancia de un grafo se define entonces como el mínimo número de vértices necesario para dominar todos los vértices del grafo. Diversas variantes de este concepto han sido introducidas y ampliamente...
El número de estabilidad de un grafo es el tamaño del conjunto independiente más grande que se puede encontrar en el grafo. En otras palabras, corresponde al número máximo de vértices que pueden formar un conjunto independiente (un conjunto de vértices en el que ningún par de vértices está conectado por una arista).
Calcular el número de...
El número cromático de una gráfica G es la menor cantidad de colores necesarios para colorear sus vértices sin que dos vértices vecinos (unidos por una arista) tengan el mismo color. O más formalmente, es el menor entero m tal que G es más coloreable (o bien, tiene una coloración propia con m colores). A este número se le denota...
En teoría de grafos, un clique (o «una clique», pronunciado /klik/), a veces traducido desde el inglés como clan[nota 1] o camarilla,[2] C, en un grafo no dirigido G = (V, E) es un conjunto de vértices, C ⊆ V, tal que todo par de vértices distintos son adyacentes, es decir, existe una arista que los conecta. En otras palabras,...
En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del grafo. De manera simple, una coloración de los vértices de un grafo tal que ningún vértice adyacente comparta el mismo color es llamado vértice coloración.