Skip to main content
MathOverflow

Return to Question

For completeness, and to prevent the (admittedly unlikely) eventuality that a future reader who needs exactly this concept and does not read till the comments is misled, I struck out a false statement, leaving it visible, so as to keep a comment meaningful.
Source Link
Peter Heinig
Peter Heinig
  • 6.1k
  • 1
  • 27
  • 47

(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.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?

(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?

(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?

Source Link
Dominic van der Zypen
Dominic van der Zypen
  • 48.9k
  • 8
  • 47
  • 162

Non-trivial parity maps in graphs

(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?