<p>The cycles of a graph form a vector space with its own <a href="http://en.wikipedia.org/wiki/Cycle_basis">cycle basis</a> of simple cycles.  Is that what you mean?</p>

CC BY-SA 3.0
2014-06-20T02:02:35.317Z
2014-06-20T02:02:35.317Z
Ari Trachtenberg
<p>I am considering one optimization problem who is known to be NP hard in the general setting. </p>

<p>But there is application of this problem on the cylces of graph. This problem involves several sets and in this setting each set is the set of nodes of cycle in connected unidrected graph. And all cycles of connected unidrected graphs are the all sets for this problem. This is quite specific setting for the problem and I wonder whether there can be improvements in this specific setting.</p>

<p>I would like to work out all the details myself but the question is - <strong>is there the general theory of all cycles in grpahs (connected undirected)</strong>. Like - what is the number of cycles, what is the minimum and maximum lenght of them, how much common nodes they can have and so on? Mybe there are connections with group theory - e.g. cycle could be some kind of orbit for a group element (in rude language). Any such information provides the constraint on the initial problem and therefore - the complexity improvements can be possible to achieve in this specific setting.</p>

<p>Google gives a lot about Hamiltonian and similar specific cycles. My question is about all possible cycles in graph.</p>

<p>Any references could be helpful. Any names for the problems and keywords in this are could be appreciated as well. Thanks.</p>

CC BY-SA 3.0
2014-06-19T21:28:19.607Z
I have no idea what a "general theory of all cycles in graphs" would mean.  Can you describe a "general theory of X" for some other X?
Jeffε
CC BY-SA 3.0
2014-06-20T17:02:20.800Z
As I said - I guess that my optimization problem in the undirected graph setting can have improved complexity. To investigate this and prove this it would be nice to know the maximal number of cycles in graph, how the lengths of cycles are distributed and so on. Ari answer about cycle bases seemed promising - it could be great to find some kind of generators from which other cycles can be construced and so on. All those questions forms the theory and it would be nice to have one and to have it ready for applications. But I am not sure whether such theory exists.
TomR
<cc.complexity-theory><graph-theory><graph-algorithms>
What can we say about all cycles in graphs (connected undirected graph)
TomR
# What can we say about all cycles in graphs (connected undirected graph)

(Asked by: username_0 on 2014-06-19)

I am considering one optimization problem who is known to be NP hard in the general setting.

But there is application of this problem on the cylces of graph. This problem involves several sets and in this setting each set is the set of nodes of cycle in connected unidrected graph. And all cycles of connected unidrected graphs are the all sets for this problem. This is quite specific setting for the problem and I wonder whether there can be improvements in this specific setting.

I would like to work out all the details myself but the question is - **is there the general theory of all cycles in grpahs (connected undirected)**. Like - what is the number of cycles, what is the minimum and maximum lenght of them, how much common nodes they can have and so on? Mybe there are connections with group theory - e.g. cycle could be some kind of orbit for a group element (in rude language). Any such information provides the constraint on the initial problem and therefore - the complexity improvements can be possible to achieve in this specific setting.

Google gives a lot about Hamiltonian and similar specific cycles. My question is about all possible cycles in graph.

Any references could be helpful. Any names for the problems and keywords in this are could be appreciated as well. Thanks.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: I have no idea what a "general theory of all cycles in graphs" would mean.  Can you describe a "general theory of X" for some other X?  
> **username_0**: As I said - I guess that my optimization problem in the undirected graph setting can have improved complexity. To investigate this and prove this it would be nice to know the maximal number of cycles in graph, how the lengths of cycles are distributed and so on. Ari answer about cycle bases seemed promising - it could be great to find some kind of generators from which other cycles can be construced and so on. All those questions forms the theory and it would be nice to have one and to have it ready for applications. But I am not sure whether such theory exists.  

---

## 1 answers

### Answer by username_2 on 2014-06-20. Score: 5

The cycles of a graph form a vector space with its own [cycle basis](http://en.wikipedia.org/wiki/Cycle_basis) of simple cycles. Is that what you mean?


---

