3
$\begingroup$

Are $m^2 \times m^2$ Rook graphs compact? Below is an (unsuccessful) attempt to show that a Rook graph with 2 self loops on each vertex, $(Rook + 2I)$, is compact.

Complete graphs with a self loop at each vertex, $K_m^*$, are compact [Brualdi, "Applications of Doubly Stochastic Matrices", pg. 91].

Let $A=I \otimes J$ be the adjacency matrix of the vertex-disjoint union of $m$ complete graphs $K_m^*$. Then $A$ is compact [Brualdi, "App. of Dbly Stoch. Mat.", Corollary 3.7, pg. 93].

Graphs isomorphic to a compact graph are compact.

Let $B=J \otimes I$. Then $B$ is compact since it is isomorphic to $A$ via a $m^2 \times m^2$ permutation matrix $P$ that swaps zero-based rows $(j*m+i)$ and $(i*m+j)$ for $0 \leq i, j \leq (m-1)$.

Then $Rook2 = C = A+B = (I \otimes J) + (J \otimes I)$.

Since $A$ and $B$ are compact, it is straight forward to show that $Aut(A) \cap Aut(B) = \{P_C \otimes P_R \}$ where $P_C$ and $P_R$ are $m \times m$ permutation matrices.

What remains is to show that other doubly stochastic matrices $W$ that commute with $C$ are a composed from $\{ P\times (P_C \otimes P_R), (P_C \otimes P_R) \times P \}$, the isomorphic permutations between $A$ and $B$.

This is where I'm getting stuck. Expanding $WC = CW$ and doing some arithmetic gymnastics says the automorphisms fit the constraints on $W$ but I have not been able to rule out everything else.

Any help is appreciated (or if it has already been done, a pointer to a reference).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.