Let $G=(V,E)$ be an $n$-vertex simple undirected graph. A *signing* of the graph is a function $s:E \to \{1,-1\}$, and $(G,s)$ is a *signed graph*. That is, we label each edge of the graph with $1$ or $-1$. The sign function, defined on edges, can be naturally extended to paths; the sign of a path is the product of the signs of the edges on the path. A path is said to be *balanced* if its sign is $1$. In other words, the path has an even number of $-1$-labelled edges.

The signed graph $(G,s)$ is said to be *balanced* if every *closed path*^{1} is balanced, and is called imbalanced otherwise. For instance, the trivial signing where we label each edge by $1$ is clearly a balanced signed graph. However, there are non-trivial signings that can be balanced too; for example, a bipartite graph where all edges are labeled $-1$.

There is much literature on balanced signed graphs and ways to balance them. However, I am curious about the polar opposite: 'horribly imbalanced graphs', say (though this notion, too, is a different kind of 'balance'). Let us call a graph 'horribly imbalanced' if half the closed paths are balanced. This is a more global notion of 'balance', graded by cycle lengths. More precisely, define:

A signed graph $(G,s)$ is said to be 'horribly imbalanced' if for every $k$, exactly half the number of closed paths of length $k$ are labeled $1$.

Now it is possible that the total number of closed paths of length $k$ is odd, so maybe exactly 'half the number' is hoping for too much. This looks related to discrepancy theory, so lets say the avg label of closed walks of length $k$ is $0$, with some error. My questions:

Is such a notion meaningful?

Has it been studied anywhere already?

Let's assume, for simplicity, that the graph is $d$-regular. Then is there some bound on the margin of error, in terms of $n$, $k$ and $d$?

Given a regular graph, can we appropriately sign the edges so that the resulting signed graph becomes horribly imbalanced this way?

I must mention that I did post a slightly modified version of this question on stackexchange here https://math.stackexchange.com/questions/2345021/imbalance-in-a-signed-graph

Based on some offline feedback, maybe it is a better fit here. I did flag and contact the mods to inform them of the cross-post, but I apologize in advance if I am missing any etiquette and will rectify it if pointed out.

^{1} _{'closed path'='graph-theoretic cycle'='circuit'='2-regular subgraph'}

only iffor each $k\in\omega$, the number of $k$-circuits is even. Yes, this is a frighteningly restrictive necessary condition, yet trivially such graphs exist. $\endgroup$ – Peter Heinig Sep 2 '17 at 11:05