3
$\begingroup$

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"?

Improve this question
$\endgroup$
6
  • $\begingroup$ This is very much not a real question as it stands... You surely agree? $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Sep 21, 2010 at 23:21
  • $\begingroup$ On the one hand I agree; on the other, I have an answer (written below). $\endgroup$
    – David E Speyer
    Commented Sep 21, 2010 at 23:24
  • $\begingroup$ 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? $\endgroup$
    – Hans-Peter Stricker
    Commented Sep 21, 2010 at 23:27
  • $\begingroup$ Hans, the text you wrote does not ask anything. What do you want to know? $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Sep 21, 2010 at 23:28
  • 1
    $\begingroup$ Hans: one might point out that finding good structures that capture this information (aside from the ones mentioned below) is in some sense a meta-goal in algebraic graph theory. $\endgroup$
    – dvitek
    Commented Sep 22, 2010 at 3:21

2 Answers 2

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Commented Sep 21, 2010 at 23:29
  • $\begingroup$ This sounds very promising. But if this was a real answer, why isn't my question a real question? $\endgroup$
    – Hans-Peter Stricker
    Commented Sep 21, 2010 at 23:36
4
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • 3
    $\begingroup$ 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). $\endgroup$
    – Tony Huynh
    Commented Sep 21, 2010 at 23:48
  • 1
    $\begingroup$ I suppose that I have a split personality. They don't actually mean the same thing. It is a matter of perspective. As an object, the cycle space is technically larger than the cycle matroid since the former contains all Eulerian subgraphs, while the later only contains cycles (circuits). Of course, we can represent the cycle space compactly by just listing the fundamental cycles of the graph. So in another sense the cycle space is smaller than the cycle matroid. $\endgroup$
    – Tony Huynh
    Commented Sep 22, 2010 at 0:10
  • 2
    $\begingroup$ 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 $\endgroup$
    – Tony Huynh
    Commented Sep 22, 2010 at 0:29
  • 1
    $\begingroup$ I just wanted to mention as an aside that, as far as I know, it is an open problem to find a polynomial-time algorithm to construct a minimum weight integral cycle basis in a directed graph. Such "best bases" have application to event scheduling, so they are of considerable interest. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 22, 2010 at 0:34
  • 2
    $\begingroup$ 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 $\endgroup$
    – Suresh Venkat
    Commented Sep 22, 2010 at 5:35

You must log in to answer this question.

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