1
$\begingroup$

Question:

If $G(V,E)$ is a biconnected symmetric graph, is it possible to identify the edges, whose deletion destroys biconnectivity, in the following way:

  • determine the union $B:= ST\cup F_1$ of a spanning tree and a maximal forest, that is edge-disjoint with $ST$
  • determine a second maximal forest $F_2$ that has no edges in common with $B$.
  • take as the critical edges those edges of $B$, that are adjacent to a vertex of degree 2 or connect different trees of $F_2$.
Improve this question
$\endgroup$
3
  • $\begingroup$ I found several counter-examples, but found the flaw in each before posting! So maybe the answer is yes. But why do you suspect this? $\endgroup$
    – Aaron Meyerowitz
    Commented Feb 3, 2020 at 0:58
  • $\begingroup$ @AaronMeyerowitz the idea is essentially based on the observation, that removing any of the essential edges generates cut vertices and that a "pure" cut vertex doesn't harm the connectivity of a tree whereas the removed edges is essential for biconnectivity and separates a pair of trees in $F_2$; that is essentially the basis of the naive idea. $\endgroup$
    – Manfred Weis
    Commented Feb 3, 2020 at 4:11
  • $\begingroup$ I suspect that the sketched reasons also generalize to detecting the edges that are essential for $k$ connectivity, i.e. of any edge, whose deletion destroys $k$ connectivity. $\endgroup$
    – Manfred Weis
    Commented Feb 3, 2020 at 4:25

2 Answers 2

Reset to default
2
$\begingroup$

This seems like a counterexample: take 3 cliques $C_1$, $C_2$ and $C_3$, each on say $5$ vertices. Connect $C_1$ and $C_2$ with three vertex-disjoint edges, and connect $C_2$ and $C_3$ with 2 edges. Now it is possible to choose $ST$ to be a spanning tree going from $C_3$ to $C_2$ to $C_1$ and back to $C_2$, and $F_1$ a disjoint spanning tree going from $C_1$ to $C_2$ to $C_3$, so that the following holds: the remaining graph has three connected components, $F_2$ has a tree in every component, and $B$ connects the trees in $C_1$ and $C_2$. Hence the procedure will return an edge between $C_1$ and $C_2$, which is not critical.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That looks good. But $C_3$ is irrelevant and I am not sure $5$ is enough. $\endgroup$
    – Aaron Meyerowitz
    Commented Feb 3, 2020 at 19:21
  • 1
    $\begingroup$ Without $C_3$ the graph would be 3-connected. And it seemed to work with 5-cliques, but you might as well take larger ones. $\endgroup$
    – smapers
    Commented Feb 3, 2020 at 19:33
1
$\begingroup$

Given a bi-connected graph $G$, say an edge $e$ is destructive if $G-e$ has a cut-vertex. Say that $e$ is $(T,F_1,F_2)$-critical if there is a spanning tree $T$ and forests $F_1,F_2$ as in you description with respect to which $e$ critical.

  1. Must a $(T,F_1,F_2)$-critical edge be destructive? The answer is no. Here is a example based on the answer given by @smapers.

Here is a $14$ point graph with $38$ edges. If desired, add another $4$ edges on the left and $3$ on the right to make each a $K_7$. Either way, there are no destructive edges. The tree $T$ is the green path, The forest $F_1$ is the red tree And $F_2$ consists of two blue paths. Then the central red edge is critical but not destructive.

enter image description here

If one wants $G$ to have some destructive edges and be exactly bi-connected then, as suggested, add some new vertices and edges making a $K_5$, connect it to the $K_7$ on the left two new edges which will become part of $T$ (which will lose an edge elsewhere to avoid a cycle) and then add enough edges to make $F_1$ and $F_2$ valid.

This illustrates:

  1. Do the $(T,F_1,F_2)$-critical edges include all the destructive edges? Again, no. One can certainly arrange to have some of the destructive edges in $T.$

  2. If $e$ is destructive is there some way to choose the tree and forests so that it is critical? Yes. Assign $e$ to $F_1$ with the rest to be determined. Now $G-e$ is connected with a cut-vertex $v$. Start with all the edges on $v$ and extend that to a spanning tree $T$. Now $G-e-T$ is disconnected with the vertices of $e$ in distinct connected components. So $F_2$ will have those two vertices in distinct distinct trees. How ever we form $F_1$ (using $e$ ) and $F_2$, The destructive edge $e$ is critical.

Note that some of the trees in $F_2$ might be isolated vertices.

Improve this answer
$\endgroup$

You must log in to answer this question.

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