2
$\begingroup$

Associated to any planar graph $G$ there is another graph called its double graph, denoted by $\mathcal{H}(G)$, defined according to the following rules (see 'Trees and Matchings' section 2, page 3):

  1. Embed $G$ and its dual $G^{\ast}$ simultaneously in the plane in such a way that any vertex $v$ of $G$ should lie inside its dual face $F_{v}^{\ast}$ in $G^{\ast}$ and any two dual edges of $G$ and $G^{\ast}$ intersect exactly once.
  2. Declare all the new edge intersections from step 1 as new vertices and color them in white and all the remaining vertices coming from $G$ and $G^{\ast}$ as black vertices.
  3. Denote the resulting graph $\mathcal{H}(G)$ and notice that by construction is bipartite.

Question: Does the bipartite honeycomb lattice arise as the double graph $\mathcal{H}(G)$ of any other graph $G$?

enter image description here

Note: It is indicated in 'Trees and Matchings' that the double graph construction can be generalized to directed graphs and in this case the bipartite honeycomb lattice appears as the double graph a directed triangular lattice, however, I'm interested in undirected graphs.

$\endgroup$
2
$\begingroup$

No: in the dual graph construction, all the white vertices created have degree $4$, but the honeycomb lattice is $3$-regular.

$\endgroup$
1
  • $\begingroup$ So easy! Thanks a lot for taking the time to answer. $\endgroup$ May 9 '21 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.