Un apunte sobre valores propios y gráficos asimétricos
Autores: Lotfi, Abdullah; Mowshowitz, Abbe; Dehmer, Matthias
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
Un apunte sobre valores propios y gráficos asimétricos
Categoría
Matemáticas
Subcategoría
Análisis matemático
Palabras clave
Complejidad del grafo
Medidas de entropía
Simetría
Tamaños de órbitas
Grupos de automorfismos
Matriz de adyacencia
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 34
Citaciones: Sin citaciones
Esta nota está destinada como una contribución al estudio de medidas cuantitativas de la complejidad de grafos que utilizan medidas de entropía basadas en simetría. Determinar los tamaños de las órbitas de los grupos de automorfismos de grafos es una parte clave de tales estudios. Aquí nos centramos en un caso extremo donde cada órbita contiene solo un vértice. Una permutación de los vértices de un grafo G es un automorfismo si, y solo si, la matriz de permutación correspondiente conmuta con la matriz de adyacencia de G. Este hecho establece una conexión directa entre la matriz de adyacencia y el grupo de automorfismos. En particular, se sabe que si los autovalores de la matriz de adyacencia de G son todos distintos, cada automorfismo no trivial tiene orden 2. En esta nota, agregamos una condición al caso de autovalores distintos que hace que el grafo sea asimétrico, es decir, reduce el grupo de automorfismos a la identidad sola. Además, demostramos resultados análogos para las matrices de Google y Laplacianas. La condición se utiliza para construir un algoritmo para detectar grafos de identidad, y se dan ejemplos para demostrar que es suficiente, pero no necesario.
Descripción
Esta nota está destinada como una contribución al estudio de medidas cuantitativas de la complejidad de grafos que utilizan medidas de entropía basadas en simetría. Determinar los tamaños de las órbitas de los grupos de automorfismos de grafos es una parte clave de tales estudios. Aquí nos centramos en un caso extremo donde cada órbita contiene solo un vértice. Una permutación de los vértices de un grafo G es un automorfismo si, y solo si, la matriz de permutación correspondiente conmuta con la matriz de adyacencia de G. Este hecho establece una conexión directa entre la matriz de adyacencia y el grupo de automorfismos. En particular, se sabe que si los autovalores de la matriz de adyacencia de G son todos distintos, cada automorfismo no trivial tiene orden 2. En esta nota, agregamos una condición al caso de autovalores distintos que hace que el grafo sea asimétrico, es decir, reduce el grupo de automorfismos a la identidad sola. Además, demostramos resultados análogos para las matrices de Google y Laplacianas. La condición se utiliza para construir un algoritmo para detectar grafos de identidad, y se dan ejemplos para demostrar que es suficiente, pero no necesario.