- #1

- 492

- 0

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).

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: