2
$\begingroup$

A $\textit{signed graph}$ is a graph $G$ whose edges are signed either $+$ or $-$. A cycle is $\textit{positive}$ if the product of its edge signs is positive, i.e., it has an even number of negatively signed edges. Otherwise, the cycle is $\textit{negative}$.

So here's an interesting problem I came up with: Consider a signed complete graph $K_n$, where $n\geq 3$. If all cycles of length $k$ are positive, then every cycle in $K_n$ is positive.

I think it's true when at least one edge of $K_n$ is positive ($K_n$ could have all negative edges and $k$ could be even) because I can't find a counterexample! I've been trying to prove it by the contrapositive: If there exists a negative cycle in $K_n$ then there exists a cycle of length $k$ that is negative in $K_n$. I was trying induction on the contrapositive and was able to knock out several cases with the inductive hypothesis. I am trying to solve the case where the negative cycle is of length $n+1$ and I can't find a way to guarantee that you can find a cycle of length $k$. Any ideas??

$\endgroup$
2
$\begingroup$

For a $K_n$ graph to only have positive cycles, it must consist either of all positive edges or of two all-positive-edge subgraphs, $K_{m}$ and $K_{n-m}, 0<m<n$, joined exclusively by negative links. (Note that $K_1$ as one of the subgraphs is an option - of course this has zero edges). Any other arrangement allows a negative 3-cycle.

However your assertion will fail on an all-negative-edge $K_n$ if you choose an even $k$, so you might need to specify that $k$ is odd - then I think you can probably prove it from the above description by first showing that an all-negative graph is not allowed, then assuming a positive link somewhere and building out from there.

$\endgroup$
  • $\begingroup$ Thank you. Yes, I should exclude the case where all edges of $K_n$ are negative. $\endgroup$ – Sarah Feb 5 '15 at 17:11
  • $\begingroup$ @Sarah - yes, I see you have updated; for the sake of the proof you can also assume there is a negative edge somewhere. I'd be interested to see how far your inductive proof has proceeded. $\endgroup$ – Joffan Feb 5 '15 at 17:28

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.