Hamilton Cycles in Digraphs of Unitary Matrices

Abstract

A set $S\subseteq V$ is called an {\em $q^{+}$-set} ({\em $q^{-}$-set}, respectively) if $S$ has at least two vertices and, for every $u\in S$, there exists $v\in S,v\ne u$ such that $N^{+}(u)\cap N^{+}(v)\ne \varnothing$ ($N^{-}(u)\cap N^{-}(v)\ne \varnothing$, respectively). A digraph $D$ is called {\em s-quadrangular} if, for every $q^{+}$-set $S$, we have $|\cup \{N^{+}(u)\cap N^{+}(v):u\ne v,u,v\in S\}|\ge |S|$ and, for every $q^{-}$-set $S$, we have $|\cup \{N^{-}(u)\cap N^{-}(v):u,v\in S)\}\ge |S|$. We conjecture that every strong s-quadrangular digraph has a Hamilton cycle and provide some support for this conjecture.

8 pages