4
$\begingroup$

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 believe I have a proof 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$
  • 1
    $\begingroup$ Is this not just matroid duality? The lattice of connected partitions of $G$ is just the lattice of flats of the matroid of $G$. $\endgroup$ – Sam Hopkins Apr 2 at 22:23
  • $\begingroup$ @SamHopkins Thanks -- I think you are right that matroid duality gives a bijection between the connected partitions of $G$o and unions of cycles in the dual. Is there some matroid theoretic way to discuss the number of connected components? The corank of the union of cycles captures the cycle rank. $\endgroup$ – Lorenzo Apr 4 at 16:59
  • $\begingroup$ Number of connected components should be directly related to rank of the flat, right? (Isn't it just the rank function for the lattice you're talking about?) $\endgroup$ – Sam Hopkins Apr 4 at 17:06
  • $\begingroup$ @SamHopkins Thanks -- yes it is $n - c$, where $n$ is the number of nodes, and $c$ is the number of connected components, at least according to here: en.wikipedia.org/wiki/Graphic_matroid ... so I guess there is a theorem written down somewhere that says something like $n - rank( cl(X)) = corank(cl(X)^c)$ . Possibly in here, which is the wikipedia reference: nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p1_A1b.pdf -- I'll go try to read that now. Thanks a lot for your help! $\endgroup$ – Lorenzo Apr 4 at 17:12

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.