Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a vague imagination of what the cycle structure of a graph might be - something taking into account the numbers, lengths, Hamiltonianicities, Eulerianicities and whatsoever of cycles of a graph and their quantified interweavings - and there are of course papers and books mentioning the cycle structure of graphs - see Quo vadis, graph theory?, for example - but I cannot find a tangible definition to start with.

Question: What might be a sensible definition of "cycle structure"?

share|improve this question
    
This is very much not a real question as it stands... You surely agree? –  Mariano Suárez-Alvarez Sep 21 '10 at 23:21
    
On the one hand I agree; on the other, I have an answer (written below). –  David Speyer Sep 21 '10 at 23:24
    
If you ask me: of course it is a real question! Should I re-formulate it? It is a matter of fact that the term "cycle structure" is in use, and I am looking for a definition. Maybe I am mislead and it does not make sense to look for such a definition? –  Hans Stricker Sep 21 '10 at 23:27
    
Hans, the text you wrote does not ask anything. What do you want to know? –  Mariano Suárez-Alvarez Sep 21 '10 at 23:28
    
I edited the text, now there is a question. Sorry for that. –  Hans Stricker Sep 21 '10 at 23:37

2 Answers 2

This is a vague question, but here is an attempt at an answer. Let $G$ be a graph, let $E$ be the set of edges of $G$, and let $C \subset 2^E$ be the set of cycles of $G$. Then knowing $C$ is equivalent to the matroid of $G$. Two graphs produce the same matroid if and only if they are related by a sequence of the following moves:

(1) Taking two connected components and gluing them along a single vertex, or undoing the above.

(2) If $G$ has two vertices $u$ and $v$ so that $G \setminus \{ u,v \}$ is disconnected, cutting along those vertices and regluing some of the pieces back with $u$ and $v$ switched.

In particular, if a graph is $3$-connected, then it is determined by its matroid.

So one answer could be "The cycle structure of a graph is its matroid" and, as the above shows, this contains almost as much information as the graph.

share|improve this answer
1  
I'll just comment that I agree that this is what cycle structure of a graph means. Also, the theorem that David mentions was first proven by Whitney. –  Tony Huynh Sep 21 '10 at 23:29
    
This sounds very promising. But if this was a real answer, why isn't my question a real question? –  Hans Stricker Sep 21 '10 at 23:36

Another possible answer is the cycle space of a graph, which is a vector space and so supports the application of many tools from linear algebra.

share|improve this answer
    
Another promising answer! So the "cycle structure" of a graph might be the structure of its cycle space? Why not! –  Hans Stricker Sep 21 '10 at 23:47
2  
Yes, and from the cycle space we can still recover some properties of a graph. For example, MacClane's Theorem says that a graph is planar if and only if its cycle space has a 2-basis (a basis such that every edge is contained in at most 2 basis vectors). –  Tony Huynh Sep 21 '10 at 23:48
    
@Tony: You commented and agreed with both of the answers. Is it obvious that they mean essentially the same? –  Hans Stricker Sep 21 '10 at 23:51
1  
The cycle space is bigger than the cycle matroid if we view both of them as just sets. But since the linear algebraist is allowed to take linear combinations (in this case symmetric differences), he only needs to list a basis for the cycle space in order to represent it. It turns out that he only has to list |E(G)|-|V(G)|+1 cycles. On the other hand the matroid theorist has to list all the cycles, since he is viewing the set of cycles as a matroid –  Tony Huynh Sep 22 '10 at 0:29
1  
Also note that the cycle basis of a graph as defined above is a special case of the 1st homology group of a simplicial complex –  Suresh Venkat Sep 22 '10 at 5:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.