# Daisy cubes as resonance graphs and maximal independent sets of trees

###### Abstract

Assume that $G$ is a homeomorphically peripheral color alternating graph with
inner dual $G^{*}$ and resonance graph $R(G)$. We first establish a bijection
between the set of maximal hypercubes of the resonance graph $R(G)$ and the
set of maximal independent sets of the inner dual $G^{*}$, where $G^{*}$ is a
tree and isomorphic to the $\tau$-graph of $R(G)$. A novel characterization on
when resonance graphs are daisy cubes follows naturally. Furthermore, the
proof of the characterization provides a binary code labelling for the vertex
set of a resonance graph $R(G)$ as a daisy cube with respect to the set of
maximal independent sets of the inner dual $G^{*}$ of $G$. We then show that a
daisy cube with at least one edge is a resonance graph of a plane bipartite
graph if and only if its $\tau$-graph is a forest. As applications of our main
theorems, interesting results are obtained for Fibonacci cubes and Lucas cubes
which are special types of daisy cubes. Structure properties are also provided
for daisy cubes whose $\tau$-graphs are trees and have at most five maximal
hypercubes. We conclude the paper with two algorithms which provide a binary
code labelling for the vertex set of a resonance graph as a daisy cube.

_keywords_ : daisy cube, (homeomorphically) peripheral color alternating
graph, plane (weakly) elementary bipartite graph, resonance graph,
$\tau$-graph

Simon Brezovnika,b, Zhongyuan Chec, Niko Tratnikb,d,
Petra Žigert Pleteršekd,e

a University of Ljubljana, Faculty of Mechanical Engineering, Slovenia

b Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

c Department of Mathematics, Penn State University, Beaver Campus, Monaca, USA

d University of Maribor, Faculty of Natural Sciences and Mathematics, Slovenia

e University of Maribor, Faculty of Chemistry and Chemical Engineering,
Slovenia

<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
##  1 Introduction

Resonance graphs, also termed as $Z$-transformation graphs, depict the
relationships between perfect matchings, also known as Kekulé structures in
chemistry. Originating separately from the works of chemists [12, 9, 10] and
mathematicians [27], these graphs were initially focused on benzenoid graphs
but later expanded to include plane bipartite graphs [17, 28, 31, 32]. This
extension broadened the applicability of the concept. Research on resonance
graphs of benzenoid graphs involving hypercubes is documented in several
sources such as [18, 19, 21], while structural aspects of resonance graphs of
plane bipartite graphs are summarized in a survey paper [25].

Daisy cubes were introduced in [14] as a subfamily of partial cubes which
contains Fibonacci cubes and Lucas cubes. Recent advancements, including
characterizations and embeddings of daisy cubes, are discussed in [20, 23].
The association between Fibonacci cubes and resonance graphs was investigated
in [15, 29].

The linkage between resonance graphs and daisy cubes was initially explored in
[33], revealing that the resonance graph of a kinky benzenoid graph is a daisy
cube. Moreover, characterizations of catacondensed even ring systems and
2-connected outerplane bipartite graphs whose resonance graphs are daisy cubes
were provided in [2] and [3], respectively. Recently, we characterized all
plane bipartite graphs whose resonance graphs are daisy cubes [1]. In
particular, we showed that if $G$ is a plane elementary bipartite graph other
than $K_{2}$, then its resonance graph $R(G)$ is a daisy cube if and only if
the Fries number of $G$ equals the number of finite faces of $G$, which in
turn is equivalent to $G$ being homeomorphically peripheral color alternating.
Furthermore, we proved that a resonance graph $R(G)$ of a plane bipartite
graph $G$ is a daisy cube if and only if $G$ is weakly elementary and every
elementary component of $G$ other than $K_{2}$ is homeomorphically peripheral
color alternating.

This paper is a further development of our recent work [1] described above.
For a homeomorphically peripheral color alternating graph $G$, we first
provide a bijection between the set of maximal hypercubes of its resonance
graph $R(G)$ and the set of maximal independent sets of the inner dual $G^{*}$
of $G$, which is a highlight built on a sequence of related bijections. This
allows us to provide our first main theorem that the resonance graph $R(G)$ of
a plane elementary bipartite graph $G$ is a daisy cube if and only if there is
a bijection between the set of maximal hypercubes of $R(G)$ and the set of
maximal independent sets of the inner dual $G^{*}$ of $G$, where $G^{*}$ is a
tree isomorphic to the $\tau$-graph $R(G)^{\tau}$ of $R(G)$. The proof for the
sufficiency of the above main result provides a binary code labelling for the
vertex set of a resonance graph as a daisy cube. We then prove that daisy
cubes with isomorphic $\tau$-graphs are isomorphic. This leads to our second
main theorem that a daisy cube with at least one edge is a resonance graph of
a plane bipartite graph if and only if its $\tau$-graph is a forest. As
applications of our main theorems, we explore special types of daisy cubes,
namely Fibonacci cubes and Lucas cubes, and obtain some interesting results.
Structure properties are also provided for a daisy cube whose $\tau$-graph is
a tree and have at most five maximal hypercubes. Finally, we write two
algorithms which input a sequence of associated finite faces with respect to a
reducible face decomposition of a homeomorphically peripheral color
alternating graph $G$, and output a binary code labelling for all perfect
matchings of $G$ forming the vertex set of its resonance graph $R(G)$ as a
daisy cube.

##  2 Preliminaries

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. A set of
pairwise nonadjacent vertices of a $G$ is called an independent set. Moreover,
a maximal independent set of $G$ is an independent set that is not a proper
subset of any other independent set of $G$. The disjoint union of graphs
$G_{1}$ and $G_{2}$, denoted as $G_{1}\cup G_{2}$, is the graph whose vertex
set is a disjoint union of $V(G_{1})$ and $V(G_{2})$, and edge set is a
disjoint union of $E(G_{1})$ and $E(G_{2})$. A subgraph of $G$ induced by a
vertex subset $X\subseteq V(G)$ is denoted as $\langle X\rangle$.

A Cartesian product $\Box_{i=1}^{n}G_{i}$ of $n$ graphs $G_{1},G_{2},\ldots
G_{n}$ is a graph whose vertex set is $V(G_{1})\times
V(G_{2})\times\cdots\times V(G_{n})$ and two vertices $(x_{1},\ldots,x_{n})$
and $(y_{1},\ldots,y_{n})$ are adjacent in $\Box_{i=1}^{n}G_{i}$ if there
exists an $i\in\\{1,\ldots,n\\}$ such that $x_{i}y_{i}$ is an edge of $G_{i}$,
and $x_{j}=y_{j}$ for any $j\in\\{1,\ldots,n\\}\setminus\\{i\\}$. An
$n$-dimensional hypercube $Q_{n}$ is a Cartesian product
$\Box_{i=1}^{n}K_{2}$, while $Q_{0}$ is a one-vertex graph.

Let $(\mathcal{B}^{n},\leq)$ be a poset on the set of all binary codes of
length $n\geq 1$ with the partial order $u_{1}u_{2}\ldots u_{n}\leq
v_{1}v_{2}\ldots v_{n}$ if $u_{i}\leq v_{i}$ for all $1\leq i\leq n$. A daisy
cube generated by $X\subseteq\mathcal{B}^{n}$ is an induced subgraph of
$Q_{n}$, defined by $Q_{n}(X)=\langle\\{u\in\mathcal{B}^{n}\ |\ u\leq
x\textrm{ for some }x\in X\\}\rangle$. It is known [14] that daisy cubes are
partial cubes, that is, isometric subgraphs of hypercubes. Moreover, if
$\widehat{X}$ is the anti-chain consisting of the maximal elements of the
poset $(X,\leq)$, then $Q_{n}(X)=Q_{n}(\widehat{X})$. If $G$ is a daisy cube
and $\mathcal{P}(V(G))$ is the power set of $V(G)$, then an operator
$o:\mathcal{P}(V(G))\rightarrow\mathcal{P}(V(G))$ can be defined with
$o(X)=\\{u\in V(G)\mid u\leq v\text{ for some }v\in X\\}$ for any $X\subseteq
V(G)$. An induced subgraph $H$ of $G$ is called a $\leq$-subgraph of $G$ if
$V(H)=o(V(H))$.

Let $H$ be a nonempty isometric subgraph of $G$. Take disjoint copies of $G$
and $H_{1}=H$ and connect every vertex of $H$ in $G$ with the corresponding
vertex of $H_{1}$. Then we obtain a graph which is called a peripheral
expansion of $G$ with respect to $H$, which is denoted by $\textrm{pe}(G;H)$.
Moreover, if $H$ is a convex subgraph of $G$, then the expansion is called a
convex expansion of $G$ with respect to $H$. Assume that $G$ is a daisy cube
and $H$ is a $\leq$-subgraph of $G$. Then the peripheral expansion
$\textrm{pe}(G;H)$ is called the $\leq$-expansion of $G$ with respect to $H$.
A connected graph is a daisy cube if and only if it can be obtained from the
one-vertex graph by a sequence of $\leq$-expansions [20].

Fibonacci cubes and Lucas cubes are special types of daisy cubes. For each
$n\geq 1$, a Fibonacci cube $\Gamma_{n}$ is a graph whose vertex set is the
set of all binary codes of length $n$ without consecutive 1’s, and two
vertices are adjacent in $\Gamma_{n}$ if they differ in exactly one position.
A Lucas cube $\Lambda_{n}$ is the induced subgraph of the Fibonacci cube
$\Gamma_{n}$ such that the vertex set of $\Lambda_{n}$ consists of all binary
codes of length $n$ without consecutive 1’s and also without 1 in the first
and the last positions.

A perfect matching of a graph $G$ is a set $M\subseteq E(G)$ of vertex
disjoint edges such that every vertex of $G$ is incident to an edge from $M$.
A path (or, a cycle) of $G$ is called $M$-alternating if its edges are in and
out of $M$ alternately. Moreover, a path (or, a cycle) of $G$ is called
$(M_{1},M_{2})$-alternating if its edges are contained in $M_{1}$ and $M_{2}$
alternately for distinct perfect matchings $M_{1}$ and $M_{2}$ of $G$. A path
$P$ of $G$ is called a handle if $P$ has exactly two end vertices with degree
larger than 2 in $G$ [6]. A handle with more than one edge is called
nontrivial. It is clear that any nontrivial handle of $G$ is $M$-alternating
for any perfect matching $M$ of $G$. A subgraph $H$ of a graph $G$ is said to
be nice if the induced subgraph $G-V(H)$ has a perfect matching.

