Unigraph

Un unigrafo o grafo unigráfico es un grafo que, salvo isomorfismo definido por su secuencia de grados , es isomorfo entre sí. En otras palabras, si dos grafos cualesquiera con la misma secuencia de grados son isomorfos entre sí, entonces son (representaciones de) el mismo unigrafo. La secuencia de grados correspondiente se denomina unigráfica . ^{[ 1 ] [ 2 ]}

Para grafos sin etiquetar, es natural operar con secuencias de grados ordenadas en orden descendente o ascendente. ^{[ 1 ]}

Las propiedades de las secuencias unigráficas fueron estudiadas a mediados de la década de 1970 por Kleitman y otros. ^{[ 1 ]} En 1975, Kleitman y Li proporcionaron un algoritmo para reconocer la unigraphicidad en tiempo lineal. ^{[ 3 ]}

Es fácil comprobar que todos los grafos con menos de cinco vértices son unigrafos. Un ejemplo de par no unigráfico con 5 vértices es el grafo camino con 5 vértices y la unión de los grafos completos de 3 y 2 vértices , ambos con la secuencia de grados (2,2,2,1,1). ^{[ 2 ]}

Una serie de artículos de Regina Tyshkevich y su estudiante, Arkady Chernyak, describieron la caracterización completa de los unigrafos, la cual se resumió en su artículo de 2000. ^{[ 1 ]} La caracterización se realiza en términos de lo que ahora se denomina "descomposición de Tyshkevich". ^{[ 2 ] [ 4 ]}