subgrafo de Sachs

En teoría de grafos , un subgrafo de Sachs de un grafo dado es un subgrafo en el que todos los componentes conexos son aristas simples o ciclos . Estos subgrafos reciben su nombre de Horst Sachs , quien los utilizó en una expansión del polinomio característico de la matriz de adyacencia de grafos. ^{[ 1 ]} Una expansión similar utilizando subgrafos de Sachs también es posible para polinomios permanentes de grafos. ^{[ 2 ]} Los subgrafos de Sachs y los polinomios calculados con su ayuda se han aplicado en la teoría química de grafos , ^{[ 3 ]} por ejemplo, como parte de una prueba para la existencia de orbitales no enlazantes en estructuras de hidrocarburos . ^{[ 4 ]}

Un subgrafo de Sachs generador , también llamado factor {1,2}, es un subgrafo de Sachs en el que cada vértice del grafo dado es incidente a una arista del subgrafo. ^{[ 5 ]} La unión de dos emparejamientos perfectos es siempre un subgrafo de Sachs generador bipartito, pero en general los subgrafos de Sachs no se limitan a ser bipartitos. Algunos autores utilizan el término "subgrafo de Sachs" para referirse únicamente a los subgrafos de Sachs generadores. ^{[ 6 ]}