Assume that $G$ is a plane graph. A face $s$ of $G$ is a region enclosed by a
set of edges of $G$, which forms the periphery of $s$, denoted by $\partial
s$. A face $s$ of $G$ is called finite if the periphery of $s$ encloses a
finite region, and infinite otherwise. The periphery of the infinite face is
called the periphery of $G$. A face $f$ of $G$ is called $M$-resonant if the
periphery of $f$ is an $M$-alternating cycle for a perfect matching $M$ of
$G$, and $f$ is called $(M_{1},M_{2})$-resonant if its periphery is an
$(M_{1},M_{2})$-alternating cycle for two different perfect matching $M_{1}$
and $M_{2}$ of $G$. The inner dual of $G$, denoted by $G^{*}$, is a graph
whose vertices are finite faces of $G$ such that two distinct finite faces are
adjacent in $G^{*}$ if they have an edge in common. Vertices (respectively,
edges) on the periphery of $G$ are called peripheral and the remaining
vertices (respectively, edges) are interior vertices (respectively, interior
edges) of $G$. A handle of $G$ is called a peripheral handle if all of its
edges are peripheral edges of $G$, and an interior handle if all of its edges
are interior edges of $G$. A plane graph whose all vertices are on the
periphery of the graph is called an outerplane graph.

Let $G$ be a plane bipartite graph with a perfect matching. A set $S$ of
finite faces of $G$ is called an alternating set of $G$ if there exists a
perfect matching $M$ of $G$ such that each face in $S$ is $M$-resonant. The
Fries number of $G$ is the maximum of the cardinalities of all the alternating
sets of $G$. An alternating set whose cardinality is the Fries number is
called a maximum cardinality alternating set of $G$. In addition, if all faces
in an alternating set $S$ are pairwise vertex disjoint, then $S$ is called a
resonant set of $G$. Moreover, a resonant set of $G$ is called maximal if it
is not contained in any other resonant set of $G$. For simplicity, we use
$G-S$ to represent the induced subgraph of $G$ obtained by removing all
vertices from a set $S$ of finite faces of $G$. It is easy to see that if $S$
is an alternating set of $G$, then the induced subgraph $G-S$ is either empty
or has a perfect matching. Furthermore, a resonant set $S$ of $G$ satisfying
$G-S$ is empty or has a unique perfect matching is called a canonical resonant
set.

The resonance graph (also called $Z$-transformation graph) $R(G)$ of a plane
bipartite graph $G$ is the graph whose vertices are the perfect matchings of
$G$, and two perfect matchings $M_{1},M_{2}$ are adjacent if their symmetric
difference $M_{1}\oplus M_{2}$ forms the edge set of exactly one cycle that is
the periphery of a finite face $s$ of $G$ [32], and the edge $M_{1}M_{2}$ is
said to have the face-label $s$. By definitions, we can see that if $G$ is a
disjoint union of plane bipartite graphs $G_{1},G_{2},\ldots,G_{m}$ with
perfect matchings, then its resonance graph $R(G)$ is the Cartesian product
$\Box_{i=1}^{m}R(G_{i})$.

An edge of a graph with a perfect matching is called allowed if it is
contained in a perfect matching of the graph, and forbidden otherwise. A graph
is said to be elementary if all its allowed edges form a connected subgraph.
For a graph with a perfect matching, each component of its subgraph obtained
by removing all forbidden edges is elementary. It was shown that a bipartite
graph $G$ is elementary if and only if it is connected and each edge of $G$ is
allowed [16]. In addition, a connected plane bipartite graph with more than
two vertices is elementary if and only if the periphery of each face
(including the infinite face) is an alternating cycle with respect to some
perfect matching of the graph [31]. A face $s$ of a plane graph $G$ is said to
be a forcing face of $G$ if the induced subgraph of $G$ obtained by deleting
all vertices of $s$ is either empty or has a unique perfect matching. By [6],
any 2-connected plane bipartite graph with a forcing face is elementary. The
concept of a plane weakly elementary bipartite graph was first introduced in
[31] for connected graphs. It is more practical to extend the concept to
include non-connected graphs too (for example, see [32]). A plane bipartite
graph (not necessarily connected) is called weakly elementary if deleting all
forbidden edges does not produce any new finite face. By definition, any plane
elementary bipartite graph is also weakly elementary. Note that all allowed
edges of a plane weakly elementary bipartite graph $G$ form elementary
components of $G$, and each elementary component of $G$ different from $K_{2}$
is called nontrivial.

For a plane bipartite graph $G$ with a perfect matching, its resonance graph
$R(G)$ is connected if and only if $G$ is weakly elementary [32]. A benzenoid
system is a 2-connected subgraph of the hexagonal lattice such that every
finite face is a hexagon. It is well known that every benzenoid system with a
perfect matching is weakly elementary [25].

We now present the concept of a reducible face decomposition of a plane
elementary bipartite graph with $n$ finite faces introduced in [31], which is
built on a bipartite ear decomposition of an elementary bipartite graph [16].
Starting from an edge $e$, join its two end vertices by a path $P_{1}$ of odd
length to obtain an even cycle $G_{1}$, proceed inductively to build a
sequence of plane bipartite graphs $G_{i}$ for $2\leq i\leq n$ where $G_{n}=G$
as follows. If $G_{i-1}=e+P_{1}+\ldots+P_{i-1}$ has already been constructed,
then $G_{i}=G_{i-1}+P_{i}$ can be obtained by adding the $i$th path $P_{i}$ of
odd length. A bipartite ear decomposition of a plane elementary bipartite
graph $G$ is called a reducible face decomposition (shortly RFD) if $G_{1}$ is
a periphery of a finite face $s_{1}$ of $G$, and the $i$th ear $P_{i}$ lies in
the exterior of $G_{i-1}$ such that $P_{i}$ and a part of the periphery of
$G_{i-1}$ surround a finite face $s_{i}$ of $G$ for all
$i\in\\{2,\ldots,n\\}$. For such a decomposition, we use notation
$\textrm{RFD}(G_{1},G_{2},\ldots,G_{n})$, where $G_{n}=G$. It was shown [31]
that a plane bipartite graph other than $K_{2}$ is elementary if and only if
it has a reducible face decomposition starting from any finite face of the
graph.

Assume that $G$ is a plane bipartite graph whose vertices are properly colored
black and white such that adjacent vertices receive different colors. Let $M$
be a perfect matching of $G$. An $M$-alternating cycle $C$ of $G$ is
$M$-proper (resp., $M$-improper) if every edge of $C$ belonging to $M$ goes
from white to black vertex (resp., from black to white vertex) along the
clockwise orientation of $C$. A plane bipartite graph $G$ with a perfect
matching has a unique perfect matching $M_{\hat{0}}$ (resp., $M_{\hat{1}}$)
such that $G$ has no proper $M_{\hat{0}}$-alternating cycles (resp., no
improper $M_{\hat{1}}$-alternating cycles) [30]. If $G$ is a plane (weakly)
elementary bipartite graph, then there is a finite distributive lattice
structure on the set $\mathcal{M}(G)$ of all perfect matchings of $G$ [17],
and the $height(\mathcal{M}(G))$ is the distance between $M_{\hat{0}}$ and
$M_{\hat{1}}$ in the resonance graph $R(G)$ [28].

Next, we recall two new concepts introduced in [1]. A 2-connected outerplane
bipartite graph $G$ is called peripheral color alternating if any vertex of
$G$ has degree at most 3, and vertices of $G$ can be properly colored black
and white such that vertices with degree 3 (if exist) are alternately black
and white along the clockwise orientation of the periphery of $G$. A plane
elementary bipartite graph $G$ other than $K_{2}$ is called homeomorphically
peripheral color alternating if $G$ is peripheral color alternating, or any
vertex of $G$ has degree at most 3 and $G$ can be transformed into a
peripheral color alternating graph $G^{\prime}$ by smoothing out degree-2
vertices to replace each interior nontrivial odd length handle $P$ of $G$ with
end vertices $u,v$ by an interior edge; and if $uv$ is also a peripheral edge
of $G$, then by performing edge subdivisions to replace the peripheral edge
$uv$ by a peripheral nontrivial odd length handle. See Figure 1.

Figure 1:  A homeomorphically peripheral color alternating graph $G$ that is
transformed into a peripheral color alternating graph $G^{\prime}$.

###### Theorem 2.1

[1] Let $G$ be a plane elementary bipartite graph other than $K_{2}$. Then the
following statements are equivalent.

$(i)$ The resonance graph $R(G)$ is a daisy cube.

$(ii)$ The Fries number of $G$ equals the number of finite faces of $G$.

$(iii)$ $G$ has a perfect matching $M_{A}$ such that all finite faces of $G$
are $M_{A}$-resonant.

$(iv)$ $G$ is homeomorphically peripheral color alternating.

Zhang, Ou, and Yao [29] showed that any Fibonacci cube $\Gamma_{n}$ is not the
Cartesian product of nontrivial graphs and for a plane bipartite graph
$G^{\prime}$, the resonance graph $R(G^{\prime})$ is a Fibonacci cube
$\Gamma_{n}$ if and only if $G^{\prime}$ is weakly elementary and with exactly
one elementary component $G$ which has a reducible face decomposition
$G_{i}(1\leq i\leq n)$, associated with finite faces $s_{i}(1\leq i\leq n)$
and the odd length paths $P_{i}(2\leq i\leq n)$, where $P_{i}$ starts at
$u_{i}$ and ends at $w_{i}$ along the clockwise orientation of $G_{i}$ for
$2\leq i\leq n$ such that $u_{i}$ of $P_{i}$ and $u_{i+1}$ of $P_{i+1}$ are in
different colors, and two end vertices $u_{i+1}$ and $w_{i+1}$ of $P_{i+1}$
are internal vertices of $P_{i}$ for $2\leq i\leq n-1$. Observe that this is
equivalent to $G$ being homeomorphically peripheral color alternating such
that inner dual $G^{*}$ is a path on $n$ vertices.

Djoković-Winkler relation (briefly, relation $\Theta$) plays an important role
in the study of partial cubes. Two edges $x_{1}x_{2}$ and $y_{1}y_{2}$ of a
connected graph $G$ are in relation $\Theta$ if
$d_{G}(x_{1},y_{1})+d_{G}(x_{2},y_{2})\neq
d_{G}(x_{1},y_{2})+d_{G}(x_{2},y_{1})$. The relation $\Theta$ is an
equivalence relation on the edge set of any partial cube, see [8].

Let $H$ be a partial cube. The $\tau$-graph $H^{\tau}$ of $H$ is a graph whose
vertex set is the set of $\Theta$-classes of $H$, and two distinct
$\Theta$-classes $E$ and $F$ are adjacent in $H^{\tau}$ if $H$ has two edges
$e\in E$ and $f\in F$ such that $e$ and $f$ form a convex path on three
vertices, that is, $e=uv$, $f=vw$, and $v$ is the only common neighbor of $u$
and $w$ [13]. Note that the $\tau$-graph ${R(G)}^{\tau}$ of a resonance graph
$R(G)$ is equivalent to the terminology the induced graph $\Theta(R(G))$
defined in [4] as a graph whose vertex set is the set of $\Theta$-classes of
$R(G)$, and two vertices $E$ and $F$ of $\Theta(R(G))$ are adjacent if $R(G)$
has two incident edges $e\in E$ and $f\in F$ such that $e$ and $f$ are not
contained in a common 4-cycle of $R(G)$, where $G$ is a plane bipartite graph.
For clarity and consistence, we will use notation $\tau$-graph ${R(G)}^{\tau}$
introduced in [13].

