3
$\begingroup$

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

EDIT:

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ This looks easy enough to be a homework question. Any motivation for why you're asking? $\endgroup$
    – David Eppstein
    Commented Nov 28, 2013 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
    Commented Nov 28, 2013 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
    Commented Nov 28, 2013 at 21:36

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I am sure I follow. Could you explain? $\endgroup$
    – hbm
    Commented Dec 4, 2013 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
    Commented Dec 4, 2013 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
    Commented Dec 4, 2013 at 6:11
  • $\begingroup$ Yes, a largest set, and they're all trees iff they all have exactly $n-1$ edges. $\endgroup$
    – David Eppstein
    Commented Dec 4, 2013 at 7:30

You must log in to answer this question.

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