Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cycles in a number-theoretic graph

  1. May 9, 2009 #1
    Consider the following graph:

    1.) There are n vertices labeled 1...n.
    2.) There exists an edge between vertices u and v iff label(u) | label(v) (the label of u divides the label of v).

    How many unique simple cycles does such a graph with n vertices contain?

    Note(s):
    The exact function in terms of n may be too hard to get (lol), but growth orders are also acceptable, with appropriate proof.
    The graphs are non-directed graphs... no double-edges are allowed, but self loops are present.
    Cycles may be counted one way or both ways (that is, if 1-2-4-1 is counted as a cycle, then 1-4-2-1 may or may not be counted, as long as you make your counting method explicit).
     
    Last edited: May 9, 2009
  2. jcsd
  3. Jun 18, 2009 #2
    I couldn't get a general case, but a brute force method revealed for n=1 to n=24:

    1: 0
    2: 0
    3: 0
    4: 1
    5: 1
    6: 6
    7: 6
    8: 18
    9: 25
    10: 42
    11: 42
    12: 241
    13: 241
    14: 324
    15: 667
    16: 1602
    17: 1602
    18: 5511
    19: 5511
    20: 21596
    21: 32549
    22: 35434
    23: 35434
    24: 237727

    So, it would seem that the increase from n to n+1 is dependent on the number of factors of n+1, since something like 21 (factors 1, 3, 7) is a smaller percentage increase than 20 (factors 1, 2, 4, 5, 10). And obviously when n+1 is prime, no additional loops are added.

    However, because primes necessarily don't add loops, doesn't that mean that you can't have a mathematical formula for the value at n vertices, since primes aren't mapped to any known function? I guess I'm not sure how you'd go about figuring out a growth order in that case, since it's a little erratic. Anyway, I'm interested to hear your solution (assuming you've got one?)

    [edit]
    So, let's say L(x) is the number of loops, and F(x) is the number of factors of x. It looks like L(x)/L(x-1) <= F(x), except for a few early numbers (6 and 12).
    [/edit]

    DaveE
     
    Last edited: Jun 19, 2009
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Cycles in a number-theoretic graph
  1. Product Life Cycle (Replies: 7)

  2. Hitting for the cycle (Replies: 20)

  3. The Cycling Thread (Replies: 18)

Loading...