##  3 When resonance graphs are daisy cubes

We start from a relation between resonant sets of a plane weakly elementary
bipartite graph and hypercubes of its resonance graph. This generalizes the
main result Theorem 2 in [18] from a benzenoid graph with a perfect matching
to any plane weakly elementary bipartite graph.

###### Lemma 3.1

Assume that $G$ is a plane weakly elementary bipartite graph other than
$K_{2}$. Let $\mathcal{H}(R(G))$ be the set of nontrivial hypercubes of $R(G)$
and $\mathcal{RS}(G)$ be the set of nonempty resonant sets of $G$. Define
$f:\mathcal{H}(R(G))\rightarrow\mathcal{RS}(G)$ such that if $Q$ is a
$k$-dimensional hypercube of $R(G)$ for a positive integer $k$, then
$f(Q)=S_{Q}$, where $S_{Q}$ is a cardinality $k$ resonant set of $G$ with the
property that each finite face in $S_{Q}$ is a face-label of a $\Theta$-class
of $Q$. Then $f$ is well-defined and surjective. Moreover, $f$ is a bijection
only when $\mathcal{RS}(G)$ is a set of canonical resonant sets of $G$.

Proof. It is well known [29] that for a plane weakly elementary bipartite
graph $G$, antipodal edges of a 4-cycle in $R(G)$ have the same face-label,
and face-labels of two incident edges of a 4-cycle in $R(G)$ are vertex-
disjoint faces of $G$. It follows that the edge set of any $k$-dimensional
hypercube $Q$ of $R(G)$ consists of $k$ $\Theta$-classes such that each
$\Theta$-class has a face-label, and the set of face-labels for the
$\Theta$-classes of $Q$ corresponds to $k$ vertex-disjoint finite faces of
$G$. The above fact allows us to show that $f$ is well-defined and surjective,
similarly to the proof of Theorem 2 in [18], while more concisely as follows.

If $Q$ is a $k$-dimensional hypercube of $R(G)$, then the set of finite faces
corresponding to face-labels of $\Theta$-classes of $Q$ is a cardinality $k$
resonant set $S_{Q}$ of $G$. Hence, the image of $Q$ under the mapping $f$ is
the resonant set $S_{Q}$, so $f$ is well-defined.

To see that $f$ is surjective, let $S$ be a cardinality $k$ resonant set of
$G$. Then $S$ has $2^{k}$ perfect matchings because each of peripheral cycles
of $k$ finite faces in $S$ has two perfect matchings. Assume that
$S=\\{s_{1},s_{2},\ldots,s_{k}\\}$. Then we can label each perfect matching of
$S$ as a binary string $b_{1}b_{2}\ldots b_{k}$ of length $k$ such that
$b_{i}=0$ if each edge contained in the perfect matching and on the periphery
of the finite face $s_{i}$ goes from a white vertex to a black vertex along
the clockwise orientation, and $b_{i}=1$ otherwise. Then $\\{b_{1}b_{2}\ldots
b_{k}\mid b_{i}=0,1\\}$ induces a $k$-dimensional hypercube $Q_{S}$ such that
any edge has two end vertices differing in exactly one position $i$ and
corresponding to the face-label $s_{i}$ for some $1\leq i\leq k$. Assume that
$m_{G-S}$ is the number of perfect matchings of $G-S$. Then each perfect
matching of $G-S$ can be extended to $2^{k}$ perfect matchings of $G$, which
induce a $k$-dimensional hypercube $Q_{S}[j]$ of $R(G)$ such that the set of
face-labels of $\Theta$-classes of $Q_{S}[j]$ is $S$. Hence, for each
cardinality $k$ resonant $S$ of $G$, there is a set
$\mathcal{H}_{S}=\\{Q_{S}[1],Q_{S}[2],\ldots,Q_{S}[m_{G-S}]\\}$ of
$k$-dimensional hypercubes of $R(G)$ with the property that for each hypercube
$Q_{S}[j]$ in $\mathcal{H}_{S}$, $S$ is the set of face-labels of
$\Theta$-classes of $Q_{S}[j]$. It follows that the inverse image of a
cardinality $k$ resonant set $S$ of $G$ under the mapping $f$ is a set
$\mathcal{H}_{S}$ of $k$-dimensional hypercubes of $R(G)$.

Moreover, $\mathcal{H}_{S}$ contains a unique $k$-dimensional hypercube of
$R(G)$ only when $S$ is a canonical resonant set of $G$. Otherwise,
$\mathcal{H}_{S}$ contains as many $k$-dimensional hypercubes of $R(G)$ as the
number of perfect matchings of $G-S$. $\Box$

We have shown in [1] that for a plane elementary bipartite graph $G$ other
than $K_{2}$, $R(G)$ is a daisy cube if and only if $G$ is homeomorphically
peripheral color alternating. By definition, if $G$ is homeomorphically
peripheral color alternating, then the induced subgraph of $G$ obtained by
removing vertices on the periphery of $G$ is either empty or has a unique
perfect matching, and so the infinite face of $G$ is forcing. By [6], any
2-connected plane bipartite graph with a forcing face is elementary. We next
consider plane elementary bipartite graphs whose infinite face is forcing.

###### Lemma 3.2

Let $G$ be a plane elementary bipartite graph other than $K_{2}$. Then the
infinite face of $G$ is forcing if and only if any two vertex disjoint cycles
$C_{1}$ and $C_{2}$ such that $C_{1}\cup C_{2}$ is a nice subgraph of $G$ have
disjoint interiors.

Proof. Sufficiency. Assume that any two disjoint cycles $C_{1}$ and $C_{2}$
such that $C_{1}\cup C_{2}$ is a nice subgraph of $G$ have disjoint interiors.
Suppose that the infinite face of $G$ is not forcing. Let $\partial G$ be the
periphery of $G$. Then the resulted subgraph $G^{\prime}$ obtained by deleting
all vertices on $\partial G$ has at least two perfect matchings $m_{1}$ and
$m_{2}$. It is well known that the symmetric difference of $m_{1}$ and $m_{2}$
is a set $S$ of vertex disjoint $(m_{1},m_{2})$-alternating cycles contained
in $G^{\prime}$. Let $M_{1}$ (respectively, $M_{2}$) be a perfect matching of
$G$ extended from $m_{1}$ (respectively, $m_{2}$) such that $\partial G$ is
$(M_{1},M_{2})$-alternating. Then $S$ is also a set of vertex disjoint
$(M_{1},M_{2})$-alternating cycles. Let $C$ be a cycle from $S$. Then the
union of $C$ and $\partial G$ is a nice subgraph of $G$, since both $C$ and
$\partial G$ are $(M_{1},M_{2})$-alternating. However, the interiors of $C$
and $\partial G$ are not disjoint since the former is contained in the latter,
which is a contradiction.

Necessity. Assume that the infinite face of $G$ is forcing. Suppose that there
are two vertex disjoint cycles $C_{1}$ and $C_{2}$ such that the union
$C_{1}\cup C_{2}$ is a nice subgraph of $G$ while their interiors are not
disjoint, it is possible that one of $C_{1}$ and $C_{2}$ is $\partial G$. Then
$G$ has a perfect matching $M$ such that $C_{1}$ and $C_{2}$ are
$M$-alternating. Without loss of generality, we can assume that $C_{1}$ is
contained in the interior of $C_{2}$. By Corollary 3.4 in [31], there exists
an finite face $s_{1}$ of $G$ contained in the interior of $C_{1}$ such that
$s_{1}$ is $M$-resonant and vertex disjoint from $C_{2}$. For $i=1,2$, let
$I[C_{i}]$ denote the subgraph of $G$ consisting of $C_{i}$ together with its
interior. By Theorem 2.9 in [31], each $I[C_{i}]$ for $i=1,2$ is elementary.
Assume that $I[C_{1}]$ contains $n_{1}$ finite faces and $I[C_{2}]$ contains
$n_{2}$ finite faces. Then finite faces of $I[C_{1}]$ are also finite faces of
$I[C_{2}]$ and so $n_{1}<n_{2}$. We can construct a reducible face
decomposition $G_{1},\ldots G_{n_{1}},G_{n_{1}+1},\ldots
G_{n_{2}},G_{n_{2}+1}\ldots,G_{n}(=G)$ of $G$ starting from $s_{1}$ with a
sequence of associated finite faces $s_{1},\ldots s_{n_{1}},s_{n_{1}+1},\ldots
s_{n_{2}},s_{n_{2}+1},\ldots s_{n}$ such that $I[C_{1}]$ has the reducible
face decomposition starting from $s_{1}$ with a sequence of associated finite
faces $s_{1},\ldots s_{n_{1}}$, and $I[C_{2}]$ has a reducible face
decomposition starting from $s_{1}$ with a sequence of associated finite faces
$s_{1},\ldots s_{n_{1}},s_{n_{1}+1},\ldots s_{n_{2}}$. Then by the proof of
Theorem 2 in [5], $height(\mathcal{M}(G_{1}))=1$, and for $2\leq i\leq n$,
$height(\mathcal{M}(G_{i}))\geq height(\mathcal{M}(G_{i-1}))+1$ and the
equality holds if and only if $R(G_{i})$ can be obtained from $R(G_{i-1})$ by
a peripheral convex expansion with respect to $s_{i}$ if and only if the
infinite face of $G_{i}$ is forcing. Note that the infinite face of the
subgraph $I[C_{2}]$ is not forcing. Then $height(\mathcal{M}(G))>n$. This is a
contradiction to the assumption that the infinite face of $G$ is forcing,
since the infinite face of $G$ is forcing if and only if
$height(\mathcal{M}(G))=n$ [5]. $\Box$

A coronene is the benzenoid system shown in Figure 2. It is known that an
elementary benzenoid system $G$ has no coronenes as nice subgraphs if and only
if for any pair of vertex disjoint cycles that form a nice subgraph of $G$
their interiors are disjoint [26]. The following corollary follows immediately
by Lemma 3.2.

Figure 2:  The benzenoid system coronene.

###### Corollary 3.3

Let $G$ be an elementary benzenoid system. Then the infinite face of $G$ is
forcing if and only if $G$ has no coronenes as nice subgraphs.

Next, we will present a bijection between the set of $k$-dimensional maximal
hypercubes of $R(G)$ and the set of cardinality $k$ maximal resonant sets of
$G$, which extends Lemma 4.2 and Theorem 4.3 in [21] from an elementary
benzenoid system $G$ without coronenes as nice subgraphs to a plane elementary
bipartite graph $G$ whose infinite face is forcing.

###### Lemma 3.4

