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$
0

1 Answer 1

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$
1
  • $\begingroup$ Or p if n is a prime power p^k. $\endgroup$ Commented Mar 4, 2014 at 16:46

You must log in to answer this question.

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