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).

Improve this question
$\endgroup$
4
  • 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
    Commented Apr 2, 2019 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$
    – Elle Najt
    Commented Apr 4, 2019 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
    Commented Apr 4, 2019 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$
    – Elle Najt
    Commented Apr 4, 2019 at 17:12

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .