Matriz de adyacencia de un cuadrado de un grafo.

Question

¿Cuál es la relación entre $A(G)$ y $A(G^2)$ ?

Dónde $G^2$ es la plaza de un gráfico $G$ y $A(G^2),A(G)$ sus respectivos matriz de adyacencia .

Answer 1

$G^2$ es el gráfico con el mismo conjunto de vértices que $G$ pero con aristas que conectan vértices con distancia $\leq 2$ en $G$ .

$A(G)$ muestra qué vértices de $G$ tienen una distancia de 1. $A(G^2)$ muestra qué vértices de $G^2$ tienen una distancia de $1$ o una distancia de $\leq 2$ en $G$ .

Así que, $A(G^2) - A(G)$ muestra qué vértices de $G$ tienen una distancia de exactamente 2. Esta diferencia tendría entradas no nulas y no diagonales en los mismos lugares que $[A(G)]^2$ (donde $A_{ij}^{2}$ es el número de paseos de longitud $2$ entre vértices $i$ y $j$ ).