En algunos problemas de enumeración gráfica, se considera que los vértices del gráfico están etiquetados de tal manera que se pueden distinguir entre sí, mientras que en otros problemas se considera que cualquier permutación de los vértices forma el mismo gráfico, por lo que los vértices se consideran idénticos o sin etiquetar . En general, los problemas etiquetados tienden a ser más fáciles. [5] Al igual que con la enumeración combinatoria en general, el teorema de enumeración de Pólya es una herramienta importante para reducir problemas no etiquetados a problemas etiquetados: cada clase no etiquetada se considera como una clase de simetría de objetos etiquetados.
El número de orugas de n vértices sin etiquetar es [11]
Base de datos de gráficos
Varios grupos de investigación han proporcionado una base de datos con capacidad de búsqueda que enumera gráficos con ciertas propiedades de tamaño pequeño. Por ejemplo
^ Cameron, Peter J. (2004), "Automorfismos de gráficos", en Beineke, Lowell W.; Wilson, Robin J. (eds.), Temas de teoría de grafos algebraicos , Enciclopedia de matemáticas y sus aplicaciones, vol. 102, Cambridge University Press, págs. 137-155, ISBN0-521-80197-4
^ Harary y Palmer, pag. 3.
^ Harary y Palmer, pag. 5.
^ Harary y Palmer, pag. 7.
^ Harary, Frank ; Schwenk, Allen J. (1973), "El número de orugas" (PDF) , Matemáticas discretas , 6 (4): 359–365, doi :10.1016/0012-365x(73)90067-8, hdl : 2027.42/33977.