-1
$\begingroup$

I have the following graph with the following problem:

We want to obtain a Hamiltonian cycle by supplying all nodes with 1 unit of flow. Initially the node 1 will send 4 units of flow through one and only one of its edge to the next node. The next node consumes 1 unit of flow and sends the rest through one and only one of its edge to the next node and so on until we arrive back at node 1. Node 1 will then consume the last unit of flow.

The upper bound of flow that you can send through one of the edges going out of node 1 is 4 units and the upper bound of flow that comes back through one of the edge to node 1 is 1 unit. I want to know what would be the upper bound of flow that can be sent on edges that are not connected to node 1.

graph

Improve this question
$\endgroup$
1
$\begingroup$

An upper bound is $3$, more generally $n-1$ for a graph with $n$ nodes.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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