Let $G$ be a plane elementary bipartite graph other than $K_{2}$. Assume that
the infinite face of $G$ is forcing. Then $(i)$ $S$ is a maximal resonant set
of $G$ if and only if $S$ is a canonical resonant set of $G$. $(ii)$ There is
a bijection between the set of maximal hypercubes of $R(G)$ and the set of
maximal resonant sets of $G$ which maps a $k$-dimensional maximal hypercube to
a cardinality $k$ maximal resonant set, where $k$ is a positive integer.

Proof. $(i)$ Sufficiency. Let $S$ be a canonical resonant set of $G$. Then
$G-S$ has a unique perfect matching. Hence, if $M$ is a perfect matching of
$G$ such that each finite face in $S$ is $M$-resonant, then $G$ has no other
$M$-alternating cycles except the periphery of each finite face in $S$. It
implies that $S$ cannot be contained in any other resonant set of $G$, and so
$S$ is maximal.

Necessity. Let $S$ be a maximal resonant set of $G$. Suppose that $S$ is not
canonical. Then $G-S$ has at least two different perfect matchings $M_{1}^{*}$
and $M_{2}^{*}$. Since the symmetric difference of any two perfect matchings
is a set of vertex disjoint cycles, it follows that $G-S$ contains at least
one $(M_{1}^{*},M_{2}^{*})$-alternating cycle $C$. Let $M_{1}$ and $M_{2}$ be
two perfect matchings of $G$ that are extended from $M_{1}^{*}$ and
$M_{2}^{*}$ respectively such that all finite faces contained in $S$ are
$(M_{1},M_{2})$-resonant. Then the $(M_{1}^{*},M_{2}^{*})$-alternating cycle
$C$ contained in $G-S$ is also an $(M_{1},M_{2})$-alternating cycle. Let
$I[C]$ denote the subgraph of $G$ induced by cycle $C$ together with its
interior. Then by Corollary 3.4 in [31], there exists an finite face $s$ of
$G$ that is contained in the interior of $C$, and $s$ is
$(M_{1},M_{2})$-resonant. If $S$ and $I[C]$ are vertex disjoint, then
$S\cup\\{s\\}$ is also a resonant set. This is a contradiction since $S$ is
maximal. If $S$ and $I[C]$ are not vertex disjoint, then there exists a finite
face $s$ contained in both $S$ and $I[C]$. Note that the periphery of $s$ and
$C$ are two vertex disjoint cycles which form a nice subgraph of $G$, but the
interior of $s$ is contained in the interior of $C$. Then by Lemma 3.2, the
infinite face of $G$ is not forcing. This is a contradiction.

$(ii)$ Let $f:\mathcal{H}(R(G))\rightarrow\mathcal{RS}(G)$ be a mapping
defined in Lemma 3.1, where $\mathcal{H}(R(G))$ is the set of nontrivial
hypercubes of $R(G)$ and $\mathcal{RS}(G)$ is the set of nonempty resonant
sets of $G$. Let $Q$ be a maximal $k$-dimensional hypercube of $R(G)$. Then
the image of $Q$ under the mapping $f$ is a cardinality $k$ resonant set $S$.
We claim that $S$ must be a maximal resonant set. Obviously, the inverse image
of $S$ under the mapping $f$ is a set of $k$-dimensional hypercubes
$\mathcal{H}_{S}$. If $S$ is not maximal, then each hypercube in
$\mathcal{H}_{S}$ is contained in a hypercube of $G$ of dimension greater than
$k$. This is a contradiction to the assumption that $Q\in\mathcal{H}_{S}$ is a
maximal $k$-dimensional hypercube of $R(G)$. Consequently, $S$ is a maximal
resonant set and by $(i)$, $S$ is also a canonical resonant set. By the proof
of Lemma 3.1, the inverse image of $S$ under the mapping $f$ is a unique
maximal $k$-dimensional hypercube of $R(G)$. Therefore, $f$ induces a
bijection between the set of maximal hypercubes of $R(G)$ and the set of
maximal resonant sets of $G$ which maps a $k$-dimensional maximal hypercube to
a cardinality $k$ maximal resonant set. $\Box$

We now provide a connection between (maximal) resonant sets of a
homeomorphically peripheral color alternating graph $G$ and (maximal)
independent sets of its inner dual $G^{*}$.

###### Lemma 3.5

Assume that $G$ is a homeomorphically peripheral color alternating graph with
inner dual $G^{*}$. Let $\mathcal{RS}(G)$ be the set of nonempty resonant sets
of $G$ and $\mathcal{IS}(G^{*})$ be the set of nonempty independent sets of
$G^{*}$. Define $g:\mathcal{RS}(G)\rightarrow\mathcal{IS}(G^{*})$ such that
$g(S)=S^{*}$, where $S$ is a resonant set of $G$ and $S^{*}$ is the
corresponding independent set of $G^{*}$. Then $g$ is well-defined. Moreover,
$g$ induces a bijection between the set of maximal resonant sets of $G$ and
the set of maximal independent sets of $G^{*}$, which maps a cardinality $k$
maximal resonant set of $G$ to a cardinality $k$ maximal independent set of
$G^{*}$, where $k$ is a positive integer.

Proof. If $S$ is a resonant set of $G$, then by definition, finite faces of
$G$ contained in $S$ are pairwise vertex disjoint. It follows that its
corresponding vertex set $S^{*}$ contained in $G^{*}$ is an independent set of
$G^{*}$, and so $g$ is well-defined. It is trivial that $g$ is injective since
different resonant sets of $G$ have different corresponding vertex sets in
$G^{*}$. On the other hand, if $S^{*}$ is an independent set of $G^{*}$, then
the finite faces in the corresponding set $S$ of $G$ are pairwise edge
disjoint. Since $G$ is homeomorphically peripheral color alternating, it
follows that any two finite faces in $S$ are vertex disjoint because any
vertex degree of $G$ is at most 3. Recall that each handle of $G$ is a path on
an even number of vertices, so the induced subgraph $G-S$ is either empty or
has a perfect matching. Therefore, $S$ is a resonant set of $G$ and so $g$ is
surjective.

We then show that $S$ is a maximal resonant set of $G$ if and only if
$S^{*}=g(S)$ is a maximal independent set of $G^{*}$. Necessity. Let $S$ be a
maximal resonant set of $G$. Suppose that $S^{*}$ is not maximal. Then there
exists an independent set $T^{*}$ of the inner dual $G^{*}$ such that
$S^{*}\subsetneq T^{*}$. Let $T$ be the set of finite faces of $G$
corresponding to the vertices from $T^{*}$. Similarly to the above paragraph,
we can show that $T$ is also a resonant set of $G$, which is a contradiction
to the assumption that $S$ is maximal. Sufficiency. Assume that $S^{*}$ is a
maximal independent set of the inner dual $G^{*}$. Then the corresponding set
$S$ of finite faces in $G$ is a resonant set of $G$. Therefore, the induced
subgraph $G-S$ is either empty or has a perfect matching. Suppose that $S$ is
not maximal. Then there exists a resonant set $T$ such that $S\subsetneq T$.
However, its corresponding set $T^{*}$ of vertices in the inner dual $G^{*}$
is obviously an independent set of $G^{*}$ and $S^{*}\subsetneq T^{*}$, which
is a contradiction to the assumption that $S^{*}$ is maximal.

It is clear that if $g(S)=S^{*}$, then $|S|=|S^{*}|=k$ for some positive
integer $k$. Therefore, the conclusion follows. $\Box$

Based on Lemma 3.4 and Lemma 3.5, for a homeomorphically peripheral color
alternating graph $G$, we can establish a bijection between the set of maximal
hypercubes of its resonance graph $R(G)$ and the set of maximal independent
sets of its inner dual $G^{*}$.

###### Corollary 3.6

Assume that $G$ is a homeomorphically peripheral color alternating graph with
inner dual $G^{*}$. Let $f:\mathcal{H}(R(G))\rightarrow\mathcal{RS}(G)$ be a
mapping defined in Lemma 3.1 and
$g:\mathcal{RS}(G)\rightarrow\mathcal{IS}(G^{*})$ be a mapping defined in
Lemma 3.5. Define $h:\mathcal{H}(R(G))\rightarrow\mathcal{IS}(G^{*})$ such
that $h(Q)=g(f(Q))$ for any $Q\in\mathcal{H}(R(G))$. Then $h$ induces a
bijection between the set of maximal hypercubes of $R(G)$ and the set of
maximal independent sets of $G^{*}$, which maps a $k$-dimensional maximal
hypercube $Q$ of $R(G)$ to a cardinality $k$ maximal independent set
$S_{Q}^{*}$ of $G^{*}$ with the property that each vertex of $S_{Q}^{*}$
corresponds to a face-label of a $\Theta$-class of $Q$, where $k$ is a
positive integer.

Proof. By Lemma 3.4, $f:\mathcal{H}(R(G))\rightarrow\mathcal{RS}(G)$ induces a
bijection between the set of maximal hypercubes of $R(G)$ and the set of
maximal resonant sets of $G$ which maps a $k$-dimensional maximal hypercube
$Q$ of $R(G)$ to a cardinality $k$ maximal resonant set $S_{Q}$ of $G$ with
the property that each finite face in $S_{Q}$ is a face-label of a
$\Theta$-class of $Q$. By Lemma 3.5,
$g:\mathcal{RS}(G)\rightarrow\mathcal{IS}(G^{*})$ induces a bijection between
the set of maximal resonant sets of $G$ and the set of maximal independent
sets of $G^{*}$, which maps a cardinality $k$ maximal resonant set $S_{Q}$ of
$G$ to a cardinality $k$ maximal independent set $S_{Q}^{*}$ of $G^{*}$, where
$k$ is a positive integer.

Let $h:\mathcal{H}(R(G))\rightarrow\mathcal{IS}(G^{*})$ be defined as
$h(Q)=g(f(Q))$ for any $Q\in\mathcal{H}(R(G))$. It follows that $h$ induces a
bijection between the set of maximal hypercubes of $R(G)$ and the set of
maximal independent sets of $G^{*}$, which maps a $k$-dimensional maximal
hypercube $Q$ of $R(G)$ to a cardinality $k$ maximal independent set
$S_{Q}^{*}$ of $G^{*}$ with the property that each vertex of $S_{Q}^{*}$
corresponds to a face-label of a $\Theta$-class of $Q$. $\Box$

Finally, we characterize resonance graphs that are daisy cubes using the
bijection obtained in Corollary 3.6.

###### Theorem 3.7

Let $G$ be a plane elementary bipartite graph other than $K_{2}$. Then its
resonance graph $R(G)$ is a daisy cube if and only if there is a bijection
$\phi$ between the set of maximal hypercubes of $R(G)$ and the set of maximal
independent sets of the inner dual $G^{*}$ of $G$, where $R(G)^{\tau}$ is a
tree and isomorphic to the inner dual $G^{*}$ of $G$, and $\phi$ maps a
$k$-dimensional maximal hypercube $Q$ of $R(G)$ to a cardinality $k$ maximal
independent set $S_{Q}^{*}$ of $G^{*}$ with the property that each vertex of
$S_{Q}^{*}$ corresponds to a face-label of a $\Theta$-class of $Q$, where $k$
is a positive integer.

