Complejidad espectral de grafos ponderados y no dirigidos.

MAGALY CATANZARITI ; FEDERICO MORANA; DIEGO MATEOS; HUGO AIMAR

Congreso; TREFEMAC 2022; 2022

En este trabajo introducimos un concepto de complejidad para grafos ponderados no dirigidos en términos del análisis espectral del operador Laplaciano. Calculamos la norma del vector de valores propios tanto del grafo como de su complemento y tomamos su producto. De este modo, obtenemos una medida de complejidad que satisface dos propiedades básicas que consideramos de interés. En primer lugar, la complejidad de los grafos totalmente conectados y desconectados es nula. En segundo lugar, la complejidad de grafos complementarios coincide. Esta noción de complejidad nos permite distinguir diferentes tipos de grafos situándose en el plano complejidad vs densidad de conexión. Exploramos desde el punto de vista teórico y experimental la región plana que describe la famila de todos los grafos ponderados y no dirigidos. Por otra parte estudiamos métricas basadas en el espectro que puedan dar una noción de distancia entre grafos. Por último, como aplicación utilizamos diferente tipos de grafos ponderados y no ponderados extraídos de datos reales para estudiar su ubicación en el plano y las diferencias existentes entre ellos.