0
$\begingroup$

I've also asked this question on Mathoverflow, but it hasn't gotten an answer after several months: https://mathoverflow.net/questions/316132/reference-on-generalization-of-plane-graph-duality-between-bonds-and-simple-cycl

Let $G$ be a plane graph, and $G^*$ its dual. Among the $k$ partitions of the nodes of $G$, I'll call the connected k-partitions those such that each block of nodes of the partition induces a connected subgraph of $G$.

It is well known that the connected 2-partitions of the vertices $G$ are dual to the simple cycles of $G^*$. (The duality is by sending the partition to the cut edges of that partition. This is also called the bond / simple cycle duality.)

I can prove (it is not hard, unless I made a mistake) that the connected $k$-partitions of the vertices of $G$ are dual to the set of edge subgraphs $K$ of $G^*$ with

  • $H_1(K)$ is of rank $k - 1$
  • Each connected component $K$ is $2$ edge connected.

Again, the duality is by sending a partition to the cut edges in that partition. In the other direction, it comes by taking the connected components of $G$ after removing the edges crossing the subgraph $K$.

I use this result in the course of some other proof, and I'm looking for a reference for it (as this seems like the kind of thing that is either wrong, or well known).

$\endgroup$

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.