Proof. It is trivial when $G$ has only one finite face. Assume that $G$ has
more than one finite face.

Necessity. Assume that $R(G)$ is a daisy cube. By Theorem 2.1, $G$ is
homeomorphically peripheral color alternating. By Corollary 3.6, there is a
bijection between the set of maximal hypercubes of $R(G)$ and the set of
maximal independent sets of $G^{*}$, which maps a $k$-dimensional maximal
hypercube $Q$ of $R(G)$ to a cardinality $k$ maximal independent set
$S_{Q}^{*}$ of $G^{*}$ with the property that each vertex of $S_{Q}^{*}$
corresponds to a face-label of a $\Theta$-class of $Q$, where $k$ is a
positive integer.

Since $G$ is homeomorphically peripheral color alternating, by the proof of
Theorem 3.4 in [1], there exists a peripheral color alternating graph
$G^{\prime}$ such that $R(G)$ is isomorphic to $R(G^{\prime})$, and the inner
dual $G^{*}$ of $G$ is isomorphic to the inner dual $G^{\prime*}$ of
$G^{\prime}$. Note that a peripheral color alternating graph is 2-connected
outerplane bipartite, Then by [4], $R(G^{\prime})^{\tau}$ is a tree and
isomorphic to the inner dual $G^{\prime*}$ of $G^{\prime}$. Therefore,
$R(G)^{\tau}$ is a tree and isomorphic to the inner dual $G^{*}$ of $G$.

Sufficiency. Assume that $s_{1},s_{2},\ldots,s_{n}$ are finite faces of $G$,
and $s^{*}_{1},s^{*}_{2},\ldots,s^{*}_{n}$ are the corresponding vertices of
its inner dual $G^{*}$. Let $\mathcal{I}=\\{I_{1},I_{2},\ldots,I_{t}\\}$ be
the set of maximal independent sets of the inner dual $G^{*}$. For $1\leq
i\leq t$, we can write a unique binary code $b(I_{i})$ of length $n$ for each
$I_{i}$, such that the $j$-th position is $1$ if $I_{i}$ contains $s^{*}_{j}$,
and $0$ otherwise. Then $|I_{i}|$ is the number of 1’s in $b(I_{i})$ for each
$1\leq i\leq t$. Moreover, let
$b(\mathcal{I})=\\{b(I_{1}),b(I_{2}),\ldots,b(I_{t})\\}$. By our assumption,
there is a bijection between the set of maximal hypercubes of $R(G)$ and the
set of maximal independent sets of $G^{*}$, which maps a $k$-dimensional
maximal hypercube $Q$ of $R(G)$ to a cardinality $k$ maximal independent set
$S_{Q}^{*}$ of $G^{*}$ with the property that each vertex of $S_{Q}^{*}$
corresponds to a face-label of a $\Theta$-class of $Q$, where $k$ is a
positive integer. Then we can assume that
$Q_{\mathcal{I}}=\\{Q_{I_{1}},Q_{I_{2}},\ldots,Q_{I_{t}}\\}$ is the set of
maximal hypercubes of $R(G)$ such that the set of face-labels for
$\Theta$-classes of $Q_{I_{i}}$ corresponds to the maximal independent set
$I_{i}$ of $G^{*}$. For each $1\leq i\leq t$, the maximal independent set
$I_{i}$ of $G^{*}$ contains $2^{|I_{i}|}$ subsets, and each subset can be
represented by a binary code of length $n$ such that the $j$-th position is
$1$ if the subset contains the finite face $s_{j}$, and $0$ otherwise. It
follows that for each $1\leq i\leq t$, we can label $2^{|I_{i}|}$ vertices of
the maximal hypercube $Q_{I_{i}}$ of $R(G)$ as binary codes of $2^{|I_{i}|}$
subsets of $I_{i}$ naturally such that there is an edge between two vertices
of $Q_{I_{i}}$ if their binary codes differ in exactly one position. It is
clear that each maximal independent set $I_{i}$ contains the empty set as the
smallest subset, and $I_{i}$ itself as the largest subset. Therefore, for
$1\leq i\leq t$, the maximal hypercube $Q_{I_{i}}$ of $R(G)$ has a vertex with
the binary code $0^{n}$ and a vertex with the binary code $b(I_{i})$. Note
that each vertex of $R(G)$ is a vertex of some maximal hypercube of $R(G)$ and
each edge of $R(G)$ is an edge of some maximal hypercube of $R(G)$. Then
$R(G)$ is isomorphic to
$Q_{n}(b(\mathcal{I}))=\langle\\{u\in\mathcal{B}^{n}:u\leq b(I_{i})\,\text{
for some }\,I_{i}\in\mathcal{I}\\}\rangle$. Therefore, $R(G)$ is a daisy cube
with the set of maximal elements
$b(\mathcal{I})=\\{b(I_{1}),b(I_{2}),\ldots,b(I_{t})\\}$. $\Box$

###### Remark 3.1

The proof for the sufficiency of Theorem 3.7 provides a binary code labelling
for all vertices of a resonance graph as a daisy cube, equivalently, a binary
code labelling for all perfect matchings of a homeomorphically peripheral
color alternating graph $G$. For example, see Figure 3.

Figure 3:  The resonance graph $R(G)$ as a daisy cube with three maximal
elements corresponding to three maximal independent sets of $G^{*}\cong
R(G)^{\tau}$ which is a tree.

Note that by Theorem 4.3 in [1], for a plane bipartite graph $G$ with a
perfect matching, its resonance graph $R(G)$ is a daisy cube if and only if
$G$ is weakly elementary such that each elementary component of $G$ different
from $K_{2}$ is homeomorphically peripheral color alternating. Next, we
provide another characterization of resonance graphs of plane bipartite graphs
that are daisy cubes.

###### Corollary 3.8

Let $G$ be a plane bipartite graph with elementary components
$G_{1},G_{2},\ldots,G_{m}$ different from $K_{2}$. Then $R(G)$ is a daisy cube
if and only if for each $1\leq i\leq m$, there is a bijection $\phi_{i}$
between the set of maximal hypercubes of $R(G_{i})$ and the set of maximal
independent sets of $G^{*}_{i}$, where $R(G)^{\tau}$ is a forest with $m$
components $R(G_{i})^{\tau}$ for $1\leq i\leq m$, each of which is a tree
isomorphic to the inner dual $G^{*}_{i}$ of $G_{i}$, and $\phi_{i}$ maps a
$k$-dimensional maximal hypercube of $R(G_{i})$ to a cardinality $k$ maximal
independent set of $G^{*}_{i}$.

Proof. Note that $R(G)=R(G_{1})\Box R(G_{2})\Box\cdots\Box R(G_{m})$. By
Corollary 4.2 in [1], a Cartesian product is a daisy cube if and only if each
factor is a daisy cube. It follows that $R(G)$ is a daisy cube if and only if
$R(G_{i})$ is a daisy cube for $1\leq i\leq m$. By Lemma 3.2 in [13], the
$\tau$-graph of a Cartesian product is a disjoint union of $\tau$-graphs of
its factors, then $R(G)^{\tau}=R(G_{1})^{\tau}\cup
R(G_{2})^{\tau}\cup\ldots\cup R(G_{m})^{\tau}$. The conclusion follows by
Theorem 3.7. $\Box$

##  4 When daisy cubes are resonance graphs

We now study when daisy cubes are resonance graphs in terms of their
$\tau$-graphs. In general, two different partial cubes can have isomorphic
$\tau$-graphs. For example, the cycle $C_{6}$ and the Lucas cube $\Lambda_{3}$
are different partial cubes with the same $\tau$-graph $C_{3}$. But daisy
cubes with isomorphic $\tau$-graphs are isomorphic.

###### Lemma 4.1

Let $A$ and $B$ be daisy cubes. If their $\tau$-graphs $A^{\tau}$ and
$B^{\tau}$ are isomorphic, then $A$ and $B$ are isomorphic.

Proof. By induction on the number $n$ of $\Theta$-classes of daisy cubes. If
$n=1$, then any daisy cube with one $\Theta$-class is the one-edge graph. If
$n=2$, then any daisy cube with two $\Theta$-classes has the property that its
$\tau$-graph is either an edge or two isolated vertices. If its $\tau$-graph
is an edge, then the daisy cube is a path of length $2$. If its $\tau$-graph
is two isolated vertices, then the daisy cube is a 4-cycle.

We assume that if two daisy cubes have less than $n$ $\Theta$-classes and
their $\tau$-graphs are isomorphic, then two daisy cubes are isomorphic. Let
$\\{E_{1},E_{2},\ldots,E_{n}\\}$ (respectively,
$\\{F_{1},F_{2},\ldots,F_{n}\\}$) be the set of $\Theta$-classes of daisy cube
$A$ (respectively, daisy cube $B$). Then $\\{E_{1},E_{2},\ldots,E_{n}\\}$
(respectively, $\\{F_{1},F_{2},\ldots,F_{n}\\}$) is the vertex set of
$\tau$-graph $A^{\tau}$ (respectively, $\tau$-graph $B^{\tau}$). Assume that
$\phi:A^{\tau}\rightarrow B^{\tau}$ is an isomorphism such that
$\phi(E_{i})=F_{i}$ for $1\leq i\leq n$.

By Proposition 2.1 in [20], every $\Theta$-class of a daisy cube is
peripheral. By Theorem 2.10 in [20], a connected graph is a daisy cube if and
only if it can be obtained from the one-vertex graph by a sequence of
$\leq$-expansions. Then we can assume that $E_{n}$ is the new $\Theta$-class
generated during the process to obtain the daisy cube $A$ from a daisy cube
$A_{n-1}$ by a peripheral expansion with respect to a $\leq$-subgraph
$A^{\prime}_{n-1}$ of $A_{n-1}$; and $F_{n}$ is the new $\Theta$-class
generated during the process to obtain the daisy cube $B$ from a daisy cube
$B_{n-1}$ by a peripheral expansion with respect to a $\leq$-subgraph
$B^{\prime}_{n-1}$ of $B_{n-1}$. Then by Proposition 2.7 in [20], each of
$A^{\prime}_{n-1}$ and $B^{\prime}_{n-1}$ is isomorphic to a daisy cube. By
definition, we can see that $A^{\tau}\setminus\\{E_{n}\\}$ is the $\tau$-graph
of $A_{n-1}$, and $B^{\tau}\setminus\\{F_{n}\\}$ is the $\tau$-graph of
$B_{n-1}$. By our assumption, $\phi:A^{\tau}\rightarrow B^{\tau}$ is an
isomorphism with $\phi(E_{n})=F_{n}$. Then $A^{\tau}\setminus\\{E_{n}\\}$ is
isomoprhic to $B^{\tau}\setminus\\{F_{n}\\}$. By [14], a contraction of a
daisy cube is a daisy cube. Then the contraction of $\Theta$-class $E_{n}$
from the daisy cube $A$ results a daisy cube $A_{n-1}$ whose $\tau$-graph is
$A^{\tau}\setminus\\{E_{n}\\}$; and the contraction of $\Theta$-class $F_{n}$
from the daisy cube $B$ results a daisy cube $B_{n-1}$ whose $\tau$-graph is
$B^{\tau}\setminus\\{F_{n}\\}$. By induction hypothesis, daisy cubes $A_{n-1}$
and $B_{n-1}$ are isomorphic.

During the process to obtain daisy cube $A$ from $A_{n-1}$ by a peripheral
expansion with respect to a $\leq$-subgraph $A^{\prime}_{n-1}$ of $A_{n-1}$, a
new subgraph $A^{\prime}_{n-1}\Box K_{2}$ and a new $\Theta$-class $E_{n}$ are
generated. By Lemma 3.2 in [13], $(A^{\prime}_{n-1}\Box
K_{2})^{\tau}={A^{\prime}}^{\tau}_{n-1}\cup K_{2}^{\tau}$. Then $E_{n}$ is not
adjacent to any vertices of $A^{\tau}$ contained in
${A^{\prime}}^{\tau}_{n-1}$ which form the set of $\Theta$-classes of
$A^{\prime}_{n-1}$. By Proposition 2.2 in [20], every $\Theta$-class of a
daisy cube with $n$ $\Theta$-classes contains an edge with the vertex $0^{n}$
as an endpoint. By the definition of a $\tau$-graph, $E_{n}$ is adjacent to
all vertices of $A^{\tau}$ contained in $V(A^{\tau})\setminus
V({A^{\prime}}^{\tau}_{n-1})$. During the process to obtain daisy cube $B$
from $B_{n-1}$ by a peripheral expansion with respect to a $\leq$-subgraph
$B^{\prime}_{n-1}$ of $B_{n-1}$, a new subgraph $B^{\prime}_{n-1}\Box K_{2}$
and a new $\Theta$-class $F_{n}$ are generated. Similarly, $F_{n}$ is not
adjacent to any vertices of $B^{\tau}$ contained in
${B^{\prime}}^{\tau}_{n-1}$ which form the set of $\Theta$-classes of
$B^{\prime}_{n-1}$; and $F_{n}$ is adjacent to all vertices of $B^{\tau}$
contained in $V(B^{\tau})\setminus V({B^{\prime}}^{\tau}_{n-1})$.

Recall that $\phi:A^{\tau}\rightarrow B^{\tau}$ is an isomorphism and
$\phi(E_{n})=F_{n}$. Then the induced subgraph of $A^{\tau}$ generated by all
vertices not adjacent to $E_{n}$ is isomorphic to the induced subgraph of
$B^{\tau}$ generated by all vertices not adjacent to $F_{n}$. It follows that
$\langle V({A^{\prime}}^{\tau}_{n-1})\rangle$ and $\langle
V({B^{\prime}}^{\tau}_{n-1})\rangle$ are isomorphic. By induction hypothesis,
daisy cubes $A^{\prime}_{n-1}$ and $B^{\prime}_{n-1}$ are isomorphic. It
follows that daisy cubes $A$ and $B$ are isomorphic by their peripheral
expansion structures described above. $\Box$

###### Theorem 4.2

A daisy cube $H$ with at least one edge is a resonance graph of a plane
bipartite graph if and only if its $\tau$-graph $H^{\tau}$ is a forest.
Moreover, $H$ is a resonance graph of a plane elementary bipartite graph if
and only if its $\tau$-graph $H^{\tau}$ is a tree.

Proof. Let $H$ be a daisy cube with at least one edge. By Theorem 4.3 in [1],
we know that if a daisy cube is the resonance graph $R(G)$ of a plane
bipartite graph $G$, then $G$ is weakly elementary. There are two
possibilities. If $G$ is elementary, then by Theorem 3.7, $R(G)^{\tau}$ is a
tree. If $G$ is weakly elementary with more than one elementary component,
then by Corollary 3.8, $R(G)^{\tau}$ is a forest.

It remains to show that if $H^{\tau}$ is a tree or a forest, then $H$ is a
resonance graph $R(G)$ of a plane (weakly) elementary bipartite graph $G$. If
$H^{\tau}$ is a tree, then we can construct a peripheral color alternating
graph $G$ whose inner dual $G^{*}$ is isomorphic to the tree $H^{\tau}$. By
Theorem 2.1, $R(G)$ is a daisy cube. Since a peripheral color alternating
graph $G$ is 2-connected outerplane bipartite, by [4], $R(G)^{\tau}$ is a tree
and isomorphic to the inner dual $G^{*}$ of $G$. It follows that $H^{\tau}$
and $R(G)^{\tau}$ are isomorphic. By Lemma 4.1, daisy cubes $H$ and $R(G)$ are
isomorphic, and so $H$ is a resonance graph of a plane elementary bipartite
graph.

If $H^{\tau}$ is a forest with more than one component, then
$H^{\tau}=T_{1}\cup T_{2}\cup\ldots\cup T_{m}$, where $T_{i}$ is a tree for
$1\leq i\leq m$. We can construct a list of peripheral color alternating
graphs $G_{i}$ with the property that inner dual $G_{i}^{*}$ is isomorphic to
tree $T_{i}$, and resonance graph $R(G_{i})$ is a daisy cube for $1\leq i\leq
m$. By [4], $R(G_{i})^{\tau}$ is a tree and isomorphic to the inner dual
$G_{i}^{*}$ of $G_{i}$ for $1\leq i\leq m$. It follows that $R(G_{i})^{\tau}$
and $T_{i}$ are isomorphic trees for $1\leq i\leq m$. Let $G$ be a plane
bipartite graph constructed by adding an edge $e_{i}$ between one vertex from
$G_{i}$ and one vertex from $G_{i+1}$ for $1\leq i\leq m-1$. Then $G$ is a
weakly elementary with $m$ elementary components $G_{i}$ for $1\leq i\leq m$,
and its resonance graph $R(G)=R(G_{1})\Box R(G_{2})\Box\cdots\Box R(G_{m})$.
By Corollary 4.2 in [1], $R(G)$ is a daisy cube since $R(G_{i})$ is a daisy
cube for $1\leq i\leq m$. By Lemma 3.2 in [13],
$R(G)^{\tau}=R(G_{1})^{\tau}\cup R(G_{2})^{\tau}\cup\ldots\cup
R(G_{m})^{\tau}$. Recall that $T_{i}$ and $R(G_{i})^{\tau}$ are isomorphic
trees for $1\leq i\leq m$. Then $H^{\tau}$ and $R(G)^{\tau}$ are isomorphic.
By Lemma 4.1, daisy cubes $H$ and $R(G)$ are isomorphic. So $H$ is a resonance
graph of a plane weakly elementary bipartite graph. $\Box$

Recall that Fibonacci cubes and Lucas cubes are special types of daisy cubes
[14]. Fibonacci cubes are the resonance graphs of fibonaccenes, i.e., zigzag
hexagonal chains [15], and a structural characterization was provided for all
plane bipartite graphs whose resonance graphs are Fibonacci cubes [29]. On the
other hand, a Lucas cube $\Lambda_{n}$ cannot be a resonance graph of any
plane bipartite graph for $n\geq 3$ [29].

We now state some interesting consequences of our results regarding Fibonacci
and Lucas cubes.

###### Corollary 4.3

The number of maximal hypercubes of a Fibonacci cube $\Gamma_{n}$ equals the
Padovan number $a_{n+1}$ for any $n\geq 1$.

Proof. By [22], the $\tau$-graph of a Fibonacci cube $\Gamma_{n}$ is a path
$P_{n}$ of order $n$. It is known [11] that for the path on $n$ vertices, the
number of maximal independent sets equals the Padovan number $a_{n+1}$ from
the Padovan sequence $a_{0},a_{1},a_{2},\ldots$, which is defined as
$a_{0}=a_{1}=a_{2}=1$, and $a_{n}=a_{n-2}+a_{n-3}$ for any $n\geq 3$. The
conclusion follows by Theorem 3.7. $\Box$

###### Proposition 4.4

Let $\Lambda_{n}$ be a Lucas cube where $n\geq 3$. Then its $\tau$-graph
$\Lambda_{n}^{\tau}$ is a cycle $C_{n}$.

Proof. For each integer $i\in\\{1,\ldots,n\\}$, let $X_{i}$ be the
$\Theta$-class of $\Lambda_{n}$ corresponding to the $i$-th position in the
binary codes of $\Lambda_{n}$. We first prove that $X_{1}$ is adjacent to
$X_{2}$ and $X_{n}$ in $\Lambda_{n}^{\tau}$. Suppose that $X_{1}$ and $X_{2}$
are not adjacent in $\Lambda_{n}^{\tau}$. Then there exists a 4-cycle in
$\Lambda_{n}$ such that its vertices have the binary codes $00a^{n-2}$,
$01a^{n-2}$, $11a^{n-2}$, and $10a^{n-2}$, which is a contradiction since the
third vertex does not exist in $\Lambda_{n}$. Similarly, we can show that
$X_{1}$ and $X_{n}$ are adjacent. Note that vertices $0^{n}$,
$0^{j-1}10^{n-j}$, $10^{j-2}10^{n-j}$, and $10^{n-1}$ form a $4$-cycle in
$\Lambda_{n}$, where two edges belong to $X_{1}$ and the other two edges
belong to $X_{j}$. It follows that $X_{1}$ cannot be adjacent to $X_{j}$ in
$\Lambda_{n}^{\tau}$, where $j\in\\{3,\ldots,n-1\\}$. Therefore, $X_{1}$ is
adjacent only to $X_{2}$ and $X_{n}$ in $\Lambda_{n}^{\tau}$. Similar argument
can be applied for any vertex of $\Lambda_{n}^{\tau}$, and so
$\Lambda_{n}^{\tau}$ is a cycle on $n$ vertices. $\Box$

By Theorem 4.2 and Proposition 4.4, the Lucas cube $\Lambda_{n}$, where $n\geq
3$, cannot be the resonance graph of a plane bipartite graph. Moreover, it is
obvious that the $\tau$-graph of a nontrivial hypercube $Q_{n}$, where $n\geq
2$, is the graph on $n$ vertices without edges. Consequently, the hypercube
$Q_{n}$, where $n\geq 2$, cannot be the resonance graph of a plane elementary
bipartite graph either. However, any hypercube $Q_{n}$, where $n\geq 1$, is
the resonance graph of a plane weakly elementary bipartite graph with $n$ even
cycles as $n$ elementary components.

By Theorem 3.7, we have the following observation.

###### Corollary 4.5

If a daisy cube $H$ is the resonance graph of a plane elementary bipartite
graph with $n\geq 1$ finite faces, then $H^{\tau}$ is a tree of order $n$ and
there is a bijection between the set of maximal hypercubes of $H$ and the set
of maximal independent sets of $H^{\tau}$, which maps a $k$-dimensional
maximal hypercube of $H$ to a cardinality $k$ maximal independent set of
$H^{\tau}$, where $k$ is a positive integer.

This motivates us to characterize trees with $k$ maximal independent sets and
provide structure properties for daisy cubes whose $\tau$-graphs are trees and
have $k$ maximal hypercubes. We solve the above problem when $k$ is at most
$5$.

For each integer $n\geq 2$, let $S^{1}_{n-1}$ be a star on $n$ vertices. For
each integer $i\geq 2$, let $S_{p,q}^{i}$ be a tree obtained from a path
$P_{i}$ on $i$ vertices by adding $p$ pendant edges at one end vertex of
$P_{i}$ and $q$ pendant edges at the other end vertex of $P_{i}$. If $i=2$,
the obtained tree is called a bistar. Moreover, by $S_{p,q,r}^{3}$ we denote a
tree obtained from a path $P=v_{1}v_{2}v_{3}$ on 3 vertices by adding $p$
pendant edges at $v_{1}$, $q$ pendant edges at $v_{2}$, and $r$ pendant edges
at $v_{3}$.

###### Lemma 4.6

Let $T$ be a tree and $\textnormal{MIS}(T)$ be the set of maximal independent
sets of $T$. Then

(i) $|\textnormal{MIS}(T)|=2$ if and only if $T$ is a star $S^{1}_{n-1}$ for
some $n\geq 2$;

(ii) $|\textnormal{MIS}(T)|=3$ if and only if $T$ is a bistar $S_{p,q}^{2}$
for some $p,q\geq 1$.

(iii) $|\textnormal{MIS}(T)|=4$ if and only if $T$ is a $S_{p,q}^{3}$ for some
$p,q\geq 1$.

(iv) $|\textnormal{MIS}(T)|=5$ if and only if $T$ is a $S_{p,q}^{4}$ for some
$p,q\geq 1$ or a $S_{p,q,r}^{3}$ for some $p,q,r\geq 1$.

Proof. $(i)$ If $T$ is a star $S^{1}_{n-1}$ for some $n\geq 2$, then
$|\textnormal{MIS}(T)|=2$. On the other hand, if $|\textnormal{MIS}(T)|=2$ but
$T$ is not a star, then $T$ contains a path on four vertices. This implies
that $T$ has at least three maximal independent sets and so
$|\textnormal{MIS}(T)|>2$, which is a contradiction.

$(ii)$ If $T$ is a bistar $S_{p,q}^{2}$ for some $p,q\geq 1$, then
$|\textnormal{MIS}(T)|=3$. On the other hand, if $|\textnormal{MIS}(T)|=3$ but
$T$ is not a bistar, then $T$ contains a path on five vertices. This implies
that $T$ has at least four maximal independent sets and so so
$|\textnormal{MIS}(T)|>3$, which is a contradiction.

$(iii)$ If $T$ is a $S_{p,q}^{3}$ for some $p,q\geq 1$, then
$|\textnormal{MIS}(T)|=4$. On the other hand, if $|\textnormal{MIS}(T)|=4$,
then $T$ contains a path on five vertices $xv_{1}v_{2}v_{3}y$. Adding extra
pendant edges at $v_{1}$ or extra pendant edges at $v_{3}$ still results in a
tree with four maximal independent sets. Adding extra pendant edges at any
other vertices will result in tree with more than four maximal independent
sets.

$(iv)$ If $T$ is a $S_{p,q}^{4}$ for some $p,q\geq 1$ or a $S_{p,q,r}^{3}$ for
some $p,q,r\geq 1$, then $|\textnormal{MIS}(T)|=5$. On the other hand, if
$|\textnormal{MIS}(T)|=5$, then $T$ contains a $S_{p,q}^{3}$ obtained from a
path $P=v_{1}v_{2}v_{3}$ on 3 vertices by adding $p$ pendant edges at $v_{1}$
and $q$ pendant edges at $v_{3}$. There are only two methods to increase the
number of maximal independent sets by one. One method is to subdivide the path
$v_{1}v_{2}v_{3}$ by adding an extra vertex $x$, which will result in
$S_{p,q}^{4}$. The other method is to add extra pendent edges at $v_{2}$ which
will result in a $S_{p,q,r}^{3}$. $\Box$

###### Remark 4.1

Note that for a tree $T$, $\textrm{diam}(T)=2$ if and only if $T$ is a star,
and $\textrm{diam}(T)=3$ if and only if $T$ is a bistar. Hence, for
$k\in\\{2,3\\}$, the number of maximal independent sets of a tree $T$ is $k$
if and only if $diam(T)=k$.

By Corollary 4.5 and Lemma 4.6, we can easily determine the structure of daisy
cubes that are resonance graphs of plane elementary bipartite graphs and with
at most five maximal elements.

###### Theorem 4.7

Let $H$ be a daisy cube that is isomorphic to the resonance graph of a plane
elementary bipartite graph with $n\geq 1$ finite faces. If $H$ has at most
five maximal elements, then exactly one of the following holds.

  * (i)

$H$ is isomorphic to $K_{2}$.

  * (ii)

$H$ is isomorphic to an edge disjoint union of $K_{2}$ and $Q_{n-1}$ with one
common vertex $0^{n}$.

  * (iii)

$H$ has three maximal hypercubes $A$, $B$, and $C$ with one common vertex
$0^{n}$ and there are positive integers $p$ and $q$ such that $p+q+2=n$,
$\dim(A)=p+1$, $\dim(B)=p+q$, $\dim(C)=q+1$, where $A$ and $C$ are edge
disjoint, the intersection of $A$ and $B$ is a $p$-dimensional hypercube, and
the intersection of $B$ and $C$ is a $q$-dimensional hypercube.

  * (iv)

$H$ has four maximal hypercubes $A$, $B$, $C$, and $D$ with one common vertex
$0^{n}$ and there are positive integers $p$ and $q$ such that $p+q+3=n$,
$\dim(A)=p+1$, $\dim(B)=p+q+1$, $\dim(C)=q+1$, $\dim(D)=2$, where $A$ and $C$
are edge disjoint, $B$ and $D$ are edge disjoint, $A\cap B$ is a
$p$-dimensional hypercube, $B\cap C$ is a $q$-dimensional hypercube, $A\cap D$
is an edge, and $C\cap D$ is an edge.

  * (v)

$H$ has five maximal hypercubes $A$, $B$, $C$, $D$, and $E$ with one common
vertex $0^{n}$ and there are positive integers $p$ and $q$ such that
$p+q+4=n$, $\dim(A)=\dim(B)=p+q+1$, $\dim(C)=p+2$, $\dim(D)=q+2$, $\dim(E)=2$,
where $C$ and $D$ are edge disjoint, $E$ is edge disjoint from $A$ and $B$,
$A\cap B$ is a $(p+q)$-dimensional hypercube, $A\cap C$ is a
$(p+1)$-dimensional hypercube, $A\cap D$ is a $q$-dimensional hypercube,
$B\cap C$ is a $p$-dimensional hypercube, $B\cap D$ is a $(q+1)$-dimensional
hypercube, $C\cap E$ is an edge, and $D\cap E$ is an edge.

  * (vi)

$H$ has five maximal hypercubes $A$, $B$, $C$, $D$, and $E$ with one common
vertex $0^{n}$ and there are positive integers $p$, $q$, and $r$ such that
$p+q+r+3=n$, $\dim(A)=p+q+r$, $\dim(B)=p+r+1$, $\dim(C)=p+q+1$,
$\dim(D)=q+r+1$, $\dim(E)=q+2$, where $B$ and $E$ are edge disjoint, $A\cap B$
is a $(p+r)$-dimensional hypercube, $A\cap C$ is a $(p+q)$-dimensional
hypercube, $A\cap D$ is a $(q+r)$-dimensional hypercube, $A\cap E$ is a
$q$-dimensional hypercube, $B\cap C$ is a $p$-dimensional hypercube, $B\cap D$
is an $r$-dimensional hypercube, $C\cap D$ is a $q$-dimensional hypercube,
$C\cap E$ is a $(q+1)$-dimensional hypercube, and $D\cap E$ is a
$(q+1)$-dimensional hypercube.

Proof. By Corollary 4.5 and Lemma 4.6, we distinguish cases based on the
number of maximal independent sets of tree $H^{\tau}$. Case $(i)$ is trivial
when $|\textnormal{MIS}(H^{\tau})|=1$. In Case $(ii)$ we have
$|\textnormal{MIS}(H^{\tau})|=2$. By Lemma 4.6, $H^{\tau}$ is a star
$S^{1}_{n-1}$ for some $n\geq 2$. So, $H^{\tau}$ has two vertex disjoint
maximal independent sets: one has a single vertex, the other has $n-1$
vertices. It follows that $H$ has two edge disjoint maximal hypercubes $K_{2}$
and $Q_{n-1}$ with one common vertex $0^{n}$. In Case $(iii)$ let
$|\textnormal{MIS}(H^{\tau})|=3$. By Lemma 4.6, $H^{\tau}$ is a bistar
$S_{p,q}^{2}$ for some $p,q\geq 1$, where $p+q+2=n$. See Figure 4. Obviously,
the three maximal independent sets of $H^{\tau}$ are
$I_{A}=\\{u_{1},u_{2},\ldots,u_{p},v\\}$,
$I_{B}=\\{u_{1},u_{2},\ldots,u_{p},v_{1},v_{2},\ldots,v_{q}\\}$, and
$I_{C}=\\{u,v_{1},v_{2},\ldots,v_{q}\\}$.

Figure 4:  There maximal independent sets $I_{A}$, $I_{B}$, and $I_{C}$ of a
bistar $S_{p,q}^{2}$.

Consequently, $H$ has three maximal hypercubes $A$, $B$, and $C$ such that
$\dim(A)=|I_{A}|=p+1$, $\dim(B)=|I_{B}|=p+q$, and $\dim(C)=|I_{C}|=q+1$.
Moreover, $I_{A}\cap I_{C}=\emptyset$, $I_{A}\cap
I_{B}=\\{u_{1},u_{2},\ldots,u_{p}\\}$, and $I_{B}\cap
I_{C}=\\{v_{1},v_{2},\ldots,v_{q}\\}$. It follows that hypercubes $A$ and $C$
are edge disjoint, the intersection of hypercubes $A$ and $B$ is a
$p$-dimensional hypercube, and the intersection of hypercubes $B$ and $C$ is a
$q$-dimensional hypercube.

Cases $(iv)$, $(v)$ and $(vi)$ can be proved similarly to Case (iii). $\Box$

