Grafos Particulares

Grafo Nulo

En este grafo los vértices que lo componen so estás conectados, esto es, que son vértices aislados, se puede decir también, que es un grafo trivial que no tiene vértices ni aristas.

Grafo Vacío

Es aquel grafo que no tienen aristas.

Grafo Trivial 

Es un grafo trivial es un grafo con 0 aristas, y 0 ó 1 vértices. Los grafo triviales son grafos completos: a aquel que no posee vértices se le llama grafo nulo, mientras que al que posee un vértice, se le conoce como grafo singleton.

Grafo Simple

Es aquel grafo que no posee bucles o lazos. Se puede decir también, que un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Un grafo que no es simple se denomina multigrafo.

Grafo Completo

Un grafo completo es un grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas. Se puede hacer referencia que un grafo completo de n vértices tiene  aristas, y se nota . Es un grafo regular con todos sus vértices de grado . La única forma de hacer que un grafo completo se torne disconexo a través de la eliminación de vértices, sería eliminándolos todos.

Ejemplos

Los grafos completos de 1 a 12 nodos son los siguientes:

Grafos Bipartito o Completo

 Es aquel grafo bipartito en el que todos los vértices de la partición  están conectados a todos los vértices de la partición  y viceversa.

  

En otras palabras, Un grafo bipartito completo  es un grafo bipartito tal que  Es decir, un grafo bipartito completo está formado por dos conjuntos dis-conjuntos de vértices y todas las posibles aristas que unen esos vértices.

El grafo completo bipartito con particiones de tamaño  y  es denotado como .

Ejemplos

Grafo Plano

Es aquel que puede ser dibujado en el plano cartesiano sin cruce de aristas. Todo grafo plano puede ser dibujado sobre la esfera, y viceversa.

Grafo Rueda

 Es un grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1).

Se puede decir también, que un grafo rueda (W_n), o simplemente rueda, es un grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1).

Los grafos rueda son grafos planos, y como tales pueden ser "incrustado" en un plano. Más específicamente, todo gráfico rueda es un grafo de Halin. Son auto-duales: el dual de cualquier grafo rueda es un grafo isomórfico.

Grafo Perfecto

Es aquel que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo.