0
$\begingroup$

What is the right definition to generalise the following observations?

1. $1$-connectivity induces a partition of graph vertices into $1$-connected components

2. $2$-connectivity induces a partition of graph edges into $2$-connected components

3. $2$-edge-connectivity induces a partition of graph vertices into $2$-edge-connected components


Two possibilities:

  • An edge is a relation between vertices, so consider relations between edges
  • An edge is a relation between $2$ vertices, so consider relations between $3$ vertices

However, neither of these more general concepts is directly present in the original graph. Is there some set of virtual objects implicitly defined by the graph, for which there is a natural equivalence relation?

$\endgroup$
  • $\begingroup$ Do you mean edges or vertices in 2? $\endgroup$ – PrudiiArca Feb 14 at 8:38
  • 1
    $\begingroup$ I don’t understand your question. $k$-connected components define an equivalence class with respect to the corresponding membership relation on vertices. Moreover $k$-connected implies $k$-edge-connected (if I recall correctly), so this membership relation extends to edges. What is your question about? $\endgroup$ – PrudiiArca Feb 14 at 8:45
  • $\begingroup$ @PrudiiArca I meant edges in $2$, because the same vertex could be a member of multiple $2$-connected components. And the same edge could be a member of multiple $3$-connected components. Could you explain how the $k$-connected components define equivalence classes? Will there not be significant overlap? I think the answer to that might answer the original question. $\endgroup$ – D. G. Feb 14 at 10:21
  • $\begingroup$ @PrudiiArca Actually I think I may have found the answer. $k$-edge-connectivity is the easier case, partitioning graph vertices into $k$-edge-connected components. $k$-vertex-connectivity partitions the $K_k$ subgraphs into $k$-vertex-connected components. $\endgroup$ – D. G. Feb 14 at 10:51
  • $\begingroup$ @PrudiiArca Unfortunately it's not true, because a $k$-vertex-connected graph can be $K_k$-free, for example $K_{5,5}$ is $3$-connected but $K_3$-free. Therefore although the $K_k$ subgraphs will be partitioned, the $k$-vertex-connected components cannot be reconstructed from the partition. $\endgroup$ – D. G. Feb 15 at 1:18

Your Answer

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

Browse other questions tagged or ask your own question.