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 2 days ago
  • 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 2 days ago
  • $\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. 2 days ago
  • $\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. 2 days ago
  • $\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. 2 days ago

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.