¿Cuándo la matriz de adyacencia o incidencia de un grafo tiene la propiedad de los consecutivos?

Question

Dado un grafo, ¿cuáles son algunas condiciones suficientes (y necesarias) para saber si su matriz de adyacencia tiene la propiedad de los consecutivos?

¿Pregunta similar para su matriz de incidencia?

Tenga en cuenta que un $\{0,1\}$ -Se dice que una matriz con valores tiene la propiedad de los consecutivos, si existe una permutación de columnas tal que los unos de cada fila de la matriz resultante son consecutivos. También se pueden intercambiar los papeles de las filas y las columnas en la definición.

Gracias y saludos.

Answer 1

Propuesta. La matriz de adyacencia de un grafo $\Gamma$ tiene la propiedad de los tonos consecutivos si y sólo si

1. $\Gamma$ es un árbol, o

2. cada ciclo inducido de $\Gamma$ es un $4$ -ciclo.

Esta respuesta es un trabajo en progreso, ya que estoy atascado en el caso de 4 ciclos de la inversa.

$\Rightarrow$ :

Una inducción $n$ -el ciclo tiene vértices $0,\ldots, n-1$ con $i$ incidente a $j$ si y sólo si $j=i\pm 1$ tomando los índices módulo $n$ . Así que en la matriz de adyacencia, tenemos $$A_{i,i+1}=A_{i,i-1}=A_{i+1,i}=A_{i-1,i}=1$$ para cada $i$ y todas las demás entradas $0$ .

Supongamos que $\sigma$ es la permutación de $\{1,\ldots,n\}$ dando lugar a una disposición consecutiva de $A$ . Para tener ambos $1$ en una fila junto a otros $1$ en esa columna, necesitamos que $\sigma(i)=\sigma(i+2)\mp 1=\sigma(i-2)\pm 1$ . Sin embargo, a menos que $n=4$ no podemos hacer tal biyección sin dejar alguna columna con $n-2$ ceros que separan un par de $1$ 's. Sin embargo, si $n=4$ , $$A^\sigma=\left(\begin{array}{cccc}1&0&1&0\\1&0&1&0\\0&1&0&1\\0&1&0&1\end{array}\right)$$ es un arreglo consecutivo admisible.