For a $2$-edge-connected simple graph $G$ and a tree $T$ of $G$, let $C_e$ be the unique cycle in $T + e$, $e \in E(G) - E(T)$. Define the set $\mathcal{C}(T) = \{C_e | e \in E(G) - E(T)\}$.

Now given a set of cycles $\mathcal{C}$ of $G$, is it possible to decide if $\mathcal{C}$ = $\mathcal{C}(T)$ for some tree $T$ of $G$?


It is easy to see that the following conditions for $\mathcal{C}$ = $\mathcal{C}(T)$ are necessary :

1) $|\mathcal{C}|$ = $|E(G)| - |V(G)| + 1|$

1') $\cup\mathcal{C} = E(G)$

2) The set $\{e \in E(G)| e \in c_1\cap c_2 \text{ and } c_1,c_2 \in \mathcal{C} \text{ and }c_1 \ne c_2 \}$ is forest of $G$

My question is: Are they also sufficient?

  • 2
    $\begingroup$ This looks easy enough to be a homework question. Any motivation for why you're asking? $\endgroup$ – David Eppstein Nov 28 '13 at 5:02
  • $\begingroup$ It is not a homework, but I should have been more precise(see edit.) I am interested in studying the correspondence between tree and even graphs arising from the symmetric difference of their Fundamental cycles. $\endgroup$ – hbm Nov 28 '13 at 20:55
  • $\begingroup$ Before (2) you should add that every edge is in at least one of the cycles. Another necessary condition is that the intersection of any two cycles is empty or a path; does it follow? $\endgroup$ – Brendan McKay Nov 28 '13 at 21:36

I had a complicated algorithm based on matroid intersection here earlier, but there's a much simpler answer: a cycle basis is fundamental if and only if each cycle includes at least one edge that is not part of any other cycle. And it's easy to see that any collection of cycles with this property is automatically linearly independent. So you can check if a collection of cycles is a fundamental cycle basis by verifying that each has a unique edge and that there are enough cycles to form a basis.

The reference is:

Cribb, D. W.; Ringeisen, R. D.; Shier, D. R. On cycle bases of a graph. Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. I (Baton Rouge, La., 1981). Congr. Numer. 32 (1981), 221–229.

| cite | improve this answer | |
  • $\begingroup$ I am sure I follow. Could you explain? $\endgroup$ – hbm Dec 4 '13 at 1:40
  • $\begingroup$ The subsets of edges that do not include any cycles form the independent sets of a matroid. The subsets of edges that don't include all of the unique edges of some cycle form the independent sets of a different matroid. When you have two matroids on the same elements, you can find the largest set that's independent for both of them, in polynomial time. If this set is a tree, you've solved the problem, and if not there is no solution. $\endgroup$ – David Eppstein Dec 4 '13 at 3:35
  • $\begingroup$ I think you mean "a" largest set; but if one is a tree than they all are. Right? $\endgroup$ – Brendan McKay Dec 4 '13 at 6:11
  • $\begingroup$ Yes, a largest set, and they're all trees iff they all have exactly $n-1$ edges. $\endgroup$ – David Eppstein Dec 4 '13 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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