0
$\begingroup$

Suppose we have a weighted directed graph $G=(V,E,f)$. Each $e\in E$ is associated with $f_e\in \mathbb{N}$. There is a source node $s$, which only has outgoing edges, and a sink node $t$, which only has incoming edges.

Consider the automorphism group of $G$, denoted as $A$.

Is there always an integer flow $F$

  1. is a max flow, i.e., the value of the flow equals the min-cut of $G$.

  2. is invariant under the action of any element in $A$.

$\endgroup$

1 Answer 1

1
$\begingroup$

No. Consider the graph with vertices $\{s, a, a', b, t\}$ and edges $\{s\to a, s\to a', a\to b, a'\to b, b\to t\}$. If each edge has weight 1 then the max integer flow is not invariant under the only non-identity automorphism.

$\endgroup$
1
  • $\begingroup$ @Taylor Thank you very much! It is very nice. $\endgroup$
    – gondolf
    Commented Sep 11, 2022 at 13:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .