1
$\begingroup$

Given a simple regular graph of degree $d$ on $n$ vertices.

Assume an ordering of vertices and assume all orientations of edges is from $i$ to $j$ if edges $ij$ exists and $i<j$. Pick $m$ random edges and flip their orientation. For every simple closed path $p$ denote $\sigma(p)$ by difference in number of edges with orientation $i$ to $j$ with $i<j$ and number of edges with orientation $i$ to $j$ with $i>j$.

What is the probability that if we pick a random simple closed path $p$ then $\sigma(p)\bmod 2\equiv0$? How many such simple closed path can we expect?

At least can we tell anything about this when graph is complete?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

If the length of simple closed path $P$ is equal to $l$ , I think $\sigma (p) \equiv 0 (mod2)$ is equivalent with $l \equiv 0 (mod2)$ . If the length of simple closed path $P$ is even , then $\sigma (p)$ is even , and conversely if the length of $P$ is odd , then $\sigma(p)$ is odd. Therefore it's enough to counting all cycles in the graph and all even cycles in the graph. The ratio of two number is wanted probability.

$\endgroup$
1
  • $\begingroup$ I think this is a bad suggestion. $\endgroup$
    – user76479
    Dec 29, 2015 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.