Let's consider a cubic bipartite graph $G$ with a $3$-edge coloring (label the colors $-1,0,1$) and further, paths $p\in P$ on $G$ without backtracking of length $|p|$, that return to the origin.

The adjacency matrix $A$ of $G$ can be split in three due to the edge coloring: $$ A=A_{-1}+A_0+A_1 $$ Starting from a initial vertex $v_0$, paths without backtracking can be written as a sequence of subsequent matrix multiplication of $A_k$ with $k\in\{-1,0,1\}$ and $A_mA_l\neq A^2_m$, e.g.: $$ A_0A_1A_0A_{-1} ... A_1A_0v_0 $$ and if we think of $A_kv_0$ being an initial edge, we recognize that our non-backtracking path, will necessarily continue with an edge $A_{k{\color{red} \pm} 1 \bmod 3}$. So we finally store our path in a sequence $^p\Delta$ of $(|p|-1)$ "${\color{red} \pm} $"'s., e.g. $(+,...,+,+,-)$. All possible paths $p$ have a correponding sequence $^p\Delta$.

I already found two things:

  1. If a path $p$ is returning, the path $q$, with $^{q}\Delta=-\left(^{p^{-1}}\Delta\right)$ which is the sign-inverted, position-reversed sequence is also returning, which also holds true for cycles.

  2. For simple cycles (not a concatenation of several ones), I think I found that $\displaystyle\sum_{k=1}^{|p|-1} ({^p\Delta}) _k\bmod 3 \neq 0$, which does not hold for other returning paths, like cycles with a tail.

Two examples:

  1. a $4$-cycle with a sequence of coloured adajacency matrices $A_1A_0A_{-1}A_0$ results in $^p\Delta=\left(0-1,-1-0,0-(-1)\right)=(-,-,+)$, which sums up to $1 \bmod 3$.

  2. a $6$-cycle with a sequence of coloured adajacency matrices $A_1A_0A_{-1}A_1A_0A_{-1}$ results in $^p\Delta=(-,-,-,-,-)$, which sums up to $-1 \bmod 3$.

Are there criteria for $^p\Delta$ to identify as well concatenated cycles in the set of paths that return to the origin?

Also other criteria for simple cycles are welcome...


1 Answer 1


Another thing to note (related to point 2) is that the sum is always equivalent to $1 \bmod 2$ for returning paths. So then, you have that the sum is always $\pm 1 \bmod 6$ for simple cycles.


Since the graph is bipartite, any returning path $p$ must contain an even number of edges. This means that we have an odd number of elements in the sequence ${^p}\Delta$. If we take the sum of the $p-1$ elements in the sequence modulo 2, we get $(p-1) \times 1 \equiv 1$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .