5
$\begingroup$

I've stumbled across this family of flow networks, and posted the sequence of maximal flows to OEIS: A238729. I can't find any reference to it either. Has anyone seen it?

Here is the description: Consider the network whose nodes are the divisors of n, with an edge from a to b if and only if b/a is a prime factor of n, in which case the capacity of the edge is b/a. The source of this network is 1 and the sink is n. For n >=2 the sequence of maximal flows, {F(n)} starts out 2, 3, 2, 5, 4, 7, 2, 3, 4, 11, 4, 13, 4, 6, 2, 17, 5, 19, 4, 6, 4, 23, 4, 5, 4, 3, 4, 29, 8, 31, 2, 6, 4, 10, 5, 37, 4, 6, 4, 41, 8, 43, 4, 6, 4, 47, 4, 7, 6

I have a general formula for F.

$\endgroup$
1
$\begingroup$

As a service to the community, here are these digraphs in sage:

def divisor_graph(n):
    """
    Mathoverflow 159319
    """
    vert = divisors(n)
    return DiGraph([(a, b, b / a) for b in vert
                    for a in divisors(b) if is_prime(b//a)])

One trivial remark is that the capacity is $n$ if $n$ is prime.

$\endgroup$
  • $\begingroup$ Or p if n is a prime power p^k. $\endgroup$ – The Masked Avenger Mar 4 '14 at 16:46

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.