logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro