3
$\begingroup$

(This question actually arose in real life when dealing with status bits with mutual influence.)

Let $G=(V,E)$ be a connected, simple, undirected graph with $|V| \geq 2$. For $v\in V$, let $N_G(v) = \{w\in V: \{v,w\}\in E\}$. A parity map for $G$ is a map $f:V\to {\mathbb Z}/2{\mathbb Z}$ such that for every $v\in V$ we have $$f(v) = \sum_{w\in N_G(v)}f(w).$$ We say a parity function is non-trivial if it is not $0$ everywhere. For example, the complete graphs $K_n$ all have non-trivial parity maps: if $n$ is even, the constant $1$ map is a parity map, and for $n$ odd, pick one vertex, map it to $0$, and map the other points to $1$. Note that for $n\geq 4$ the circle $C_n$ does not have a non-trivial parity map.

Question. Is there for every $n\in \mathbb{N}$ a connected graph $G$ with minimal degree $\delta(G) = n$ such that $G$ has no non-trivial parity maps?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ The statement "for $n\geq 4$ the circle $C_n$ does not have a non-trivial parity map" is false. E.g., for $n=6$, a non-trivial parity map does exist, e.g. (the matrix is meant to represent a circuit, e.g. by reading it clockwise): $\begin{matrix} 1 \quad- & 0\quad- & 1\quad \\ \hspace{-18pt}| & & \hspace{-10pt}|\\ 1\quad- & 0\quad - & 1\quad\end{matrix}$. $\endgroup$
    – Peter Heinig
    Mar 2, 2018 at 10:01
  • 1
    $\begingroup$ If $n$ is even, then the complete bipartite graph $K_{n,n}$ has minimal degree $n$ and does not admit a non-trivial parity map. $\endgroup$
    – Philipp Lampe
    Mar 2, 2018 at 10:24
  • $\begingroup$ For completeness, let me note that, curiously, $n=4$ is the only natural number such that the $n$-circuit $C_n$ does not admit a non-trivial parity map. One can even push this to $n\in\{0,1,2\}$ if one agrees that '$n$-circle'='$n$-vertex 2-regular connected multigraph', then this everything works. (For $n=1$, it's the loop.) The non-trivial parity maps in the cases $n\in\{3\}\cup\{k: k\geq 5\}$ are unique and easy to find. In a sense, you have discovered a characterization of the number $4$: a number $n$ is equal to $4$ iff the 'circle' on $n$ vertices admits a nontrivial parity map. $\endgroup$
    – Peter Heinig
    Mar 2, 2018 at 15:44
  • $\begingroup$ Dear @Dominic van der Zypen: for completeness, and to prevent the (admittedly unlikely) eventuality that a future reader who needs exactly this concept (and does not read up to the comments-section) is misled, I struck out a false statement, leaving it visible, so as to keep a comment meaningful. I hope you agree with this (if MO aspires to be some sort of living reference work, then even small errors should be corrected), but of course, needless to say, you can also delete the statement entirely if you prefer. $\endgroup$
    – Peter Heinig
    Mar 2, 2018 at 15:59
  • $\begingroup$ Thanks @PeterHeinig, sorry for being a bit sloppy! I'll leave the statement as is, as it was my mistake, and if it deleted, the comments pointing to a deleted line of mine might confuse other readers. It was a good idea of yours just to strike the false statement but not delete it $\endgroup$
    – Dominic van der Zypen
    Mar 3, 2018 at 7:49

1 Answer 1

Reset to default
8
$\begingroup$

I think $K_{n,n+1}$ works. Clearly each side must be monochromatic. So the side of odd size must be all $0$. But then the other side must be all $0$.

Improve this answer
$\endgroup$

Your Answer

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

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