I have solved a following problem, the solution seems too simple, so I am suspicious, that I am making a mistake. Would be very greateful, if someone cheked the solution.

So, the problem : do there exist two simple, non isomorphic graphs, which cycle matrices are equal and every edge is contained in some cycle.

The solution : let two graphs be $G_1$ and $G_2$. Their corresponding cycle matrices are $C_1$ and $C_2$. Since they are aqual, let $C_1 = C_2 = C$. Let $A_1$ and $A_2$ be icidence matrices of $G_1$ and $G_2$. From theory it is known that $C \cdot A_1^T = 0$ and $C \cdot A_2^T = 0$. But, then $C \cdot A_1^T = C \cdot A_2^T$ and $A_1^T = A_2^T$ and $A_1 = A_2$. But this means that $G_1$ and $G_2$ are isomorphic. So the answer is no, such graphs do not exist.

Edit : since all matrices contain only values ${0,1}$, multiplication is done in the way, that $0 \cdot 0 = 0$, $1 \cdot 0 = 0$, $0 \cdot 1 = 0$ and $1 \cdot 1 = 1$

About the cycle matrix. Let the graph $G$ have $m$ edges and let $q$ be the number of different cycles in $G$. The cycle matrix $B = [b_{ij}]_{q \times m}$ of $G$ is $(1,0)$ matrix of order $q \times m$ with $b_{ij} = 1$ if the $i$th cycle includes $j$th edge and $b_{ij} = 0$ otherwise.

  • $\begingroup$ First line should be "Hallo, everyone". I have written that way dont know why it doesnt display as it should. $\endgroup$ – Jevgenijs Strigins Nov 17 '13 at 17:27
  • 1
    $\begingroup$ What is the cycle matrix? $\endgroup$ – Jernej Nov 17 '13 at 23:57
  • $\begingroup$ I edited my question with definition of cycle matrix. $\endgroup$ – Jevgenijs Strigins Nov 18 '13 at 7:36
  • $\begingroup$ Title says "isomorphic," body asks for "non-isomorphic". Please edit one or the other. $\endgroup$ – Gerry Myerson Nov 18 '13 at 8:09
  • 1
    $\begingroup$ If $G_1$ is a cycle of length 3, and $G_2$ is a cycle of length 3 together with a 4th vertex (either isolated, or adjacent to one of the vertices in the 3-cycle), then the graphs have the same cycle matrix, but are not isomorphic, right? $\endgroup$ – Gerry Myerson Nov 18 '13 at 8:14

I'm not entirely sure I have the right definition of cycle --- I'm assuming that something like abcadea (where the letters stand for vertices) doesn't count as a cycle, since it decomposes into two cycles, abca and adea. If I have it right, then there are connected counter-examples. Let $G_1$ be three triangles sharing a single vertex. Let $G_2$ also consist of three triangles, with the 1st and 2nd having one common vertex, the 2nd and 3rd having a different common vertex. Each graph has 9 edges forming 3 cycles, and the same cycle matrix $$\pmatrix{1&1&1&0&0&0&0&0&0\cr0&0&0&1&1&1&0&0&0\cr0&0&0&0&0&0&1&1&1\cr}$$ but the graphs are clearly not isomorphic, as only $G_1$ has a vertex of degree 6.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.