Timeline for What is the cycle structure of a graph?
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 22, 2010 at 5:35 | comment | added | Suresh Venkat | 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 | |
| Sep 22, 2010 at 0:34 | comment | added | Joseph O'Rourke | 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. | |
| Sep 22, 2010 at 0:29 | comment | added | Tony Huynh | 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 | |
| Sep 22, 2010 at 0:20 | comment | added | Hans-Peter Stricker | If the cycle space is larger than the cycle matroid when seen as an OBJECT, seen as WHAT it is smaller than the cycle matroid? (Just want to get the proper context.) | |
| Sep 22, 2010 at 0:10 | comment | added | Tony Huynh | 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. | |
| Sep 21, 2010 at 23:51 | comment | added | Hans-Peter Stricker | @Tony: You commented and agreed with both of the answers. Is it obvious that they mean essentially the same? | |
| Sep 21, 2010 at 23:48 | comment | added | Tony Huynh | 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). | |
| Sep 21, 2010 at 23:47 | comment | added | Hans-Peter Stricker | Another promising answer! So the "cycle structure" of a graph might be the structure of its cycle space? Why not! | |
| Sep 21, 2010 at 23:44 | history | answered | Joseph O'Rourke | CC BY-SA 2.5 |