{
  "id": "1808.10119",
  "version": "v1",
  "published": "2018-08-30T04:52:55.000Z",
  "updated": "2018-08-30T04:52:55.000Z",
  "title": "A combinatorial property of flows on a cycle",
  "authors": [
    "Zhuo Diao"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper, we prove a combinatorial property of flows on a cycle. $C(V,E)$ is an undirected cycle with two commodities: $\\{s_{1},t_{1}\\}, \\{s_{2},t_{2}\\}$;$r_1>0,r_2>0, \\mathbf r=(r_i)_{i=1,2}$ and $f,f'$ are both feasible flows for $(C,(s_i,t_i)_{i=1,2},\\mathbf r)$. Then $\\exists i\\in\\{1,2\\}, p\\in P_i, f(p)>0, \\forall e\\in p, f(e)\\geq f'(e)$ ; Here for each $i\\in\\{1,2\\}$, let $P_i$ be the set of $s_i$-$t_i$ paths in $C$ and $P=\\cup_{i=1,2}P_i$. This means given a two-commodity instance on a cycle, any two distinct network flow $f$ and $f'$, compared with $f'$, $f$ can't decrease every path's flow amount at the same time. This combinatorial property is a generalization from single-commodity case to two-commodity case, and we also give an instance to illustrate the combinatorial property doesn't hold on for $k-$commodity case when $k\\geq 3$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-08-30T04:52:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "combinatorial property",
      "distinct network flow",
      "two-commodity instance",
      "paths flow",
      "single-commodity case"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}