Un subgráfico generado de un gráfico es otro gráfico formado a partir de un subconjunto de los vértices del gráfico junto con todos los bordes que conectan pares de vértices de ese subconjunto.
Formalmente, sea G = ( V , E ) cualquier gráfico, y sea S ⊂ V un subconjunto de vértices en G . Entonces el subgrafo generado G [ S ] es un grafo cuyos vértices son elementos de S , y cuyas aristas consisten en todas las aristas del conjunto E , cuyos vértices finales pertenecen a S [1] . La misma definición se aplica a grafos no dirigidos , grafos dirigidos e incluso multigrafos .
Un subgrafo generado G [ S ] también puede llamarse un subgrafo generado en G por un conjunto de vértices S o (si el contexto no conduce a ambigüedad) un subgrafo generado de vértices S .
Los tipos importantes de subgrafos son los siguientes:
El problema de isomorfismo de subgrafo generado es un tipo de problema de búsqueda de subgrafo isomorfo en el que el objetivo es probar si un gráfico se puede encontrar como un subgrafo generado de otro gráfico. Debido a que este problema incluye el problema de la camarilla como un caso especial, es NP-completo [4] .