We conclude the section with the following open problem.

Problem. Let $k>5$. Characterize all trees for which
$|\textnormal{MIS}(T)|=k$.

##  5 Algorithms

In this section, we present two algorithms which produce a binary code
labelling for the vertex set of the resonance graph of a homeomorphically
peripheral color alternating graph. By definitions, any homeomorphically
peripheral color alternating graph $G$ can be transformed into a special type
of 2-connected outerplane bipartite graph $G^{\prime}$ which is called a
peripheral color alternating graph such that $R(G)$ is isomorphic to
$R(G^{\prime})$. By Lemma 3.3 in [1], a 2-connected outerplane bipartite graph
$G^{\prime}$ is peripheral color alternating if and only if either it has at
most two finite faces or every adjacent triple of finite faces in $G^{\prime}$
is regular, that is, any three finite faces $s$, $s^{\prime}$,
$s^{\prime\prime}$ of $G^{\prime}$ where $s$ and $s^{\prime}$ have the common
edge $e$, and $s^{\prime},s^{\prime\prime}$ have the common edge $f$ satisfy
the property that the distance $d_{L(G)}(e,f)$ between two edges $e$ and $f$
in the line graph $L(G)$ of $G$ is even [3]. We can use the simplified version
of the algorithm presented in [3] to obtain Algorithm 1.

Input: $RFD(G_{1},G_{2},\ldots,G_{n})$ of a homeomorphically peripheral color
alternating graph $G$ associated with a sequence $s_{1},\ldots,s_{n}$ of
finite faces.

Output: Binary codes for all perfect matchings of $G$.

1 $B:=\\{00,01,10\\}$

2 for  _$r=2,\ldots,n-1$_ do

3 $B^{\prime}:=\emptyset$

4 set $j\in\left\\{1,\ldots,r\right\\}$ such that $s_{j}$ is adjacent to
$s_{r+1}$

5 $i=\min\\{l\ |\ s_{l}\textrm{ is adjacent to }s_{j}\\}$

6 for  _each $x\in B$_ do

7 $B^{\prime}:=B^{\prime}\cup\\{x0\\}$

8 if  _$x_{j}=0$_ then

9 $B^{\prime}:=B^{\prime}\cup\\{x1\\}$

10 end if

11

12 end for

13 $B:=B^{\prime}$

14 end for

return _$B$_

Algorithm 1 Binary coding of perfect matchings of a homeomorphically
peripheral color alternating graph $G$ by a reducible face decomposition of
$G$.

Moreover, by Remark 3.1, it is possible to apply the approach described in the
proof of Theorem 3.7 to obtain Algorithm 2. In order to do that, we need to
find all maximal independent sets of a tree. Wilf [24] showed that for a tree
of order $n\geq 1$, the largest number of its maximal independent sets is
$2^{n/2-1}+1$ or $2^{(n-1)/2}$ depending on whether $n$ is even or odd. He
also provided a linear time algorithm for the computation of the number of
maximal independent sets of any given tree. Chang et al. [7] presented an
algorithm that generates all maximal independent sets for trees of order $n$
in lexicographic order with $O(n^{2})$ delay between the output of any two
successive independent sets and with $O(n)$ space.

Input: Inner dual $G^{*}$ with vertices $s_{1},\ldots,s_{n}$ of a
homeomorphically peripheral color alternating graph $G$.

Output: Binary codes for all perfect matchings of $G$.

1 find the maximal independent sets $I_{1},\ldots,I_{k}$ of $G^{*}$

2 $B:=\emptyset$

3 for  _$r=1,\ldots,k$_ do

4 for  _every subset $X$ of $I_{r}$_ do

5 $B:=B\cup\\{x_{1}x_{2}\ldots x_{n}\\}$, where for every
$i\in\\{1,\ldots,n\\}$, $x_{i}=1$ if $s_{i}\in X$ and $x_{i}=0$ if
$s_{i}\notin X$

6

7 end for

8

9 end for

return $B$

Algorithm 2 Binary coding of perfect matchings of a homeomorphically
peripheral color alternating graph $G$ by maximal independent sets of the
inner dual $G^{*}$.

Let $G$ be a homeomorphically peripheral color alternating graph. Note that
every binary code of a perfect matching of $G$ produced in Algorithm 2
corresponds to exactly one independent set of the inner dual $G^{*}$ of $G$.
Therefore, there exists a bijection between the set of all perfect matchings
of $G$ and the set of all independent sets of $G^{*}$.

###### Remark 5.1

If $G$ is a plane bipartite graph whose resonance graph $R(G)$ is a daisy
cube, then we can apply the presented algorithms on every nontrivial
elementary component of $G$.

Acknowledgment: Simon Brezovnik, Niko Tratnik, and Petra Žigert Pleteršek
acknowledge the financial support from the Slovenian Research and Innovation
Agency: research programme No. P1-0297 (Simon Brezovnik, Niko Tratnik, Petra
Žigert Pleteršek), projects No. J1-4031 (Simon Brezovnik), N1-0285 (Niko
Tratnik), and L7-4494 (Petra Žigert Pleteršek). All four authors thank the
Slovenian Research and Innovation Agency for financing our bilateral project
between Slovenia and the USA (title: Structural properties of resonance graphs
and related concepts, project No. BI-US/22-24-158).

## References

  * [1] S. Brezovnik, Z. Che, N. Tratnik, P. Žigert Pleteršek, Resonance graphs of plane bipartite graphs as daisy cubes, arXiv:2311.06508.
  * [2] S. Brezovnik, N. Tratnik, P. Žigert Pleteršek, Resonance graphs of catacondensed even ring systems, Appl. Math. Comput. 374 (2020) 125064.
  * [3] S. Brezovnik, N. Tratnik, P. Žigert Pleteršek, Resonance graphs and a binary coding of perfect matchings of outerplane bipartite graphs, MATCH Commun. Math. Comput. Chem. 90 (2023) 453–468.
  * [4] Z. Che, Characterizations of the resonance graph of an outerplane bipartite graph, Discrete Appl. Math. 258 (2019) 264–268.
  * [5] Z. Che, Peripheral convex expansions of resonance graphs, Order 38 (2021) 365-376.
  * [6] Z. Che, Z. Chen, Forcing faces in plane bipartite graphs (II), Discrete Appl. Math. 161 (2013) 71–80.
  * [7] Y. H. Chang, J. S. Wang, R. C. T. Lee, Generating all maximal independent sets on trees in lexicographic order, Inform. Sci. 76 (1994), 279–296.
  * [8] D. Ž. Djoković, Distance preserving subgraphs of hypercubes, J. Combin. Theory Ser. B 14 (1973) 263–-267.
  * [9] S. El-Basil, Kekulé structures as graph generators, J. Math. Chem. 14 (1993) 305–318.
  * [10] S. El-Basil, Generation of lattice graphs. An equivalence relation on Kekulé counts of catacondensed benzenoid hydrocarbons, J. Mol. Struct.(Theochem) 288 (1993) 67–84.
  * [11] Z. Füredi, The number of maximal independent sets in connected graphs, J. Graph Theory 11 (1987) 463–470.
  * [12] W. Gründler, Signifikante Elektronenstrukturen fur benzenoide Kohlenwasserstoffe, Wiss. Z. Univ. Halle 31 (1982) 97–116.
  * [13] S. Klavžar, M. Kovše, Partial cubes and their $\tau$-graphs, Eur. J. Comb. 28 (2007) 1037–1042.
  * [14] S. Klavžar, M. Mollard, Daisy cubes and distance cube polynomial, European J. Combin. 80 (2019), 214–223.
  * [15] S. Klavžar, P. Žigert Pleteršek, Fibonacci cubes are the resonance graphs of fibonaccenes, Fibonacci Q. 43 (2005) 269–276.
  * [16] L. Lovasz, M. D. Plummer, Matching theory, North-Holland Mathematics Studies, 121. Annals of Discrete Mathematics, Vol 29, North-Holland Publishing Co., Amsterdam, 1986.
  * [17] P. C. B. Lam, H. Zhang, A distributive lattice on the set of perfect matchings of a plane bipartite graph, Order 20 (2003) 13–29.
  * [18] K. Salem, S. Klavžar, I. Gutman, On the role of hypercubes in the resonance graphs of benzenoid graphs, Discrete Math. 306 (2006) 699–704.
  * [19] K. Salem, S. Klavžar, A. Vesel, P. Žigert, The Clar formulas of a benzenoid system and the resonance graph, Discr. Appl. Math. 157 (2009) 2565–2569.
  * [20] A. Taranenko, Daisy cubes: a characterization and a generalization, European J. Combin. 85 (2020), 103058, 10 pp.
  * [21] A. Taranenko, P. Žigert Pleteršek, Resonant sets of benzenoid graphs and hypercubes of their resonance graphs, MATCH Commun. Math. Comput. Chem. 68 (2012) 65–77.
  * [22] A. Vesel, Characterization of resonance graphs of catacondensed hexagonal graphs, MATCH Commun. Math. Comput. Chem. 53 (2005) 195–208.
  * [23] A. Vesel, Efficient proper embedding of a daisy cube, Ars Math. Contemp. 21 (2021) art. no. P2.07.
  * [24] H. S. Wilf, The number of maximal independent sets in a tree, SIAM J. Alg. Disc. Meth. 7 (1986) 125–130.
  * [25] H. Zhang, $Z$-transformation graphs of perfect matchings of plane bipartite graphs: a survey, MATCH Commun. Math. Comput. Chem. 56 (2006) 457–476.
  * [26] F. Zhang, R. Chen, A theorem concerning polyhex graphs, MATCH Commun. Math. Comput. Chem. 19 (1986) 176–188.
  * [27] F. Zhang, X. Guo, R. Chen, $Z$-transformation graph of perfect matching of hexagonal systems, Discrete Math. 72 (1988) 405–415.
  * [28] H. Zhang, P. C. B. Lam, W. C. Shiu, Resonance graphs and a binary coding for the 1-factors of benzenoid systems, SIAM J. Discrete Math. 22 (2008) 971–984.
  * [29] H. Zhang, L. Ou and H. Yao, Fibonacci-like cubes as $Z$-transformation graphs, Discrete Math. 309 (2009) 1284–1293.
  * [30] H. Zhang, F. Zhang, The rotation graphs of perfect matchings of plane bipartite graphs, Discrete Appl. Math. 73 (1997) 5–12.
  * [31] H. Zhang, F. Zhang, Plane elementary bipartite graphs, Discrete Appl. Math. 105 (2000) 291–311.
  * [32] H. Zhang, F. Zhang, H. Yao, $Z$-transformation graphs of perfect matchings of plane bipartite graphs, Discrete Math. 276 (2004) 393–404.
  * [33] P. Žigert Pleteršek, Resonance graphs of kinky benzenoid systems are daisy cubes, MATCH Commun. Math. Comput. Chem. 80 (2018) 207–214.