1
$\begingroup$

Dual graph of a plane graph has a standard definition https://en.wikipedia.org/wiki/Dual_graph and an edgeless graph on $n$ vertices is planar. What is the standard dual graph of such a graph?

Update from comments:

It seems like $n$ vertex planar edgeless graph could be interpreted as 'some' (I do not know which would be appropriate) 'product' of $1$ vertex graph where the 'product' might have the interpretation that if the underlying graph is connected then the 'product' is connected. Perhaps for such 'product' graphs one might give special meaning to connectedness where usual connectedness fails thus salvaging some definition of duality?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ The dual of the edgeless graph on 1 vertex is itself. As that Wikipedia article mentions, duals are usually only defined for connected planar graphs (at least, this is required for $(G^{*})^{*} = G$). $\endgroup$
    – Sam Hopkins
    Commented May 21, 2020 at 20:10
  • $\begingroup$ So there is no working definition for edgeless graph on itself? Well take a graph $G_1$ with vertices $u$ and $v$ and an edge and thus its dual has one vertex. So $(G_1^*)^*\neq G_1$ it seems. Since dual of any star graph is also one vertex $(G^*)^*=G$ seems restrictive. I think I miss details. $\endgroup$
    – VS.
    Commented May 21, 2020 at 20:11
  • 1
    $\begingroup$ I don't understand your question. The most reasonable definition of the dual of the edgeless graph on $n$ vertices would be the edgeless graph on $1$ vertex (but then the dual of the dual will not be the primal graph). $\endgroup$
    – Sam Hopkins
    Commented May 21, 2020 at 20:13
  • $\begingroup$ The dual of a star graph (or indeed any tree) is a single vertex with a loop on it for each edge of the original graph. The way in which the loops are arranged in the plane allows the original tree to be recovered. If you don't allow loops in your graphs then planar duality really only makes sense for 2-edge-connected graphs. $\endgroup$
    – lambda
    Commented May 21, 2020 at 20:39
  • $\begingroup$ Building off lambda's comment, the dual of any tree on $n$ vertices will be a graph which has one vertex and $n-1$ loops: what differs from tree to tree is how these loops are embedded in the plane. Indeed, duality makes the most sense for (connected) plane graphs, i.e., graphs with a fixed embedding in the plane. (But, as that Wiki page also mentions, by a theorem of Whitney, if your graph is 3-connected then the embedding, and hence the dual graph, is unique.) $\endgroup$
    – Sam Hopkins
    Commented May 21, 2020 at 21:25

0

Reset to default

You must log in to answer this question.