1
$\begingroup$

I read that the XOR of basis cycles can generate all the cycles present in the graph.

I was just wondering if there exists any one vertex which is present in all the basis cycles and is present in all the cycles of the graph.

Can someone point me to something that might help me tackle this problem?

$\endgroup$
3
$\begingroup$

Consider the following graph:

counterexample 1

Let $S$ be the set containing the cycles formed by i) the red and black edges, and ii) the blue and black edges. $S$ is a cycle basis in which every cycle contains vertex $x$, yet the cycle formed by the red and blue edges does not contain $x$.


Edit: it is also not true that the existence of a vertex $x$ that lies in all cycles of a cycle basis implies that $x$ belongs to all cycles of the graph. See the following counterexample:

counterexample 2

The $3$ cycles that can be formed by taking an edge $e$ of color $c$ for $c \in \{ \mbox{red, green, blue}\}$ along with the two black edges incident to the endpoints of $e$ form a basis $S$. Vertex $x$ belongs to all the cycles in $S$ but it does not belong to the cycle formed by the red, green, and blue edges.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I get your point. I've edited the question a bit. All 3 points along the middle line exist in both the basis cycles and 2 of them (the extreme ones) exist in all the cycles as well. Now will the condition hold ? $\endgroup$ – asds_asds Nov 6 '19 at 21:05
  • 1
    $\begingroup$ Your new property is clearly false as you're asking for a vertex that is (1) in all basis cycles, (2) in all cycles of the graph. (2) Implies (1) so your condition is equivalent to only (2). In any case (1) alone is false: there might not be any vertex that is present in all basis cycles. Think of a graph consisting of two disconnected triangles. (If you want a connected graph then simply add a vertex between two arbitrary vertices in different components) $\endgroup$ – Steven Nov 6 '19 at 21:10
  • $\begingroup$ In the case of the two triangles with a vertex connecting them, there isn't any vertex that occurs in both the basis cycles , so I can say that there is no vertex that is common to all the cycles. However if in a connected graph (1) holds true then (2) will always be true? $\endgroup$ – asds_asds Nov 6 '19 at 22:12
  • 1
    $\begingroup$ I added another counterexample to my answer. $\endgroup$ – Steven Nov 6 '19 at 22:52
  • $\begingroup$ Is there any way to locate a point which is present in all the cycles of a graph? I thought that the fundamental cycles approach would do it but now it seems wrong. The graph is always connected. $\endgroup$ – asds_asds Nov 6 '19 at 22:58

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.