Los gráficos con los desplazamientos de las matrices de adyacencia

Question

Vamos a Un y B ser la matriz de adyacencia de dos grafo simple de gráficos. Podemos asignar algunos combinatoria interpretaciones a este par de gráficos si Un y B conmutan?

Answer 1

Me resulta difícil pensar en algo útil. La matriz de adyacencia de un grafo y su complemento conmutan si y sólo si el grafo es regular. Un régimen de asociación es una partición de los bordes en forma de gráficos, cuyas matrices de adyacencia de conmutar (junto con otras condiciones). Hay una gran cantidad de literatura sobre estos, pero no recuerdo nada que relaciona las propiedades de los diferentes gráficos en la partición.

Tenga en cuenta también que una gráfica tiene muchos diferentes matrices de adyacencia en general ($n!/|\mathrm{Aut}(G)|$) y estos pueden o no conmuta con cada uno de los otros. Y algunos de estos pueden conmutan con la matriz de adyacencia de un segundo gráfico, y los otros no.

Answer 2

$AB=BA$ dice que para los vértices $u,v$ hay muchos caminos $u-w-v$$uw\in A$$vw\in B$$uv\in B$$vw\in A$.