# Enumerating Chemical Graphs with Mono-block 2-Augmented Tree Structure from
Given Upper and Lower Bounds on Path Frequencies

Yuui Tamura1 Yuhei Nishiyama1 Chenxi Wang1 Yanming Sun1 Aleksandar Shurbevski1
Hiroshi Nagamochi1 Tatsuya Akutsu2

1 Department of Applied Mathematics and Physics,
Kyoto University, Kyoto 606-8501, Japan.
{y.tamura, y.nishiyama, chenxi, sun.ym, shurbevski<EMAIL_ADDRESS>2 Bioinformatics Center, Institute for Chemical Research,
Kyoto University, Uji 611-0011, Japan.
<EMAIL_ADDRESS>
> Abstract.  We consider a problem of enumerating chemical graphs from given
> constraints concerning their structures, which has an important application
> to a novel method for the inverse QSAR/QSPR recently proposed. In this
> paper, the structure of a chemical graph is specified by a feature vector
> each of whose entries represents the frequency of a prescribed path. We call
> a graph a 2-augmented tree if it is obtained from a tree (an acyclic graph)
> by adding edges between two pairs of non-adjacent vertices. Given a set of
> feature vectors as the interval between upper and lower bounds of feature
> vectors, we design an efficient algorithm for enumerating chemical
> 2-augmented trees that satisfy the path frequency specified by some feature
> vector in the set. We implemented the proposed algorithm and conducted some
> computational experiments.

##  1 Introduction

Development of novel drugs is one of the major goals in chemoinformatics and
bioinformatics. To achieve this purpose, it is important not only to
investigate common chemical properties over chemical compounds having certain
structural pattern [6, 7, 16], but also to enumerate all the chemical
compounds having a specified structural pattern. The enumeration of chemical
compounds has a long history, which can be traced back to Cayley [8], who
addressed the enumeration of structural isomers of alkanes in the 19th
century.

A multigraph is a graph that can have multiple edges between the same pair of
vertices, where multiple edges represent double bonds or triple bonds in a
chemical compound. Let us call a multigraph a $k$-augmented tree if it is
connected and it becomes a tree possibly with multiple edges after removing
edges between $k$ pairs of adjacent vertices, where a $0$-augmented tree and a
$1$-augmented tree are also called an acyclic graph and a monocyclic graph,
respectively. In the $97,092,888$ chemical compounds in the PubChem database,
the ratio of the number of chemical compounds of a $k$-augmented tree
structure to that of all registered chemical compounds is around $2.9\%$,
$13.3\%$, $28.2\%$, $24.2\%$ and $16.0\%$ for $k=0,1,2,3$ and $4$,
respectively.

Quantitative Structure Activity/Property Relationships (QSAR/QSPR) analysis is
a major approach for computer-aided drug design. In particular, inverse
QSAR/QSPR plays an important role [17, 22], which is to infer chemical
structures from given chemical activities/properties. As in many other fields,
Artificial Neural Network (ANN) and deep learning technologies have recently
been applied to inverse QSAR/QSPR. In these approaches, new chemical graphs
are generated by solving a kind of inverse problems on neural networks, where
neural networks are trained using known chemical compound/activity pairs.
However, there was no mathematical guarantee for the existence of solutions in
these approaches. In order to solve the inverse problem mathematically, a
novel approach has been proposed by Akutsu and Nagamochi [2] for ANNs, using
mixed integer linear programming (MILP).

Recently Chiewvanichakorn et al. [9], Azam et al. [3, 4] proposed a novel
framework for the inverse QSAR/QSPR by combining the MILP-based formulation of
the inverse problem on ANNs [2] and efficient enumeration of acyclic graphs
and monocyclic graphs. This combined framework for inverse QSAR/QSPR mainly
consists of two phases. The first phase defines a function $f$ that converts
each chemical graph $G$ into a feature vector $f(G)$ that consists of several
descriptors on the structure of $G$ and then solves (1) Prediction Problem,
where a prediction function $\psi_{\mathcal{N}}$ on a chemical property $\pi$
is constructed with an ANN $\mathcal{N}$ using a data set of chemical
compounds $G$ and their values $a(G)$ of $\pi$. The second phase solves (2)
Inverse Problem, where (2-a) given a target value $y^{*}$ of the chemical
property $\pi$, a feature vector $x^{*}$ is inferred from the trained ANN
$\mathcal{N}$ so that $\psi_{\mathcal{N}}(x^{*})$ is close to $y^{*}$ and
(2-b) then a set of chemical structures $G^{*}$ such that $f(G^{*})=x^{*}$ is
enumerated. Methods applied to the case of inferring acyclic or monocyclic
chemical graphs have been implemented as computer programs, through which
chemical graphs $G^{*}$ are inferred from given target values $y^{*}$ of
actual chemical properties such as heat of atomization, heat of formation,
boiling point and octanol/water partition coefficient [3, 9, 4]. In this
framework, an efficient algorithm for enumerating acyclic or monocyclic graphs
that satisfy given descriptors is an important building block to solve (2-b).
A natural next target to apply the framework for the inverse QSAR/QSPR is to
construct a system of inferring chemical 2-augmented trees. To attain this, we
design an efficient algorithm for enumerating chemical 2-augmented trees.

Some useful tools such as MOLGEN [12], OMG [20], and similar, have been
developed and are available for enumeration of chemical graphs. However, they
are not always very efficient in enumerating chemical graphs that satisfy a
given condition on structures such as frequency of certain types of subgraphs,
because they treat general graph structures. In particular, it is known that
the number of molecules (i.e., chemical graphs) with up to 30 atoms (vertices)
C, N, O, and S, may exceed $10^{60}$ [5].

Fujiwara et al. [11] and Ishida et al. [14] studied the enumeration of acyclic
chemical graphs that satisfy a given feature vector which specifies the
frequency of all paths of up to a prescribed length in a chemical compound to
be constructed. Their results have been recognized as establishing new
methodologies in this track of research in chemoinformatics [25]. Instead of
giving a single feature vector $f$ on the frequency of prescribed paths,
Shimizu et al. [21] treated a set $F$ of feature vectors on path frequency
given as the set of all vectors between a pair of upper and lower feature
vectors, and designed a branch-and-bound algorithm of enumerating acyclic
chemical graphs each of which satisfies some feature vector $f$ in the set
$F$. Afterward Suzuki et al. [23] proposed an improved and more efficient
algorithm. For monocyclic graphs, Suzuki et al. [24] proposed an efficient
algorithm that constructs a monocyclic chemical graph by adding an edge to an
acyclic chemical graph. Such acyclic chemical graphs in turn, can be obtained
by an existing algorithm [11, 23]. The above-mentioned algorithms for
enumerating acyclic and monocyclic chemical graph with given path frequencies
now play a crucial role in the novel methods for inverse QSAR/QSPR [3, 9, 4].

For 2-augmented trees, we distinguish two types: (i) those with two edge-
disjoint cycles and (ii) those with a single bi-connected component, where
every two cycles share an edge. We call a 2-augmented tree in type (ii) a
mono-block 2-augmented tree. In this paper, we design an algorithm for
enumerating mono-block 2-augmented trees that satisfy given upper and lower
bounds of path frequencies of graphs. We implemented the proposed algorithm
and conducted some computational experiments.

##  2 Preliminaries on Graphs

This section reviews some basic definitions on graphs and introduces the
notion of chemical graphs as used in this paper.

###  2.1 Multigraphs

Let $\mathbb{Z}_{+}$ denote the set of positive integers. For two integers $a$
and $b$, let $[a,b]$ denote the set of all integers $i$ with $a\leq i\leq b$.

A graph is defined to be an ordered pair $(V,E)$ of a finite set $V$ of
vertices and a finite set $E$ of edges. In this paper, we do not consider
self-loops, and an edge in $E$ joining two vertices $u,v\in V$ is denoted by
$uv$.

Let $G$ be a graph. We denote the vertex set and the edge set of $G$ by $V(G)$
and $E(G)$, respectively. An ordered pair $(V^{\prime},E^{\prime})$ of subsets
$V^{\prime}\subseteq V(G)$ and $E^{\prime}\subseteq E(G)$ is called a subgraph
of $G$ if $(V^{\prime},E^{\prime})$ forms a graph, i.e., $\\{u,v\in V\mid
uv\in E^{\prime}\\}\subseteq V^{\prime}$. We say that a subset $X\subseteq
V(G)$ induces a subgraph $G^{\prime}$ if $V(G^{\prime})=X$ and $E(G^{\prime})$
contains every edge in $E(G)$ between two vertices in $X$.

We call a graph where each vertex and edge has a unique name or an index a
labeled graph. Throughout the paper, graphs are considered to be labeled, to
distinguish or enumerate vertices, edges or some other structures in a graph.
Figure 1(a) shows an example of a labeled graph. A rooted graph is a graph in
which either a vertex or an edge is designated as a root.

Figure 1:  (a) An example of a labeled graph, each vertex is labeled with a
unique label $v_{i}$, $i=1,2,\dots,19$, and each edge with a unique label
$e_{j}$, $j=1,2,\dots,25$, (b) A monocyclic graph $G$ with a unique cycle $C$,
where the pendent tree $G\langle v\rangle$ for a vertex $v\in V(C)$ is the
subtree enclosed by a dashed line.

A graph is called a multigraph when there can be more than one edge between
the same pair of endvertices. Let $G$ be a multigraph. For a vertex $v\in
V(G)$, we call the number of edges incident to $v$ the degree of $v$ and
denote it by ${\rm deg}(v)$. Let $\\{u,v\\}\subseteq V(G)$. The _multiplicity_
, i.e., the number of edges, between two vertices $u$ and $v$ is denoted by
${\rm mul}_{G}(u,v)$, where for two non-adjacent vertices $u$ and $v$, it
holds ${\rm mul}_{G}(u,v)=0$. We refer to the set of ${\rm
mul}_{G}(u,v)~{}(\geq 0)$ simple edges with endvertices $u$ and $v$ as a
multiple edge with multiplicity ${\rm mul}_{G}(u,v)$. Let $\overline{E}(G)$
denote the set of pairs $\\{u,v\\}\subseteq V(G)$ with ${\rm mul}_{G}(u,v)=0$.
For a pair of adjacent vertices $u$ and $v$, let $G-uv$ denote the graph
$G^{\prime}$ obtained by removing ${\rm mul}_{G}(u,v)$ simple edges between
$u$ and $v$ from $G$. Conversely, let $G+q\cdot uv$ denote the graph
$G^{\prime}$ obtained by adding $q\in\mathbb{Z}_{+}$ simple edges between $u$
and $v$, i.e., ${\rm mul}_{G^{\prime}}(u,v)={\rm mul}_{G}(u,v)+q$. In
particular, we denote $G+1\cdot uv$ by $G+uv$. If $G$ is clear from the
context, then we denote ${\rm mul}_{G}(u,v)$ by ${\rm mul}(u,v)$.

For a nonnegative integer $k$, a graph $P$ which consists of $k+1$ distinct
vertices $v_{0},v_{1},$ $\dots,$ $v_{k}$ and $k$ multiple edges
$v_{i}v_{i+1},~{}i\in[1,k-1]$, is called a path (or a path of length $k$), and
is denoted by $P=(v_{0},v_{1},\ldots,v_{k})$. The length, i.e., the number of
edges in a path $P$ is also denoted by $|P|$. A graph $C$ which consists of a
path $(v_{0},v_{1},\ldots,v_{\ell})$ of length $\ell\geq 2$ and a multiple
edge between $v_{\ell}$ and $v_{0}$ is called a cycle and is denoted by
$C=(v_{0},v_{1},\ldots,v_{\ell},v_{0})$. In this paper, a graph which consists
of two vertices and two edges between them is not considered as a cycle.

A block in $G$ is defined to be a maximal vertex subset $X\subseteq V(G)$ such
that for any two vertices $u,v\in X$, there is a cycle of $G$ that passes
through $u$ and $v$. We call $G$ a mono-block graph if $G$ has exactly one
block $X$ with $|X|\geq 2$.

A connected multigraph with no cycles is called a multitree. Every multitree
$T$ has either a vertex $v$ or an adjacent vertex pair $\\{v,v^{\prime}\\}$
removal of which leaves no connected component with more than
$\lfloor|V(T)|/2\rfloor$ vertices [15]. Such a vertex or an adjacent vertex
pair is called a centroid, where a centroid $v$ is called a unicentroid and a
centroid $\\{v,v^{\prime}\\}$ is called a bicentroid.

Let $T$ be a rooted multitree and $v\in V(T)$. Let $u\in V(T)$ be a vertex
such that $v$ is on the unique path between $u$ and the root. We call $u$ a
descendant of $v$ and call $v$ an ancestor of $u$. In particular, if $u$ and
$v$ are adjacent, we call $u$ a child of $v$ and call $v$ the parent of $u$.
The parent of $v$ is denoted by ${\rm p}(v)$. The set of children of a vertex
$v$ is denoted by ${\text{\sc Ch}}(v)$. The depth of $v$ represents the length
of the unique path between $v$ and the root, and is denoted by ${\rm d}(v)$.
If $v$ is the root vertex or an endvertex of the root edge, then $v$ has no
parent, and ${\rm d}(v)=0$. We denote by $T_{v}$ the subtree of $T$ induced by
$v$ and the set of descendants of $v$. For an edge $vw\in E(T)$ such that
$w={\rm p}(v)$, we denote by $T_{wv}$ the subtree of $T$ induced by $w$, $v$,
and the set of descendants of $v$. That is, $T_{wv}$ consists of the subtree
$T_{v}$ and the vertex $w={\rm p}(v)$ joined by a multiple edge between $v$
and $w$ with multiplicity ${\rm mul}_{T}(v,w)$. We regard $T_{wv}$ to be
rooted at $w$.

For a connected multigraph $G$ with at least one cycle and a vertex $v\in
V(G)$ such that $v$ is included in some of the cycles in $G$, the pendent tree
$G\langle v\rangle$ of vertex $v$ is defined to be the subgraph $T$ of $G$
induced by $v$ and the set of vertices reachable from $v$ without passing
through any edge in a cycle of $G$, where $T$ becomes a tree, possibly only
consisting of vertex $v$. We treat $G\langle v\rangle$ as a tree rooted at
$v$. For a vertex $u\in V(G\langle v\rangle)$ we define $\rho_{G}(u)=v$. For
convenience, for a pendent tree $T=G\langle v\rangle$ and a vertex $u\in
V(G\langle v\rangle)$, we denote the subtree $T_{u}$ of $G\langle v\rangle$
rooted at $u$ by $G\langle u\rangle$. In addition, for the parent
$w=\mathrm{p}(u)$ of $u$ in $G\langle v\rangle$, we denote by $G\langle
w,u\rangle$ the rooted tree $T_{wu}$.

An example of a pendent tree is illustrated in Fig. 1(b). For a multigraph $G$
with $n$ vertices, we say that a pendent tree of $G$ is _exceeding_ if it has
at least $n/3$ vertices.

###  2.2 $k$-Augmented Trees

A $k$-augmented tree with $n$ vertices is a connected multigraph such that the
number of pairs of adjacent vertices is $(n-1)+k$, i.e., it is constructed
from a multiree with $n$ vertices by adding edges between $k$ pairs of non-
adjacent vertices.

####  2.2.1 1-Augmented Trees

Let $G$ be a monocyclic graph, which has a unique cycle $C$. Throughout this
draft we will also call 1-augmented trees _monocyclic graphs_. For a vertex
$u\in V(G)$, let $\rho_{G}(u)$ denote the vertex $v\in V(C)$ such that $u\in
V(G\langle v\rangle)$. Note that in the case when $u\in V(C)$, it holds that
$u=\rho_{G}(u)$. See Fig. 1(b) for an example of a monocyclic graph, where
$\rho_{G}(u)$ is denoted for a vertex $u$.

For a monocyclic graph $G$ and two vertices $u,v\in V(G)$ such that
$\rho_{G}(u)=\rho_{G}(v)$ (i.e., $u$ and $v$ are contained in the same pendent
tree of $G$), let $P(u,v)$ denote the unique path in $G$ between $u$ and $v$.

####  2.2.2 Mono-block 2-Augmented Trees

Let $H$ be a mono-block $2$-augmented tree, and $C_{1}$, $C_{2}$, and $C_{3}$
be the three distinct cycles of $H$. We observe that there are exactly two
vertices contained in all of the cycles of $H$. We call these vertices
junctions. We call a pair of a junction $u$ and a neighbor of $u$ on some of
the cycles of $H$ a junction pair. Note that the number of junction pairs in
one mono-block 2-augmented tree is either six or five (see Fig. 2 (a) and (b),
respectively) . Let $u$ and $u^{\prime}$ be the junctions of $H$. For
$i\in[1,3]$, we define $P(u,u^{\prime};C_{i})$ to be the unique path from $u$
to $u^{\prime}$ that is not in $C_{i}$. Note that either
$P(u,u^{\prime};C_{i})$ is itself a junction pair, or it contains exactly two
junction pairs. See Fig. 2 for an example of mono-block $2$-augmented trees
and junctions.

Figure 2:  Mono-block $2$-augmented trees $H_{a}$ and $H_{b}$ with junctions
$u$ and $u^{\prime}$. (a) The pair $\\{u,x\\}$ is one of the junction pairs of
$H_{a}$. The path $P(u,u^{\prime};C_{1})$ is drawn in bold. (b) The path
$P(u,u^{\prime};C_{1})$ drawn in bold consists of a single edge $uu^{\prime}$.

##  3 Problem Formulation

In this section, we formalize the problem to be addressed in this paper.

###  3.1 Chemical Graphs

To treat chemical compounds as multigraphs, we introduce a color for every
vertex in a graph. Colors represent chemical elements, such as O, N, or C. Let
us denote the set of colors by $\Sigma$, and the color of a vertex $v$ by
${\rm col}(v)$. The valence of a chemical element $c\in\Sigma$ is denoted by
an integer function ${\rm val}(c)\in\mathbb{Z}_{+}$. The size of a bond
between two adjacent atoms is indicated by the edge multiplicity between the
two vertices that correspond to those atoms. A multigraph $G$ is called a
$\Sigma$-colored graph if each vertex $v\in V(G)$ is assigned a color ${\rm
col}(v)\in\Sigma$. A chemical compound can be viewed as a $\Sigma$-colored
multigraph without self-loops, where vertices and colors represent atoms and
elements, respectively. Throughout this paper, we call $\Sigma$-colored
multigraphs without self-loops chemical graphs.

Let $G$ be a chemical graph. Chemical compounds, especially organic compounds,
are rich with hydrogen atoms. Since the valence of hydrogen is $1$, we can
determine the structure of chemical graphs without considering hydrogen atoms.
On this ground, we suppress hydrogen in order to enumerate chemical graphs
more quickly. As a result, for some vertex $v$ in a hydrogen-suppressed
chemical graph, the degree ${\rm deg}(v)$ may be smaller than the valence
${\rm val}({\rm col}(v))$. For a vertex $v\in V(G)$, we define the residual
degree of $v$ to be ${\rm val}({\rm col(v)})-{\rm deg}(v)$ and denote it by
$\mathrm{res}(v)$. In a hydrogen-suppressed chemical graph, for a vertex $v$,
$\mathrm{res}(v)$ represents the number of hydrogen atoms adjacent to $v$ in
the corresponding chemical compound.

###  3.2 Isomorphism on Chemical Multigraphs

In enumerating chemical graphs, we must avoid duplication of equivalent
graphs. For example, two chemical graphs $G$ and $G^{\prime}$ may have the
same graph structure, and imply the same chemical compound even if they are
different as labeled graphs. This case is formalized by the notion of
_isomorphism_ as follows. Let $G=(V,E)$ and
$G^{\prime}=(V^{\prime},bE^{\prime})$ be two chemical multigraphs. The
following bijection $\psi$ from $V(G)$ to $V(G^{\prime})$ is called an
isomorphism from $G$ to $G^{\prime}$:

  * (i)

for each vertex $x\in V(G)$, it holds that ${\rm col}(x)={\rm col}(\psi(x))$;
and

  * (ii)

for each pair $\\{x,y\\}\subseteq V(G)$, it holds that ${\rm
mul}_{G}(x,y)={\rm mul}_{G^{\prime}}(\psi(x),\psi(y))$.

If there exists an isomorphism from $G$ to $G^{\prime}$, then we say that $G$
and $G^{\prime}$ are isomorphic. We write $G\approx G^{\prime}$ if $G$ and
$G^{\prime}$ are isomorphic, and write $G\not\approx G^{\prime}$ otherwise.
For two sets $\mathcal{G}$ and $\mathcal{G}^{\prime}$ of chemical graphs, we
say that $\mathcal{G}^{\prime}$ represents $\mathcal{G}$ if
\- for each chemical graph $G\in\mathcal{G}$, there is a chemical graph
$G^{\prime}\in\mathcal{G}^{\prime}$ such that $G\approx G^{\prime}$; and
\- for any two chemical graphs
$G^{\prime}_{1},G^{\prime}_{2}\in\mathcal{G}^{\prime}$, it holds that
$G^{\prime}_{1}\not\approx G^{\prime}_{2}$.

An automorphism of a chemical graph $G$ is defined to be an isomorphism $\psi$
from $V(G)$ to $V(G)$ itself.

In addition, for two graphs $G$ and $G^{\prime}$ and vertex subsets
$X\subseteq V(G)$ and $Y\subseteq V(G^{\prime})$ such that $|X|=|Y|$, if there
exists an isomorphism $\psi$ from $V(G)$ to $V(G^{\prime})$ such that for each
vertex $x\in X$ it holds that $\psi(x)\in Y$, we say that $G$ and $G^{\prime}$
are _$(X,Y)$ -isomorphic_. In the case when the sets $X$ and $Y$ are
singletons, i.e. $X=\\{x\\}$ and $Y=\\{y\\}$ and $G$ and $G^{\prime}$ are
$(X,Y)$-isomorphic, we may write that they are $(x,y)$-isomorphic. Finally, if
$G$ is a graph rooted at vertex $v_{r}$ and $G^{\prime}$ is rooted at
$v^{\prime}_{r}$ and they are $(v_{r},v^{\prime}_{r})$-isomorphic, then we say
that they are rooted isomorphic and denote this by
$G\underset{r}{\approx}G^{\prime}$.

###  3.3 Feature Vectors

In this paper, “feature vectors” represent occurrences of paths in a graph. To
specify a feature vector space, we fix three parameters: a set $\Sigma$ of
colors; the maximum multiplicity $d\geq 1$ among all pairs of vertices in
multigraphs to be enumerated; and the maximum length $K\geq 0$ of the path
structures to be specified.

Let $c_{0},c_{1},\dots,c_{K}\in\Sigma$ be $K+1$ colors and
$m_{1},m_{2},\dots,m_{K}\in[1,d]$ be $K$ integers, where it may hold that
$c_{i}=c_{j}$ or $m_{i}=m_{j}$ for some $i$ and $j$. We call an alternating
sequence $t=(c_{0},m_{1},c_{1},\dots,m_{K},c_{K})$ a colored sequence of
length $|t|=K$. We denote the set of all colored sequences with length $K$ by
$\Sigma^{K,d}$, and the union of
$\Sigma^{0,d},\Sigma^{1,d},\dots,\Sigma^{K,d}$ by $\Sigma^{\leq K,d}$. For a
colored sequence $t=(c_{0},m_{1},c_{1},\dots,m_{K},c_{K})\in\Sigma^{K,d}$, let
${\rm rev}(t)$ denote its reverse sequence
$(c_{K},m_{K},c_{K-1},\dots,m_{1},c_{0})\in\Sigma^{K,d}$.

Let a chemical graph $P$ be a path $P=(v_{0},v_{1},\ldots,v_{K})$ of length
$K$ with root $v_{0}$. We define the colored sequence
$\gamma(P)\in\Sigma^{K,d}$ of $P$ to be

$\gamma(P)\triangleq({\rm col}(v_{0}),{\rm mul}_{P}(v_{0},v_{1}),{\rm
col}(v_{1}),\ldots,{\rm mul}_{P}(v_{K-1},v_{K}),{\rm col}(v_{K})).$

Let $G$ be a chemical graph. For a colored sequence $t\in\Sigma^{\leq K,d}$,
the frequency ${\rm frq}(t,G)$ of $t$ in $G$ is defined to be the number of
vertex-rooted subgraphs $G^{\prime}$ of $G$ such that
$G^{\prime}\underset{r}{\approx}P$ for a rooted path $P$ with $\gamma(P)=t$.
We define the feature vector ${\bf f}(G)$ of level $K$ of $G$ to be the
$|\Sigma^{\leq K,d}|$-dimensional vector such that ${\bf f}(G)[t]={\rm
frq}(t,G)$ for each colored sequence $t\in\Sigma^{\leq K,d}$.

Given a color set $\Sigma$ and integers $d$ and $K$, the set of $|\Sigma^{\leq
K,d}|$-dimensional vectors whose entries are nonnegative integers is called a
feature vector space and is denoted by ${\bf f}(\Sigma,K,d)$. Equivalently,
each vector $\mathbf{g}\in\mathbf{f}(\Sigma,K,d)$ is a mapping
$\mathbf{g}:\Sigma^{\leq K,d}\to\mathbb{Z}_{+}$. For two vectors
$\mathbf{g},\mathbf{g}^{\prime}\in\mathbf{f}(\Sigma,K,d)$, we write
$\mathbf{g}\leq\mathbf{g}^{\prime}$ if for each entry $t\in\Sigma^{\leq K,d}$,
it holds that $\mathbf{g}[t]\leq\mathbf{g}^{\prime}[t]$. For two given vectors
${\bf g},{\bf g^{\prime}}\in{\bf f}(\Sigma,K,d)$, a chemical graph $G$ is
called feasible if ${\bf g}\leq{\bf f}(G)\leq{\bf g^{\prime}}$ and
$\mathrm{res}(v)\geq 0$ holds for all vertices $v\in V(G)$. Let
$\mathcal{G}({\bf g},{\bf g^{\prime}})$ denote the set of all chemical graphs
feasible to $({\bf g},{\bf g^{\prime}})$.

##  4 Problem of Enumerating Mono-block $2$-Augmented Trees

Let $\mathcal{G}_{1}$ denote the set of $\Sigma$-colored labeled monocyclic
graphs, and $\mathcal{G}_{2}$ denote the set of $\Sigma$-colored labeled mono-
block $2$-augmented trees. Note that each of $\mathcal{G}_{1}$ and
$\mathcal{G}_{2}$ conceptually contains infinitely many labeled graphs unless
a way of expressing labeled graphs is restricted.

For two given vectors ${\bf g}_{\ell}$ and ${\bf g}_{u}$, the set of feasible
graphs $H\in\mathcal{G}_{2}$ is denoted by $\mathcal{G}_{2}({\bf
g}_{\ell},{\bf g}_{u})$. Our goal in this paper is to construct a set
$\mathcal{G}^{\prime}_{2}$ that represents the set $\mathcal{G}_{2}({\bf
g}_{\ell},{\bf g}_{u})$. Since we can use an existing algorithm to obtain a
set $\mathcal{G}^{\prime}_{1}$ that represents $\mathcal{G}_{1}$ (for example,
the algorithm due to Suzuki et al. [24]), we design an algorithm to our goal
so that our target set $\mathcal{G}^{\prime}_{2}$ is constructed
(I) by adding some number $p\in[1,\min\\{\mathrm{res}(x),\mathrm{res}(y)\\}]$
of edges between some non-adjacent vertices $x$ and $y$ in each
$\Sigma$-colored labeled monocyclic graph $H$ in $\mathcal{G}^{\prime}_{1}$;
and
(II) by discarding from the graphs $H$ those that are infeasible, i.e., ${\bf
g}_{\ell}>{\bf f}(H)$ or ${\bf f}(H)>{\bf g}_{u}$.

We design procedures for tasks (I) and (II) separately. In the rest of this
subsection, we examine the task (I). Testing if a graph $H\in\mathcal{G}_{2}$
satisfies ${\bf g}_{\ell}\leq{\bf f}(H)\leq{\bf g}_{u}$ can be handled in a
relatively easy way. We remark that all non-isomorphic $\Sigma$-colored
labeled monocyclic graphs might not be needed for us to generate our target
set $\mathcal{G}^{\prime}_{2}$ which is restricted by bounds ${\bf g}_{\ell}$
and ${\bf g}_{u}$. In other words, we may be able to introduce a pair $({\bf
g}^{\prime}_{\ell},{\bf g}^{\prime}_{u})$ of lower and upper feature vectors
on $\Sigma$-colored labeled monocyclic graphs so that a smaller set of non-
isomorphic $\Sigma$-colored labeled monocyclic graphs can produce all
necessary graphs in our target set $\mathcal{G}^{\prime}_{2}$.

For two vectors ${\bf g}_{1}$ and ${\bf g}_{2}$, the set of feasible graphs in
$\mathcal{G}_{1}$ is denoted by $\mathcal{G}_{1}({\bf g}_{1},{\bf g}_{2})$.
Following the idea of Suzuki et al. [24], we modify a given lower vector ${\bf
g}_{\ell}$ into a vector ${\bf g}^{\dagger}_{\ell}$ so that any graph in
$\mathcal{G}_{2}({\bf g}_{\ell},{\bf g}_{u})$ can be constructed from some
graph in $\mathcal{G}_{1}({\bf g}^{\dagger}_{\ell},{\bf g}_{u})$. For a given
lower vector ${\bf g}_{\ell}\in{\bf f}(\Sigma,K,d)$, we define ${\bf
g}^{\dagger}_{\ell}\in{\bf f}(\Sigma,K,d)$ as follows:

  * (i)

for each $t\in\Sigma^{0,d}$, let ${\bf g}^{\dagger}_{\ell}[t]={\bf
g}_{\ell}[t]$;

  * (ii)

for each $t=(c,m,c^{\prime})\in\Sigma^{1,d}$, let

$\mathbf{g}_{\ell}^{\dagger}[t]=\left\\{\begin{array}[]{ll}\max\\{0,\mathbf{g}_{\ell}[t]-1\\},&\text{if}~{}c\neq
c^{\prime}\\\
\max\\{0,\mathbf{g}_{\ell}[t]-2\\},&\text{if}~{}c=c^{\prime},\text{
and}\end{array}\right.$

  * (iii)

for each $t\in\Sigma^{\leq K,d}\setminus\Sigma^{\leq 1,d}$, let ${\bf
g}^{\dagger}_{\ell}[t]=0$.

######  Lemma 1.

For a set $\Sigma$ of colors and integers $K\geq 0$ and $d\geq 1$, let the
vectors ${\bf g}_{u},{\bf g}_{\ell}\in{\bf f}(\Sigma,K,d)$ be such that ${\bf
g}_{\ell}\leq{\bf g}_{u}$, and $H\in\mathcal{G}_{2}({\bf g}_{\ell},{\bf
g}_{u})$. Then, for each junction pair $\\{x,y\\}\subseteq V(H)$, it holds
that $H-xy\in\mathcal{G}_{1}({\bf g}^{\dagger}_{\ell},{\bf g}_{u})$.

###### Proof.

Let $\\{x,y\\}$ be a junction pair in $H$. Let $G$ be the graph $H-xy$. We
show that $G\in\mathcal{G}_{1}({\bf g}^{\dagger}_{\ell},{\bf g}_{u})$ i.e.,
$G$ is a graph in $\mathcal{G}_{1}$ with ${\bf g}^{\dagger}_{\ell}\leq{\bf
f}(G)\leq{\bf g}_{u}$ and $\mathrm{res}(v)\geq 0$ for each vertex $v\in V(G)$.
Obviously, $G=H-xy$ is a graph in $\mathcal{G}_{1}$ because removing from $H$
all edges between a junction pair leaves only one cycle in $G$.

Since $H\in\mathcal{G}_{2}({\bf g}_{\ell},{\bf g}_{u})$, we have ${\bf
g}_{\ell}\leq{\bf f}(H)\leq{\bf g}_{u}$. First we check the upper bound of
${\bf f}(G)$. Since removing all edges between $x$ and $y$ does not increase
the frequency of any colored sequence, it holds that ${\rm frq}(t,G)\leq{\rm
frq}(t,H)$ for any colored sequence $t$. Hence it holds that ${\bf
f}(G)\leq{\bf f}(H)\leq{\bf g}_{u}$. Next we check the lower bound of ${\bf
f}(G)$. For a colored sequence $t\in\Sigma^{0,d}$, we consider the entry ${\bf
f}(G)[t]$. We have ${\bf f}(G)[t]={\bf f}(H)[t]={\bf g}_{\ell}[t]={\bf
g}^{\dagger}_{\ell}[t]$ for all colored sequences $t\in\Sigma^{0,d}$, since
removing edges does not change the frequency of colored sequences of length
$0$. A colored sequence $t\in\Sigma^{1,d}$ is given by $(c,m,c^{\prime})$, and
we have the following observations: If $t=\gamma(xy)$ or $t=\gamma(yx)$ for
some path $xy$ in $H$, it holds that

${\bf f}(G)[t]=\left\\{\begin{array}[]{ll}\max\\{0,{\bf
f}(H)[t]-1\\}&\text{if}~{}t\neq{\rm rev}(t)\\\ \max\\{0,{\bf
f}(H)[t]-2\\}&\text{if}~{}t={\rm rev}(t);\end{array}\right.$

and otherwise, we have ${\bf f}(G)[t]={\bf f}(H)[t]$. For all colored
sequences $t\in\Sigma^{1,d}$, since ${\bf g}_{\ell}\leq{\bf f}(H)[t]$, it
holds that

${\bf f}(G)[t]\geq\left\\{\begin{array}[]{ll}\max\\{0,{\bf
g}_{\ell}[t]-1\\}&\text{if}~{}c\neq c^{\prime}\\\ \max\\{0,{\bf
g}_{\ell}[t]-2\\}&\text{if}~{}c=c^{\prime}.\end{array}\right.$

According to the definition of ${\bf g}^{\dagger}_{\ell}$, we have ${\bf
f}(G)[t]\geq{\bf g}^{\dagger}_{\ell}[t]$ for each colored sequence
$t\in\Sigma^{1,d}$. For a colored sequence $t\in\Sigma^{\leq
K,d}\setminus\Sigma^{\leq 1,d}$, it is clear from the definition of ${\bf
g}^{\dagger}_{\ell}$ that ${\bf f}(G)[t]\geq{\bf g}^{\dagger}_{\ell}[t]=0$.
From above, we have ${\bf g}^{\dagger}_{\ell}\leq{\bf f}(G)\leq{\bf g}_{u}$.

Finally, we prove that $\mathrm{res}(v)\geq 0$ for each vertex $v\in V(G)$.
Since $H$ is feasible, it holds that $\mathrm{res}(u)\geq 0$ for each vertex
$u\in V(H)$. Removing edges from $H$ does not decrease the residual degree of
any vertex. Hence it holds that $\mathrm{res}(v)\geq 0$ for each vertex $v\in
V(G)$. ∎

Lemma 1 states that for each graph $H\in\mathcal{G}_{2}({\bf g}_{\ell},{\bf
g}_{u})$, there is at least one monocyclic graph $G\in\mathcal{G}_{1}({\bf
g}^{\dagger}_{\ell},{\bf g}_{u})$, a pair $\\{x,y\\}\in\overline{E}(G)$, and
an integer $p$ giving $H$ as $G+p\cdot xy$. For this, we first generate all
monocyclic graphs in $\mathcal{G}_{1}({\bf g}^{\dagger}_{\ell},{\bf g}_{u})$.
Then we enumerate all mono-block $2$-augmented trees in $\mathcal{G}_{2}({\bf
g}_{\ell},{\bf g}_{u})$ by adding edges between pairs of non-adjacent vertices
in each of the given monocyclic graphs, where the pair of endvertices of the
newly added edges becomes a junction pair of the newly created mono-block
$2$-augmented tree. The problem to deal with in this paper is formalized as
follows.

Enumerating mono-block $2$-augmented trees from given monocyclic graphs with
given Upper and Lower Path Frequency

A set $\Sigma$ of colors, integers $K\geq 0$ and $d\geq 1$, two vectors ${\bf
g}_{u},{\bf g}_{\ell}\in{\bf f}(\Sigma,K,d)$ such that ${\bf g}_{\ell}\leq{\bf
g}_{u}$ and for all colored sequences $t\in\Sigma^{0,d}$ it holds that ${\bf
g}_{\ell}[t]={\bf g}_{u}[t]$, and a set $\mathcal{G}^{\prime}_{1}$ that
represents the set $\mathcal{G}_{1}({\bf g}^{\dagger}_{\ell},{\bf g}_{u})$.

A set $\mathcal{G}^{\prime}_{2}$ that represents the set $\mathcal{G}_{2}({\bf
g}_{\ell},{\bf g}_{u})$.

In the rest of the paper, we focus on designing an enumerating procedure for
the task (I).

###  4.1 Sketch of the Enumerating Procedure

Suppose that a set $\mathcal{G}^{\prime}_{1}=\\{G_{1},G_{2},\ldots,G_{q}\\}$
that represents the set $\mathcal{G}_{1}({\bf g}^{\dagger}_{\ell},{\bf
g}_{u})$ is given. When $\Sigma$-colored labeled mono-block $2$-augmented
trees are generated by adding a multiple edge $xy$ between a pair
$\\{x,y\\}\in\overline{E}(G)$ to each graph
$G_{i}\in\mathcal{G}^{\prime}_{1}$, we have to check whether the same graph
has already been generated in the process or not, i.e., whether a newly
generated graph $H=G_{i}+p\cdot xy\in\mathcal{G}_{2}$ is isomorphic to another
graph $H^{\prime}=G_{j}+q\cdot x^{\prime}y^{\prime}\in\mathcal{G}_{2}$ that
has already been obtained from some graph $G_{j}\in\mathcal{G}^{\prime}_{1}$.
We call the duplication arising when $H=G_{i}+p\cdot xy$ and
$H^{\prime}=G_{j}+q\cdot x^{\prime}y^{\prime}$ are isomorphic with $i\neq j$
_inter-duplication_ , and that when $H=G_{i}+p\cdot xy\approx
H^{\prime}=G_{i}+q\cdot x^{\prime}y^{\prime}$ _intra-duplication_. This
section provides some ideas on how to avoid such duplications without storing
all generated graphs and explicitly comparing the new one with each of them.

In enumeration algorithms, the concept of a family tree is widely employed
[18, 19, 24] in order to efficiently cope with inter-duplication. In order to
define a family tree for graphs, we need to define a parent-child relationship
between graph structures so that the parent structure of a given chemical
graph $H$ is uniquely determined from the topological structure of $H$. A
parent-child relationship over classes $\mathcal{H}$ and $\mathcal{G}$ of
chemical graphs is defined by an injective mapping
$\pi:\mathcal{H}\to\mathcal{G}$ as follows. Given a chemical graph
$H\in\mathcal{H}$, we define a labeled graph $G=\pi(H)\in\mathcal{G}$ so that
for any two chemical graphs $H_{1}$ and $H_{2}$ with $H_{1}\approx H_{2}$, it
holds $G_{1}\approx G_{2}$ with chemical graphs $G_{i}=\pi(H_{i})$, $i=1,2$,
implying that $\pi(H)$ is determined only from the topological structure of
$H$. For two chemical graphs $G\in\mathcal{G}$ and $H\in\mathcal{H}$ with
$G=\pi(H)$, the graph $G$ is called the parent of $H$ (the parent of $H$ as an
unlabeled graph which is unique up to automorphism), and the graph $H$ is
called a child of $G$. Let ${\text{\sc Ch}}_{\pi}(G)$ denote the set of
chemical graphs $H\in\mathcal{H}$ such that $G=\pi(H)$. Therefore, we easily
observe the next.

######  Lemma 2.

Let $\pi:\mathcal{H}\to\mathcal{G}$ be a parent-child relationship over
classes $\mathcal{H}$ and $\mathcal{G}$ of chemical graphs. For two chemical
graphs $G,G^{\prime}\in\mathcal{G}$, if $G\not\approx G^{\prime}$, then
${\text{\sc Ch}}_{\pi}(G)\cap{\text{\sc Ch}}_{\pi}(G^{\prime})=\emptyset$.

Then, Lemma 2 ensures that we do not need to explicitly check for inter-
duplication, that is, if a chemical graph $H\in\mathcal{G}_{2}$ that is a
child of a chemical graph $G_{i}\in\mathcal{G}_{1}$ is isomorphic to some
chemical graph $H^{\prime}\in\mathcal{G}_{2}$ generated from a chemical graph
$G_{j}\in\mathcal{G}_{1}$ with $i\neq j$.

This section closes by presenting a high level description of a procedure
that, given a chemical graph $G\in\mathcal{G}_{1}$ and a maximum multiplicity
$d$, constructs a set $\mathcal{G}_{2}(G,d)$ that represents the set of
chemical graphs in ${\text{\sc Ch}}_{\pi}(G)~{}(\subseteq\mathcal{G}_{2})$
with multiplicity at most $d$. For this, we will introduce
(I-a) an appropriate choice of a parent-child relationship
$\pi:\mathcal{G}_{2}\to\mathcal{G}_{1}$; and
(I-b) a way of avoiding intra-duplication from the same chemical graph
$G\in\mathcal{G}_{1}$.
The technical details on (I-a) and (I-b) will be discussed in Sections 7 and
8, respectively. Now the task (I) is divided into two subtasks, (I-a) and
(I-b).

We here explain ideas on (I-a) and (I-b). For (I-a), we define a parent-child
relationship $\pi:\mathcal{G}_{2}\to\mathcal{G}_{1}$ such that the parent
$\pi(H)$ of $H$ is a $\Sigma$-colored labeled monocyclic graph obtained from
$H$ by removing all $\mathrm{mul}_{H}\\{x,y\\}$ edges between a junction pair
$\\{x,y\\}$ which meets a certain condition derived in Section 7. The reason
why such a junction pair $\\{x,y\\}$ is carefully chosen is that the resulting
function $\pi$ must satisfy the definition of parent-child relationships over
classes $\mathcal{G}_{2}$ and $\mathcal{G}_{1}$.

To handle (I-b) for a chemical graph $G\in\mathcal{G}_{1}$, we call a subset
$F\subseteq\overline{E}(G)$ proper if
\- for any $H\in{\text{\sc Ch}}_{\pi}(G)$, there is a pair $\\{u,v\\}\in F$
and an integer $p\in[1,\min\\{\mathrm{res}(u),\mathrm{res}(v)\\}]$, such that
$H\approx G+p\cdot uv$; and
\- for two distinct pairs $\\{x,y\\},\\{u,v\\}\in F$, and integers
$p\in[1,\min\\{\mathrm{res}(x),\mathrm{res}(y)\\}]$ and
$q\in[1,\min\\{\mathrm{res}(u),\mathrm{res}(v)\\}]$ it holds that $G+p\cdot
xy\not\approx G+q\cdot uv$.
Section 8 provides a procedure for testing if a given pair
$\\{x,y\\}\in\overline{E}(G)$ belongs to a proper set $F$ after executing a
preprocessing to construct $F$.

With the above ideas, a procedure for constructing a set
$\mathcal{G}_{2}(G,d)$ is given as follows.

Procedure 1

1:An integer $d$ and a chemical graph $G\in\mathcal{G}_{1}$ with a unique
cycle $C$ and multiplicity at most $d$.

2:A set $\mathcal{G}_{2}(G,d)$ that represents the set of chemical graphs in
${\text{\sc Ch}}_{\pi}(G)~{}(\subseteq\mathcal{G}_{2})$ with multiplicity at
most $d$.

3:Execute a preprocessing to construct a proper set
$F\subseteq\overline{E}(G)$; /* by Procedure 5 in Section 8 */

4:for each pair $\\{x,y\\}\in F$ do

5: for each integer $p\in[1,\min\\{d,\mathrm{res}(x),\mathrm{res}(y)\\}]$ do

6: if $G+p\cdot xy$ is a child of $G$ /* tested by Procedure 4 in Section 7 */
then

7: Generate the mono-block $2$-augmented tree $G+p\cdot xy$ as part of the
output

8: end if

9: end for

10:end for.

##  5 Signature and Code

In order to define our parent-child relationship
$\pi:\mathcal{G}_{2}\to\mathcal{G}_{1}$ for the task (I-a), we introduce the
notion of “signature” of graphs.

For a class $\mathcal{G}$ of graphs, if we have a way of choosing a labeling
of each graph $G\in\mathcal{G}$ which is unique up to the graph’s
automorphism, then we can test the isomorphism of the two graphs directly by
comparing their labels. Such a labeling for a graph $G$ is called a canonical
form of $G$. Once such a canonical form for a class $\mathcal{G}$ of graphs is
obtained, we can easily encode each graph $G\in\mathcal{G}$ into a sequence
$\sigma(G)$, called the signature of $G$, such that two graphs
$G,G^{\prime}\in\mathcal{G}$ are isomorphic if and only if
$\sigma(G)=\sigma(G^{\prime})$.

###  5.1 Lexicographical Order

We fix a total order of the colors in $\Sigma$ arbitrarily, e.g., ${\tt
O}<{\tt N}<{\tt C}$. We introduce a lexicographical order among sequences with
elements in $\Sigma\cup\mathbb{Z}_{+}$ as follows. A sequence
$A=(a_{1},a_{2},\dots,a_{p})$ is lexicographically smaller than a sequence
$B=(b_{1},b_{2},\dots,b_{q})$ if there is an index $k\in[1,\min\\{p,q\\}]$
such that

  * (i)

$a_{i}=b_{i}$ for all $i\in[1,k]$; and

  * (ii)

$k=p<q$ or $a_{k+1}<b_{k+1}$ with $k<\min\\{p,q\\}$.

If $A$ is lexicographically smaller than $B$, then we denote $A\prec B$. If
$p=q$ and $a_{i}=b_{i}$ for all $i\in[1,p]$, then we denote $A=B$. Let
$A\preceq B$ mean that $A\prec B$ or $A=B$.

We often rely on lexicographically sorting a collection
$S=(s_{1},s_{2},\ldots,s_{k})$ of $k$ sequences. We will represent a
lexicographically ascending (resp., descending) order on collection $S$ by a
permutation $\pi:[1,k]\to[1,k]$ such that for $1\leq i<j\leq k$ it holds that
$s_{\pi(i)}\preceq s_{\pi(j)}$ (resp., $s_{\pi(j)}\preceq s_{\pi(i)}$).

For a collection $S$ of sequences, let us denote by $||S||=\sum_{s\in S}|s|$
the total length of the sequences in the collection $S$. A known algorithm due
to Aho et al. [1] can be used to lexicographically sort a collection $S$ of
sequences over an alphabet of size $n$ in $O(||S||+n)$ computation time.

###  5.2 Canonical Form and Signature of Trees

In this subsection, we review the concept of a canonical form of rooted trees
[18, 19].

####  5.2.1 Ordered Trees

An ordered tree is a rooted tree with a fixed total order among the children
of each vertex. By convention, we assume that the order of children in an
ordered tree is from left to right.

Let $T$ be a multitree with $n$ vertices, rooted at a vertex $r$. There may be
many different ordered trees on $T$. A canonical form of $T$ is given by an
adequately chosen ordered tree on $T$. When we conduct a depth-first-search,
we assume that we visit children from left to right. We denote the vertices of
$T$ by $v_{1},v_{2},\dots,v_{n}$, indexed in the order visited by a depth-
first-search starting from the root. Let $\tau$ be an ordered tree on $T$ and
let $\delta(\tau)$ denote the alternating _color-depth sequence_
$(c_{1},d_{1},\dots,c_{n},d_{n})$ that consists of the color $c_{i}$ and the
depth $d_{i}$ of the $i$-th vertex $v_{i}$ for $i\in[1,n]$. Let ${\rm
M}(\tau)$ denote the sequence $(m_{2},m_{3},\dots,m_{m})$ of the multiplicity
$m_{i}={\rm mul}(v_{i},{\rm p}(v_{i}))$ between the $i$-th vertex $v_{i}$ and
its parent ${\rm p}(v_{i})$ for $i\in[2,n]$.

####  5.2.2 Left-heavy Trees

A left-heavy tree of a rooted tree $T$ is an ordered tree $\tau$ that has the
lexicographically maximum code $\delta(\tau)$ among all ordered trees of $T$.
Note that a left-heavy tree has the following recursive structure: for every
vertex $v\in V(T)$, the subtree $T_{v}$ is also a left-heavy tree, and
$\delta(T_{v})$ and ${\rm M}(T_{v})$ are continuous subsequences of
$\delta(T)$ and ${\rm M}(T)$, respectively. We define the canonical form of a
rooted tree $T$ to be the left-heavy tree $\tau$ that has the
lexicographically maximum sequence ${\rm M}(\tau)$ among all left-heavy trees
of $T$, and define the _signature_ of $T$ to be
$\sigma(T)\triangleq(\delta(\tau),{\rm M}(\tau))$. We give a procedure to
calculate the signature $\sigma$ of a rooted tree as Procedure 2 in Section
5.2.3.

####  5.2.3 Calculating the Signature of Rooted Multi-Trees

For any two sequences $S_{1}$ and $S_{2}$, let $S_{1}\oplus S_{2}$ denote the
concatenation of $S_{1}$ and $S_{2}$. Given an ordered multi-tree $T$ on $n$
vertices indexed $v_{1},v_{2},\ldots,v_{n}$ as visited in a depth-first
traversal, let $\delta(T)=(c_{1},d_{1},c_{2},d_{2},\ldots,c_{n},d_{n})$ be its
color-depth sequence as defined in Section 5.2.2. For an integer $k\geq 1$ we
define the _$k$ -shift_ $\delta^{k}(T)$ of the sequence $\delta(T)$ to be the
sequence $(c_{1},d_{1}+k,c_{2},d_{2}+k,\ldots,c_{n},d_{n}+k)$ obtained by
adding $k$ to each of the depth entries of $\delta(T)$.

Let $T$ be an ordered multi-tree rooted at a vertex $r$, and let
$u_{1},u_{2},\ldots,u_{\deg(r)}$ denote the children of $r$ indexed according
to their left-to-right ordering. Let $\mathrm{M}(u_{i})$ denote
$\mathrm{mul}(u_{i},\mathrm{p}(u_{i}))\oplus\mathrm{M}(T(u_{i}))$ for each
$i\in[1,\deg(r)]$. Given the signatures
$\sigma(T(u_{i}))=(\delta(T(u_{i})),\mathrm{M}(T(u_{i})))$ for all
$i\in[1,\deg(r)]$, we devise a way to represent $\sigma(T)$ by
$\sigma(T(u_{i}))$ via the following observation.

######  Observation 3.

Let $T$ be an ordered multi-tree rooted at a vertex $r$, and let ${\text{\sc
Ch}}(r)=\\{u_{1},u_{2},\ldots,u_{\deg(r)}\\}$ denote the set of children of
$r$ indexed according to their left-to-right ordering. Given the sequences
$\delta(T_{u})$ and $\mathrm{M}(T_{u})$ for all $u\in{\text{\sc Ch}}(r)$, for
the sequences $\delta(T)$ and $\mathrm{M}(T)$ it holds that:

$\displaystyle\delta(T)$
$\displaystyle=(\mathrm{col}(r),0)\oplus\delta^{1}(T(u_{1}))\oplus\delta^{1}(T(u_{2}))\oplus\cdots\oplus\delta^{1}(T(u_{\deg(r)}));$
$\displaystyle\mathrm{M}(T)$
$\displaystyle=\mathrm{M}(u_{1})\oplus\mathrm{M}(u_{2})\oplus\cdots\oplus\mathrm{M}(u_{\deg(r)}).$

######  Lemma 4.

Given a rooted multi-tree $T$, let $\tau$ denote the ordered multi-tree such
that $\sigma(T)=(\delta(\tau),\mathrm{M}(\tau))$, and let $\prec_{\tau}$
denote the left-to right ordering among siblings in $\tau$. For any two
siblings $u$ and $v$ in $\tau$, if $u\prec_{\tau}v$, then it holds that
$(\delta(\tau_{v}),\mathrm{mul}(v,\mathrm{p}(v)),\mathrm{M}(\tau_{v}))\prec(\delta(\tau_{u}),\mathrm{mul}(u,\mathrm{p}(u)),\mathrm{M}(\tau_{u}))$.

###### Proof.

To derive a contradiction, suppose that there exist siblings $u$ and $v$ in
$\tau$ such that $u\prec_{\tau}v$ and
$(\delta(\tau_{u}),\mathrm{mul}(u,\mathrm{p}(u)),\mathrm{M}(\tau_{u}))\prec(\delta(\tau_{v}),\mathrm{mul}(v,\mathrm{p}(v)),\mathrm{M}(\tau_{v}))$
holds. Let $\tau^{\prime}$ denote the ordered multi-tree obtained by switching
the places of $u$ and $v$ in $\tau$. Clearly, $\tau^{\prime}$ is isomorphic to
$T$ and
$(\delta(\tau),\mathrm{M}(\tau))\prec(\delta(\tau^{\prime}),\mathrm{M}(\tau^{\prime}))$.
This contradicts the assumption that
$\sigma(T)=(\delta(\tau),\mathrm{M}(\tau))$, i.e., that $\sigma(\tau)$ is
lexicographically maximum among all of the ordered multi-trees isomorphic to
$T$. ∎

By Observation 3 and Lemma 4, we show an algorithm to calculate the signature
of a given rooted multi-tree in Procedure 2. As an added benefit, the
procedure in fact calculates the signatures of all rooted subtrees of a given
tree.

Procedure 2 SubTreeSignature

1:A $\Sigma$-colored multi-tree $T$ with multiplicity at most $d$ rooted at a
vertex $r\in V(T)$.

2:The signatures $\sigma(T_{v})$ of each rooted tree $T_{v}$, $v\in V(T)$.

3:$s:=\emptyset$;

4:for each $v\in V(T)$ in DFS-post order do

5: if $v$ is a leaf then

6: $\delta[v]:=(\mathrm{col}(v),0);\mathrm{M}[v]:=\emptyset$

7: else

8: /* The signatures $s[u]$ of all children of $v$ are already obtained */

9: for each $u\in{\text{\sc Ch}}(v)$ do

10: $\delta^{\prime}:=$ 1-shift of $\delta[u]$;

11: $\mathrm{M}^{\prime}:=\mathrm{mul}(u,\mathrm{p}(u))\oplus\mathrm{M}[u]$;

12: $s^{\prime}[u]:=(\delta^{\prime},\mathrm{M}^{\prime})$

13: end for;

14: $S:=(s^{\prime}[u]\mid u\in{\text{\sc Ch}}(v))$;

15: Let $k:=|{\text{\sc Ch}}(v)|$;

16: /* Represent $S$ as $(s_{i}=(\delta_{i},\mathrm{M}_{i})\mid i\in[1,k])$ */

17: Sort $S$ in lexicographically descending order $\pi$;

18:
$\delta[v]:=(\mathrm{col}(v),0)\oplus\delta_{\pi(1)}\oplus\delta_{\pi(2)}\oplus\cdots\oplus\delta_{\pi(k)}$;

19:
$\mathrm{M}[v]:=\mathrm{M}_{\pi(1)}\oplus\mathrm{M}_{\pi(2)}\oplus\cdots\oplus\mathrm{M}_{\pi(k)}$

20: end if

21: $s[v]:=(\delta[v],\mathrm{M}[v])$

22:end for;

23:output $s[v]$ as $\sigma(T_{v})$ for each $v\in V(T)$.

######  Lemma 5.

Given a $\Sigma$-colored rooted tree $T$ on $n$ vertices and multiplicity at
most $d$, Procedure 2 computes the signatures $\sigma(T_{v})$ of all rooted
subtrees $T_{v}$, $v\in V(T)$, of $T$ in $O(n\cdot(n+|\Sigma|+d))$ time.

###### Proof.

Let $n_{v}$ denote the number of vertices in the subtree $T_{v}$ rooted at
vertex $v$, and ${\rm d}_{v}$ the maximum depth of a leaf in the rooted tree
$T_{v}$, where $v$ is taken to have depth $0$, and it holds that ${\rm
d}_{v}\leq n_{v}$.

The for-loop of lines 4 to 22 is executed for each vertex $v$ in $T$. Since
vertices are iterated in an DFS-post order, in each iteration, the signatures
$\sigma(T_{u})$ are already computed for each child $u$ of $v$ in $T$. Then,
in the for-loop of lines 9 to 13, their signatures are gathered and the depth
entries are offset by 1 in line 10. This obviously takes at most $O(n_{v})$
time. Then, in line 17 the gathered sequences are sorted lexicographically.
The total length of the sequences is $O(n_{v})$, and they are over the
alphabets $\Sigma$ for the color of each vertex, $[1,{\rm d}_{v}]$ for the
depth, and $[1,d]$ for the multiplicity, thus the total alphabet size is
$|\Sigma|+d+{\rm d}_{v}$. By the algorithm for lexicographical sorting due to
Aho et al. [1], the lexicographical sorting in line 17 takes
$O(n_{v}+|\Sigma|+d+{\rm d}_{v})$ time. Finally, summing over all vertices $v$
in $T$, for the computational complexity we get

$\displaystyle\sum_{v\in V(T)}O(n_{v}+|\Sigma|+d+{\rm d}_{v})$
$\displaystyle=O(\sum_{v\in V(T)}(n_{v}+{\rm d}_{v})+n\cdot(|\Sigma|+d))$
$\displaystyle=O(n^{2}+n\cdot(|\Sigma|+d)),$

as required. ∎

####  5.2.4 Ranking of Rooted Trees

Let $\mathcal{T}$ be a finite set of rooted multi-trees, and let
$Z=\\{\sigma(T)\mid T\in\mathcal{T}\\}$ denote the set of signatures of the
trees in $\mathcal{T}$. We define a lexicographical order over $Z$ in the
usual sense, i.e., for $\sigma_{1}=(\delta_{1},{\rm
M}_{1}),\sigma_{2}=(\delta_{2},{\rm M}_{2})\in Z$ we write
$\sigma_{1}\prec\sigma_{2}$ if “$\delta_{1}\prec\delta_{2}$” or
“$\delta_{1}=\delta_{2}$ and ${\rm M}_{1}\prec{\rm M}_{2}$.” Then, we use the
lexicographical order over the set $Z$ to define a ranking
$\mathrm{rank}_{\mathcal{T}}:\mathcal{T}\to[1,|Z|]$, such that for two trees
$T_{1},T_{2}\in\mathcal{T}$,
$\mathrm{rank}_{\mathcal{T}}(T_{1})<\mathrm{rank}_{\mathcal{T}}(T_{2})$ if
$\sigma(T_{1})\prec\sigma(T_{2})$, and
$\mathrm{rank}_{\mathcal{T}}(T_{1})=\mathrm{rank}_{\mathcal{T}}(T_{2})$ means
that $\sigma(T_{1})=\sigma(T_{2})$, i.e. $T_{1}$ and $T_{2}$ are isomorphic.
It follows that having a rank function over a set of multi-trees, we can check
whether two trees in the set are isomorphic to each other by comparing their
ranks.

There exist algorithms in the literature that can calculate the rank of each
subtree of a given tree [10] and rooted subgraph of an outerplanar graph [13]
in time linear in the number of vertices in the graph. In our implementation
we use simpler algorithms for this purpose at the cost of a higher time
complexity.

For a set $\mathcal{T}$ of rooted trees, let $\mathcal{T}^{*}$ denote the set
of all rooted subtrees of trees in $\mathcal{T}$. We give a procedure to
calculate a ranking of a given set $\mathcal{T}$ of rooted trees in Procedure
3. By Procedure 2, we in fact obtain a ranking in the set $\mathcal{T}^{*}$ at
no additional cost.

Procedure 3 TreeRanking

1:A set $\mathcal{T}$ of $\Sigma$-colored rooted multi-trees with multiplicity
at most $d$.

2:A ranking function $\mathrm{rank}_{\mathcal{T}^{*}}$ of $\mathcal{T}^{*}$.

3:$R:=\emptyset$; $h:=|\mathcal{T}^{*}|$;

4:$S:=(\sigma(T_{i})\mid i\in[1,h])$; /* Calculate $\sigma(T)$ by Procedure 2
in Sec. 5.2.3 */

5:/* Treat $S=(s_{1},s_{2},\ldots,s_{h})$ as an ordered set */

6:Sort $S$ in lexicographically ascending order $\pi$;

7:$R[T_{\pi(1)}]:=1$; $r:=1$;

8:for each $i\in[2,h]$ do

9: if $s_{\pi(i-1)}\prec s_{\pi(i)}$ then $r:=r+1$ endif;

10: $R[T_{\pi(i)}]:=r$;

11:end for;

12:output $R$ as $\mathrm{rank}_{\mathcal{T}^{*}}$.

######  Lemma 6.

Let $\mathcal{T}$ be a given set of $\Sigma$-colored rooted multi-trees with
multiplicity at most $d$, and let $n$ denote the total number of vertices over
trees in $\mathcal{T}$. Then, the rank of each rooted subtree of all trees in
$\mathcal{T}$ can be computed in $O(n(n+|\Sigma|+d))$ time in total.

###### Proof.

Let $\mathcal{T}=\\{T_{1},T_{2},\ldots,T_{k}\\}$, and let $n_{i}$, $i\in[1,k]$
denote the number of vertices in tree $T_{i}$, where
$n=\sum_{i\in[1,k]}n_{i}$. The signature
$\sigma(T_{i})=(\delta(T_{i}),\mathrm{M}(T_{i}))$ of each tree $T_{i}$ is a
sequence with $O(n_{i})$ entries with $|\Sigma|+n_{i}+d$ possible values, for
the color of vertices and depth in a tree in $\delta(T_{i})$, and multiplicity
with the parent in $\mathrm{M}(T_{i})$, respectively.

By Lemma 5, computing the signatures of all rooted subtrees in line 4 takes
$O(n_{i}\cdot(n_{i}+|\Sigma|+d))$ time for each tree $T_{i}$, and therefore
$O(n\cdot(n+|\Sigma|+d))$ time in total. Now, each tree $T_{i}$ has $n_{i}$
rooted subtrees, and the total number of vertices over these subtrees is
$O(n_{i}^{2})$. Therefore, the collection of signatures for the rooted
subtrees of tree $T_{i}$ has in total $O(n_{i}^{2})$ elements taking at most
$|\Sigma|+n_{i}+d$ different values (alphabet size). Over all trees $T_{i}$,
the elements of the subtree signatures take at most
$|\Sigma|+\max_{i\in[1,k]}\\{n_{i}\\}+d\leq|\Sigma|+n+d$ different values.
Summing over all trees $T_{i}\in\mathcal{T}$, we get that the total length of
the signatures over all subtrees is $\sum_{i\in[1,k]}O(n_{i}^{2})=O(n^{2})$.
Then, all these signatures can be lexicographically sorted in
$O(n^{2}+|\Sigma|+d)$ time [1], which is dominated by the time to calculate
the signatures.

Finally, having the lexicographically sorted signatures, we assign rank to
trees in a straightforward manner by iterating over the sorted signatures as
in lines 8 to 11 in Procedure 3, and the claim follows. ∎

###  5.3 Code on Substructures of Mono-block $2$-Augmented Trees

We can use the signature defined for rooted trees in Section 5.2 to devise
codes for substructures of $k$-augmented trees, $k=1,2$. Let $H$ be a mono-
block $k$-augmented tree with a block $B$, and let $\mathcal{T}(H)=\\{H\langle
v\rangle\mid v\in B\\}$ denote the set of all pendent trees in $H$. Recall
that for a multi-tree $T\in\mathcal{T}(H)$,
$\mathrm{rank}_{\mathcal{T}(H)}(T)$ as defined in Section 5.2.4 gives the rank
of $T$ according to the lexicographical order of the signature $\sigma(T)$. To
simplify our notation, when the graph $H$ and hence the set $\mathcal{T}(H)$
is clear, we write $\mathrm{rank}()$ for the rank function
$\mathrm{rank}_{\mathcal{T}(H)}()$.

Let $H$ be a mono-block 2-augmented tree. Recall that there are exactly two
vertices called junctions, which are contained in all of the cycles in $H$, as
defined in Section 2.2.2. Also recall that for a junction $u$ in $H$ and a
neighbor $u^{\prime}$ of $u$ on a cycle of $H$, we call the pair
$(u,u^{\prime})$ a junction pair. Recall that there are at most six junction
pairs in a mono-block 2-augmented tree. Let $u$ and $v$ denote the junctions
of $H$. For a junction $u$, we define $\mathrm{code}(u)$ to be the sequence
$(|V(H\langle u\rangle)|,\mathrm{col}(u),\deg(u),\mathrm{rank}(H\langle
u\rangle))$. For junctions $u$ and $v$ and a cycle $C_{i}$ of $H$, recall that
$P(u,v;C_{i})$ denotes the $uv$-path $(v_{1},v_{2},\ldots,v_{p})$ such that
$v_{j}\not\in V(C_{i})$ for $j\in[2,p-1]$, let $n(P(u,v;C_{i}))$ denote the
number of vertices $\sum_{j=2}^{p-1}|V(H\langle v_{j}\rangle)|$, and we define
the code $\mathrm{code}(P(u,v;C_{i}))$ of the path $P(u,v;C_{i})$ to be the
following sequence:

$\displaystyle\mathrm{code}(P(u,v;C_{i}))$ $\displaystyle\triangleq$
$\displaystyle(n-n(P(u,v;C_{i})),|P(u,v;C_{i})|,$
$\displaystyle\mathrm{rank}(H\langle
v_{1}\rangle),\mathrm{mul}(v_{1}v_{2}),\mathrm{rank}(H\langle
v_{2}\rangle),\ldots,\mathrm{mul}(v_{p-1v_{p}}),\mathrm{rank}(H\langle
v_{p}\rangle)).$

For a junction $u$, we define $\mathrm{code}^{*}(u)$ to be the sequence
obtained by arranging the codes of $P(u,v;C_{i})$, $i\in[1,3]$, in
lexicographically non-ascending order.

##  6 Parent of a Mono-block 2-Augmented Tree

Let $H$ be a mono-block 2-augmented tree. Let $C_{i}$, $i\in[1,3]$, denote the
cycles of $H$, and let $u$ and $v$ denote the junctions of $H$. Without loss
of generality, we assume that
$(\mathrm{code}(u),\mathrm{code}^{*}(u))\preceq(\mathrm{code}(v),\mathrm{code}^{*}(v))$.
For the cycle $C^{*}$ such that
$\mathrm{code}(P(u,v;C^{*}))\preceq\mathrm{code}(P(u,v;C_{i}))$, $i\in[1,3]$,
let $e^{*}$ denote the edge between $u$ and the neighbor of $u$ in
$P(u,v;C^{*})$. We define the parent of $H$ to be the graph $H-e^{*}$.

######  Lemma 7.

Let $H$ be a mono-block 2-augmented tree with $n$ vertices. Let $C_{i}$,
$i\in[1,3]$ denote the cycles of $H$, and let $u$ and $v$ denote the junctions
of $H$ such that
$(\mathrm{code}(u),\mathrm{code}^{*}(u))\prec(\mathrm{code}(v),\mathrm{code}^{*}(v))$.
For the cycle $C^{*}$ such that
$\mathrm{code}(P(u,v;C^{*}))\preceq\mathrm{code}(P(u,v;C_{i}))$, $i\in[1,3]$,
the number of edges in $P(u,v;C^{*})$ is at least 2.

###### Proof.

From the definition, a cycle has at least three vertices. Since $H$ has three
distinct cycles, there exists an integer $i\in[1,3]$ such that
$|P(u,v;C_{i})|\geq 2$. Suppose that $P(u,v;C^{*})=uv$. We have
$\mathrm{code}(P(u,v;C_{i}))\prec\mathrm{code}(P(u,v;C^{*}))$ since the first
entry of $\mathrm{code}(P(u,v;C_{i}))$ (resp., $\mathrm{code}(P(u,v;C^{*}))$)
is $n-n(P(u,v;C_{i}))<n-1$ (resp., $n-n(P(u,v;C^{*}))=n-1$). This, however,
contradicts that $\mathrm{code}(P(u,v;C^{*}))$ is the lexicographically
minimum among $\mathrm{code}(P(u,v;C_{i}))$, $i\in[1,3]$. As a result, we see
that $P(u,v;C^{*})\neq uv$, and the number of edges in $P(u,v;C^{*})$ is at
least 2. ∎

##  7 Necessary and Sufficient Conditions for Generating Children

Let $G$ be a monocyclic graph with a cycle $C$. For a non-adjacent vertex pair
$\\{x,y\\}$ in $G$, and an integer
$p\in[1,\min\\{\mathrm{res}(x),\mathrm{res}(y)\\}]$, if
$\rho_{G}(x)=\rho_{G}(y)$ holds, then the graph $G+p\cdot xy$ will have two
blocks, and will not be a mono-block 2-augmented tree. Hence, in order to
generate a mono-block 2-augmented tree, we must choose a vertex pair
$\\{x,y\\}$ satisfying $\rho_{G}(x)\neq\rho_{G}(y)$. Observe that then
$\rho_{G}(x)$ and $\rho_{G}(y)$ will be the junctions in the mono-block
2-augmented tree $G+p\cdot xy$. Now, we derive necessary and sufficient
conditions to determine whether $G+p\cdot xy$ is a child of $G$ or not.

######  Lemma 8.

Let $G$ be a monocyclic graph, and let $C$ denote the cycle of $G$. Let $x$
and $y$ be non-adjacent vertices in $V(G)$ with $\rho_{G}(x)\neq\rho_{G}(y)$,
and let $p\in[1,\min\\{\mathrm{res}(x),\mathrm{res}(y)\\}]$. Let $H$ denote
the graph $G+p\cdot xy$, where $\rho_{G}(x)$ and $\rho_{G}(y)$ become the
junctions in $H$, and let $C_{i}$, $i\in[1,3]$, denote the three cycles in
$H$. Then $H$ is a child of $G$ if and only if the following conditions are
satisfied:

(i)

$x=\rho_{G}(x)$ and $y\neq\rho_{G}(y)$ (i.e., $x\in V(C)$ and $y\not\in
V(C)$);

(ii)

$(\mathrm{code}(\rho_{G}(x)),\mathrm{code}^{*}(\rho_{G}(x)))\preceq(\mathrm{code}(\rho_{G}(y)),\mathrm{code}^{*}(\rho_{G}(y)))$;
and

(iii)

$\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C))\preceq\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C_{i}))$,
for all $i\in[1,3]$.

###### Proof.

Necessity. Let $H$ denote the mono-block 2-augmented tree constructed as
$G+p\cdot xy$. Suppose that both $x$ and $y$ are in $V(C)$, then the junctions
of $H$ are $x$ and $y$. From Lemma 7, we see that $H$ is not a child of $G$.
Suppose that neither of $x$ and $y$ is in $V(C)$, then the edge $xy$ is not
incident to a junction of $H$, and we see that $H$ is not a child of $G$, and
hence Condition (i) must hold.

Next, we consider the case when vertices $x$ and $y$ satisfy Condition (i) but
do not satisfy Condition (ii). In this case, the parent of $H$ is obtained by
deleting an edge incident to $\rho_{G}(y)$, and we see that $H$ is not a child
of $G$.

Finally, we assume that $x$ and $y$ satisfy Conditions (i) and (ii) but do not
satisfy Condition (iii). In this case, there exists a cycle $C^{*}\neq C$ such
that
$\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C^{*}))\prec\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C))$.
The parent of $H$ is obtained by deleting the edge between $x$ and the
neighbor of $x$ in $P(x,\rho_{G}(y);C^{*})$ but not the edge $xy$. Hence we
see that $H$ is not a child of $G$.

Sufficiency. By choosing $x=\rho_{G}(x)\neq\rho_{G}(y)\neq y$ we see that
$H=G+p\cdot xy$ is a mono-block 2-augmented tree with junctions
$x=\rho_{G}(x)$ and $\rho_{G}(y)$ and that $xy$ is a junction pair in $H$. The
requirements of (ii) and (iii) in the lemma follow the definition of a parent
in Section 6. ∎

Let $G$ be a monocyclic graph with a cycle $C$. Let $x$ and $y$ be non-
adjacent vertices in $G$ such that $x=\rho_{G}(x)\neq\rho_{G}(y)$, and
$y\not\in V(C)$, and let $p\in[1,\min\\{\mathrm{res}(x),\mathrm{res}(y)\\}]$.
Let $H$ be the mono-block 2-augmented tree $G+p\cdot xy$. The pendent tree
$H\langle x\rangle$ is equivalent to $G\langle x\rangle$. Let $v_{y}$ be the
child of $\rho_{G}(y)$ such that $G\langle v_{y}\rangle$ contains $y$. Then
the pendent tree $H\langle\rho_{G}(y)\rangle$ is equivalent to
$G\langle\rho_{G}(y)\rangle-G\langle v_{y}\rangle$. From Condition (ii) of
Lemma 8, if $|V(G\langle\rho_{G}(y)\rangle)|-|V(G\langle
v_{y}\rangle)|<|V(G\langle x\rangle)|$ holds, then we have

$(\mathrm{code}(\rho_{G}(y)),\mathrm{code}^{*}(\rho_{G}(y)))\prec(\mathrm{code}(\rho_{G}(x)),\mathrm{code}^{*}(x)),$

and we see that $H$ is not a child of $G$. Let $C_{i}$ denote the cycles of
$H$ for $i\in[1,3]$, where $C_{1}=C$. We have $n(P(u,v;C))=|V(G\langle
v_{y}\rangle)|$. From Condition (iii) of Lemma 8, if $|V(G\langle
v_{y}\rangle)|<\max\\{n(P(u,v;C_{2})),n(P(u,v;C_{3}))\\}$ holds, then
$\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C))$ is not the lexicographically
minimum among $\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C_{i}))$, $i\in[1,3]$,
and $H$ is not a child of $G$. From these observations, we have the following
lemma.

######  Lemma 9.

Let $G$ be a monocyclic graph with $n$ vertices, and let $C$ denote the cycle
of $G$. Let $x$ and $y$ be two non-adjacent vertices in $V(G)$ such that
$x=\rho_{G}(x)\neq\rho_{G}(y)$ and $y\not\in V(C)$, and let
$p\in[1,\min\\{\mathrm{res}(x),\mathrm{res}(y)\\}]$. If $G+p\cdot xy$ is a
child of $G$, then it holds that $|V(G\langle\rho_{G}(y)\rangle)|\geq n/3$.

###### Proof.

Let $H$ be the mono-block 2-augmented tree $G+p\cdot xy$, and let $C_{i}$,
$i\in[1,3]$, denote the cycles of $H$, where $C_{1}=C$. The junctions in $H$
are $\rho_{G}(x)$ and $\rho_{G}(y)$. Let $n_{y}$ and $n^{\prime}_{y}$ denote
the numbers $n(P(\rho_{G}(x),\rho_{G}(y);C_{2}))$ and
$n(P(\rho_{G}(x),\rho_{G}(y);C_{3}))$, respectively. Without loss of
generality, we assume that $n_{y}\leq n^{\prime}_{y}$. Since the number of
vertices in $G$ is $n$, we have $n=|V(G\langle
x\rangle)|+|V(G\langle\rho_{G}(y)\rangle)|+n_{y}+n^{\prime}_{y}$.

Let $v_{y}$ be the child of $\rho_{G}(y)$ such that $G\langle v_{y}\rangle$
contains $y$. If $H$ is a child of $G$, then from Conditions (ii) and (iii) of
Lemma 8, we have $|V(G\langle\rho_{G}(y)\rangle)|-|V(G\langle
v_{y}\rangle)|\geq|V(G\langle x\rangle)|$ and $|V(G\langle v_{y}\rangle)|\geq
n^{\prime}_{y}$.

Therefore, we have

$\displaystyle|V(G\langle\rho_{G}(y)\rangle)|$ $\displaystyle\geq|V(G\langle
x\rangle)|+|V(G\langle v_{y}\rangle)|$ $\displaystyle\geq|V(G\langle
x\rangle)|+n^{\prime}_{y}$ $\displaystyle\geq
n-|V(G\langle\rho_{G}(y)\rangle)|-n_{y}-n^{\prime}_{y}+n^{\prime}_{y}$
$\displaystyle\geq(n-n_{y})/2.$

Since we have $n_{y}\leq n^{\prime}_{y}\leq|V(G\langle v_{y}\rangle)|$ and
$n=|V(G\langle
x\rangle)|+|V(G\langle\rho_{G}(y)\rangle)|+n_{y}+n^{\prime}_{y}$, we obtain
$n_{y}\leq n/3$ and $|V(G\langle\rho_{G}(y)\rangle)|\geq(n-n_{y})/2\geq n/3$.
∎

As a consequence of Lemma 9, for a monocyclic graph $G$ with $n$ vertices and
cycle $C$, a pair $\\{x,y\\}$ of non-adjacent vertices in $G$ with
$x=\rho_{G}(x)\neq\rho_{G}(y)$ and $y\not\in V(C)$, and an integer
$p\in[1,\min\\{\mathrm{res}(x),\mathrm{res}(y)\\}]$, if
$V(G\langle\rho_{G}(y)\rangle)|<n/3$ holds, then it holds that $G+p\cdot xy$
is not a child of $G$.

######  Lemma 10.

Let $G$ be a monocyclic graph with a cycle $C$ and let $r\in V(C)$. If $G$ has
a pendent tree $G\langle r^{*}\rangle$ such that $r^{*}\neq r$ and
$|V(G\langle r\rangle)|\leq|V(G\langle r^{*}\rangle)|$, then for any pair
$\\{x,y\\}$ of non-adjacent vertices such that $x\in V(C)$ and $y\in
V(G\langle r\rangle)$ and an integer
$p\in[1,\min\\{\mathrm{res}(x),\mathrm{res}(y)\\}]$ it holds that $G+p\cdot
xy$ is not a child of $G$.

###### Proof.

Let $r^{*}$ denote the root of a pendent tree such that $|V(G\langle
r\rangle)|\leq|V(G\langle r^{*}\rangle)|$. Let $H$ be the graph $G+p\cdot xy$,
where $\rho_{G}(x)$ and $\rho_{G}(y)$ are the junctions in $H$, and let
$C_{i}$, $i\in[1,3]$, denote the cycles of $H$, where $C_{1}=C$. Suppose that
$x\neq r^{*}$. Then, vertex $r^{*}$ is included in some path
$P(\rho_{G}(x),\rho_{G}(y);C_{j})$, $j\in\\{1,2,3\\}$, and it holds that
$n(P(\rho_{G}(x),\rho_{G}(y);C_{j}))\geq|V(G\langle r^{*}\rangle)|$. Let $v$
be the child of $r$ such that $V(G\langle v\rangle)$ contains $y$. For the
path $P(\rho_{G}(x),\rho_{G}(y);C)$, we have
$n(P(\rho_{G}(x),\rho_{G}(y);C))=|V(G\langle v\rangle)|<|V(G\langle
r\rangle)|$. Hence we have
$\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C^{*}))\prec\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C))$,
which contradicts Condition (iii) of Lemma 8.

Next, suppose that $x=r^{*}$. The junctions of $H$ are $r=\rho_{G}(y)$ and
$r^{*}=x$. Let $v$ be the child of $r$ such that $V(G\langle v\rangle)$
contains $y$, and we have $|V(H\langle r\rangle)|=|V(G\langle
r\rangle)|-|V(G\langle v\rangle)|$ and $|V(H\langle r^{*}\rangle)|=|V(G\langle
r^{*}\rangle)|$. Therefore, since we have $|V(H\langle
r^{*}\rangle)|>|V(H\langle r\rangle)|$ it holds that
$(\mathrm{code}(\rho_{G}(x)),\mathrm{code}^{*}(x))\succ(\mathrm{code}(\rho_{G}(y)),\mathrm{code}^{*}(\rho_{G}(y)))$,
and therefore $G+p\cdot xy$ is not a child of $G$, as required. ∎

Finally, from Lemmas 8, 9, and 10, we have the following necessary and
sufficient conditions that a pair of non-adjacent vertices in a monocyclic
graph $G$ must satisfy in order to obtain a child mono-block 2-augmented tree
by adding multiple edges between them.

######  Lemma 11.

Let $G$ be a monocyclic graph with $n$ vertices and a cycle $C$. Let $x$ and
$y$ be non-adjacent vertices in $V(G)$ with $\rho_{G}(x)\neq\rho_{G}(y)$, and
$p\in[1,\min\\{\mathrm{res}(x),\mathrm{res}(y)\\}]$. Let $H$ denote the graph
$G+p\cdot xy$, where $\rho_{G}(x)$ and $\rho_{G}(y)$ are the junctions in $H$,
and let $C_{i}$, $i\in[1,3]$ denote the three cycles in $H$. Then $H$ is a
child of $G$ if and only if the following conditions are satisfied:

(i)

$|V(G\langle\rho_{G}(y)\rangle)|\geq n/3$;

(ii)

$|V(G\langle\rho_{G}(y)\rangle)|>|V(G\langle r\rangle)|$ for each $r\in
V(C)\setminus\\{\rho_{G}(y)\\}$;

(iii)

$x=\rho_{G}(x)$ and $y\neq\rho_{G}(y)$, (i.e., $x\in V(C)$ and $y\not\in
V(C)$);

(iv)

$(\mathrm{code}(\rho_{G}(x)),\mathrm{code}^{*}(\rho_{G}(x)))\preceq(\mathrm{code}(\rho_{G}(y)),\mathrm{code}^{*}(\rho_{G}(y)))$;
and

(v)

$\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C))\preceq\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C_{i}))$,
$i\in[1,3]$.

###  7.1 Preprocessing for Efficient Computation

Notice that in Lemma 11 (iv) and (v), in order to check whether a mono-block
2-augmented tree $H$ obtained by adding an edge to a pair of nonadjacent
vertices in a monocyclic graph $G$ is indeed a child of $G$ or not, requires
our knowledge of the rank of pendent trees of $H$ in the set $\mathcal{T}(H)$
of all pendent trees in $H$. This computation might seem wasteful, as a single
monocyclic graph $G$ may have many candidates for children mono-block
2-augmented trees. We here give an observation that there exists a set
$\mathbb{T}$ of selected pendent trees of $G$ and their subtrees, such that
this set will contain as a subset the set of pendent trees of any graph $H$
obtained by adding an edge between a pair of non-adjacent vertices in $G$.
Then, to save on computation effort, we calculate the rank of rooted trees in
this set $\mathbb{T}$ only once per monocyclic graph $G$.

Let $G$ be a monocyclic graph with a cycle
$C=(v_{0},v_{1},\ldots,v_{n-1},v_{0})$. Then, in addition to the set
$\mathcal{T}(G)=\\{G\langle v_{i}\rangle\mid i\in[0,n-1]\\}$ of pendent trees,
we define the following sets of rooted trees
\- $\widehat{\mathcal{T}}(G)=\\{G\langle u\rangle\mid u\in V(G\langle
v_{0}\rangle)\setminus\\{v_{0}\\}\\}$
\- $\widetilde{\mathcal{T}}(G)=\\{G\langle\mathrm{p}(u)\rangle-G\langle
u\rangle\mid u\in V(G\langle v_{0}\rangle)\setminus\\{v_{0}\\}\\}$.
Finally, we define the union
$\mathbb{T}(G)=\mathcal{T}(G)\cup\widehat{\mathcal{T}}(G)\cup\widetilde{\mathcal{T}}(G)$.

######  Lemma 12.

Given a monocyclic graph $G$ with a cycle
$C=(v_{0},v_{1},\ldots,v_{n-1},v_{0})$, let $\\{x,y\\}\in\overline{E}(G)$ be a
pair of non-adjacent vertices such that $x\in V(C)\setminus\\{v_{0}\\}$ and
$y\in V(G\langle v_{0}\rangle)\setminus\\{v_{0}\\}$, and let $H=G+xy$ denote
the graph obtained from $G$ by adding an edge $xy$. Then it holds that

$\mathcal{T}(H)\subseteq\mathcal{T}(G)\cup\widetilde{\mathcal{T}}(G).$

###### Proof.

By the choice of $x$ and $y$ the graph $H$ is a mono-block 2-augmented tree
and the junctions of $H$ are the vertices $x$ and $v_{0}$. Let $P_{i}$,
$i=1,2,3$, denote the three $x,v_{0}$-paths in $H$, such that $xy\in
E(P_{3})$, i.e., $P_{3}=P(x,y;C)$. The pendent trees $G\langle v_{i}\rangle$,
$i\in[1,n-1]$ are preserved between $G$ and $H$. Therefore, we focus on the
pendent tree $G\langle v_{0}\rangle$. Denote by
$Q=(u_{0}=v_{0},u_{2},\ldots,u_{k-1}=y)$ the $v_{0},y$-path in the tree
$G\langle v_{0}\rangle$. Then, adding the edge $xy$ to path $Q$ we obtain
$P_{3}$ in $H$, and for each rooted tree $G\langle u_{i}\rangle$,
$i\in[0,k-2]$, the tree $G\langle u_{i}\rangle-G\langle u_{i+1}\rangle$
becomes the rooted tree $H\langle u_{i}\rangle$ in the mono-block 2-augmented
tree $H$ (see Fig. 3). Equivalently, for $i\in[1,k-1]$, the tree $G\langle
u_{i-1}\rangle-G\langle u_{i}\rangle$ becomes the pendent tree $H\langle
u_{i}\rangle$ in $H$. Since for $i\in[1,k-1]$ it holds that
$\mathrm{p}(u_{i})=u_{i-1}$ in $G\langle v_{0}\rangle$, the claim follows.

Figure 3:  (a) A monocyclic graph $G$ where the unique cycle is denoted by
$C=(v_{0},v_{1},\ldots,v_{n-1},v_{0})$, with a pair $\\{x,y\\}$ of non-
adjacent vertices such that $x\in V(C)$ and $y\in V(G\langle
v_{0}\rangle)\setminus\\{v_{0}\\}$. (b) The mono-block 2-augmented tree
$H=G+xy$ obtained by adding an edge $xy$ to the monocyclic graph $G$ in (a).
The subtrees denoted by dark gray are preserved from $G$ in $H$.

∎

######  Lemma 13.

Given an $n$-vertex $\Sigma$ -colored monocyclic graph $G$ with multiplicity
at most $d$ and a unique cycle $C=(v_{0},v_{1},\ldots,v_{m-1},v_{0})$, the
rank of all trees in $\mathbb{T}(G)$ can be computed in
$O(n\cdot(n+|\Sigma|+d))$ time in total.

###### Proof.

The set $\mathbb{T}(G)$ is composed of the set $\mathcal{T}(G)$ of pendent
trees of the graph $G$, the set $\widehat{\mathcal{T}}(G)$ of rooted subtrees
of pendent trees of $G$ and trees in the set $\widetilde{\mathcal{T}}(G)$ that
are obtained as a difference between rooted subtrees of $G$. Then, by the
observation made in Section 5.2.2 that for a left-heavy tree $T$ and any
rooted subtree $T^{\prime}$ of $T$ the sequences $\delta(T^{\prime})$ and
$\mathrm{M}(T^{\prime})$ are continuous subsequences of $\delta(T)$ and
$\mathrm{M}(T)$, it is not difficult to obtain the signatures of all trees in
the set $\widetilde{\mathcal{T}}(G)$. Finally, since the total number of
vertices of trees in the set $\widetilde{\mathcal{T}}(G)$ is not more than
that of the set $\widehat{\mathcal{T}}(G)$, and Lemma 6, the claim follows. ∎

###  7.2 A Procedure to Verify Child Conditions

We show an algorithm that for a given monocyclic graph $G$, a pair $\\{x,y\\}$
of non-adjacent vertices in $G$, and an integer
$p\in[1,\min\\{\mathrm{res}(x),\mathrm{res}(y)\\}]$, based on Lemma 11
determines whether $G+p\cdot xy$ is a child of $G$ or not in Procedure 4
ChildCheck.

Procedure 4 ChildCheck$(G,\\{x,y\\},p)$

1:A monocyclic graph $G$ with $n$ vertices and a cycle $C$, a pair
$\\{x,y\\}\in\overline{E}(G)$ of non-adjacent vertices, and an integer
$p\in[1,\min\\{\mathrm{res}(x),\mathrm{res}(y)\\}]$.

2:True if $G+p\cdot xy$ is a child of $G$, and False otherwise.

3:Answer := False;

4:if $|V(G\langle\rho_{G}(y)\rangle)|\geq n/3$ then

5: if $|V(G\langle\rho_{G}(y)\rangle)|>|V(G\langle r\rangle)|$ for each $r\in
V(C)\setminus\\{\rho_{G}(y)\\}$ then

6: if $x=\rho_{G}(x)\neq\rho_{G}(y)\neq y$ then

7: Construct $H:=G+p\cdot xy$; /* $\rho_{G}(x)$ and $\rho_{G}(y)$ are the
junctions in $H$ */

8: Let $C_{i}$, $i\in[1,3]$ denote the cycles of $H$;

9: if $\mathrm{code}(\rho_{G}(x))\prec\mathrm{code}(\rho_{G}(y))$ then

10: if
$\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C))\preceq\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C_{i})),i\in[1,3]$
then

11: Answer := True

12: end if

13: else if $\mathrm{code}(\rho_{G}(x))=\mathrm{code}(\rho_{G}(y))$ then

14: if $\mathrm{code}^{*}(\rho_{G}(x))\preceq\mathrm{code}^{*}(\rho_{G}(y))$
then

15: if
$\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C))\preceq\mathrm{code}(P(\rho_{G}(x),\rho_{G}(y);C_{i})),i\in[1,3]$
then

16: Answer := True

17: end if

18: end if

19: end if

20: end if

21: end if

22:end if;

23:output  Answer.

##  8 Intra-Duplication of Mono-block 2-Augmented Trees

The parent-child relationship helps us avoid inter-duplication, that is,
generating isomorphic structures by adding edges to topologically different
monocyclic graphs. However, the parent-child relationship is not sufficient to
eliminate intra-duplications, since isomorphic children might occur from a
single monocyclic graph $G$ by adding an edge between a pair of non-adjacent
vertices. Henceforth, we treat a graph as a labeled one and use the
information on the labeling, since there is no other way to distinguish
isomorphic mono-block 2-augmented trees generated from a single monocyclic
graph.

For a monocyclic graph $G$, two distinct non-adjacent vertex pairs $\\{x,y\\}$
and $\\{x^{\prime},y^{\prime}\\}$, and integers
$p\in[1,\min\\{\mathrm{res}(x),\mathrm{res}(y)\\}]$ and
$q\in[1,\min\\{\mathrm{res}(x^{\prime}),\mathrm{res}(y^{\prime})\\}]$, we
examine under which conditions $G+p\cdot xy$ and $G+q\cdot
x^{\prime}y^{\prime}$ are isomorphic.

######  Theorem 14.

Let $G$ be a connected graph that contains exactly one cycle $C=(v_{0},v_{1},$
$\ldots,$ $v_{n-1},$ $v_{0})$, and $\\{x_{i},y_{i}\\}$, $i=1,2$, be two pairs
of non-adjacent vertices in $G$ such that $x_{1},x_{2}\in
V(C)\setminus\\{v_{0}\\}$, $y_{1},y_{2}\not\in V(C)$ and
$\rho_{G}(y_{1})=\rho_{G}(y_{2})=v_{0}$. Let $H_{i}$, $i=1,2$, denote the
graph $G+x_{i}y_{i}$, and $c$ be a coloring of the graph $H_{1}+x_{2}y_{2}$.
Let $w_{2}$ denote the child of $v_{0}$ in the rooted tree $G\langle
v_{0}\rangle$ such that $G\langle w_{2}\rangle$ contains $y_{2}$. Assume that
$H_{1}$ and $H_{2}$ are isomorphic. Then one of the following holds.

  1. (i)

$y_{1}\neq y_{2}$, $c(x_{1}y_{1})=c(x_{2}y_{2})$, and $G\langle v_{0}\rangle$
has an automorphism $\xi$ such that $\xi(v_{0})=v_{0}$ and $\xi(y_{1})=y_{2}$;

  2. (ii)

$y_{1}=y_{2}$, $c(x_{1}y_{1})=c(x_{2}y_{2})$, and $G$ has an automorphism
$\xi$ such that $\xi(x_{1})=x_{2}$ and $\xi(v_{i})=v_{n-i\mod n}$ for each
vertex $v_{i}\in V(C)$; and

  3. (iii)

$y_{1}=y_{2}$, $c(x_{1}y_{1})=c(x_{2}y_{2})=c(v_{0}w_{2})$, $G\langle
w_{2}\rangle$ has an automorphism $\phi$ such that $\phi(w_{2})=y_{1}$, and
$G-G\langle w_{2}\rangle$ has an automorphism $\xi$ with an integer $k\geq 1$
such that $\xi(x_{1})=x_{2}$ and $\xi(v_{i})=v_{i+k\mod n}$, $v_{i}\in V(C)$.

###### Proof.

For a subgraph $A$ of $H_{i}$, $i=1,2$, let $A^{(i)}$ denote the subgraph of
$H_{i}$ induced by the vertices in $V(A)$ and $V(H_{i}\langle v\rangle)$,
$v\in A$. Without loss of generality assume that
$\\{x_{1},y_{1}\\}\neq\\{x_{2},y_{2}\\}$, $x_{1}=v_{j_{1}}$, $x_{2}=v_{j_{2}}$
and $1\leq j_{1}\leq j_{2}\leq n-1$. For each $i=1,2$, let $P_{i}$, $Q_{i}$
and $R_{i}$ denote the paths between vertices $x_{i}$ and $\rho_{G}(y_{i})$ in
$H_{i}$, where we assume that $y_{i}\in V(P_{i})$, $v_{1}\in V(Q_{1})$ and
$v_{n-1}\in V(Q_{2})$. Let $\psi:V(H_{1})\to V(H_{2})$ be an isomorphism
between $H_{1}$ and $H_{2}$. Since $H_{i}$ for each $i=1,2$ has exactly one
block $B_{i}$ with exactly two junction vertices $x_{i}$ and
$\rho_{G}(y_{i})=v_{0}$, each path between $x_{1}$ and $v_{0}$ in $H_{1}$ is
mapped by $\psi$ to a path between $x_{2}$ and $v_{0}$ in $H_{2}$. This means
that $c(x_{1}y_{1})=c(x_{2}y_{2})$,
$\psi(\\{x_{1},v_{0}\\})=\\{x_{2},v_{0}\\}$, $\psi(B_{1})=V(B_{2})$,
$|V(B_{1})|=|V(B_{2})|$, and
$\\{\psi(P_{1}^{(1)}),\psi(Q_{1}^{(1)}),\psi(R_{1}^{(1)})\\}=\\{V(P_{2}^{(2)}),V(Q_{2}^{(2)}),V(R_{2}^{(2)})\\}$.
Note that $|V(B_{i})|=|V(C)|+|V(P_{i})|-2$ for each $i=1,2$. Since
$|V(B_{1})|=|V(B_{2})|$, we see that $|V(P_{1})|=|V(P_{2})|$ and
$\\{|V(Q_{1})|,|V(R_{1})|\\}=\\{|V(Q_{2})|,|V(R_{2})|\\}$.

(i) Assume that $y_{1}\neq y_{2}$. Let $z$ denote the deepest vertex in
$V(P_{1})\cap V(P_{2})$ in the rooted tree $G\langle v_{0}\rangle$, where
possibly $z=v_{0}$. When $z\neq v_{0}$, let $Z$ denote the path from $w_{2}$
to $z$ in the subtree $G\langle v_{0}\rangle$, where we regard $V(Z)$ as an
empty set when $z=v_{0}$. For each $i=1,2$, let $z_{i}$ denote the child of
$z$ such that $y_{i}\in V(G\langle z_{i}\rangle)$ and $\overline{P}_{i}$
denote the subpath of $P_{i}$ between $z_{i}$ and $y_{i}$. Note that

$\psi(z)\not\in\psi^{-1}(\overline{P}_{2}),$ (1)

since otherwise $H_{2}\langle z\rangle$ would be isomorphic to a proper
subgraph $H_{2}\langle t\rangle$ for the vertex $t=\psi(v_{h})\in
V(\overline{P}_{2})$.

To show that $G\langle v_{0}\rangle$ has an automorphism $\xi$ such that
$\xi(v_{0})=v_{0}$ and $\xi(y_{1})=y_{2}$, it suffices to prove that

$H_{2}\langle z\rangle$ and $H_{1}\langle z\rangle$ are $(z,z)$-isomorphic.
(2)

Case 1. $\psi(z)\not\in V(G\langle v_{0}\rangle)$: In this case,
$\psi(P_{1})=V(P_{2})$ and “$\psi(v_{0})=v_{0}$ or $z\neq v_{0}$.” Now
$H_{1}\langle z\rangle$ and $H_{2}\langle\psi(z)\rangle$ are
$(z,\psi(z))$-isomorphic. Hence if $z=v_{0}$ and $\psi(v_{0})=v_{0}$, where
$\psi(z)=z$, then (2) holds. Assume that $z\neq v_{0}$. We know that
$H_{1}\langle\psi(z)\rangle$ and $H_{2}\langle\psi^{2}(z)\rangle$ are
$(\psi(z),\psi^{2}(z))$-isomorphic. By (1), $\psi(z)\in V(Z)$ holds, implying
$H_{2}\langle\psi(z)\rangle=H_{1}\langle\psi(z)\rangle$. Since $\psi$ maps
path $P_{1}-\\{v_{0},x_{1}\\}$ to path $P_{2}-\\{v_{0},x_{2}\\}$, we see that
$\psi^{2}(z)=z$. Therefore $H_{1}\langle z\rangle$ and $H_{2}\langle z\rangle$
are $(z,z)$-isomorphic.

Case 2. $\psi(z)\in V(G\langle v_{0}\rangle)$: In this case,
“$\psi(P_{1})=V(P_{2})$, $\psi(x_{1})=v_{0}$ and $z=v_{0}$” or
“$\psi(P_{1})\in\\{V(Q_{2}),V(R_{2})\\}$.” Let $h,k\in[1,n-1]$ denote the
indices such that $v_{h}=\psi(z)\in\psi(P_{1})$ and
$v_{k}=\psi^{-1}(z)\in\psi^{-1}(P_{2})$. Define subtrees $T(v)$, $v\in V(C)$
to be $G\langle v\rangle$ if $v\neq v_{0}$ and $T(v_{0})=H_{2}\langle
v_{0}\rangle$. For the subset $S_{1}=V(C)\setminus\psi^{-1}(\overline{P}_{2})$
of $V(C)$, define a function $f:S_{1}\to V(G)$ such that

$f(v)=\left\\{\begin{array}[]{ll}\psi(v)&\mbox{ if }v\in
S_{1}\setminus\psi^{-1}(Z)\\\ \psi^{2}(v)&\mbox{ if
}v\in\psi^{-1}(Z).\end{array}\right.$

We here prove the following properties:
(a-1) For the subset $S_{2}=V(C)\setminus\psi(\overline{P}_{1})$ of $V(C)$,
$f$ is a bijection from $S_{1}$ to $S_{2}$;
(a-2) Let $v^{\dagger}=v_{k}$ if $z\neq v_{0}$ and $v^{\dagger}=v_{0}$ if
$z=v_{0}$. Then $f(v^{\dagger})=v_{h}$. For each vertex $v\in
S_{1}\setminus\\{v^{\dagger}\\}$, $T(v)$ and $T(f(v))$ are
$(v,f(v))$-isomorphic; and
(a-3) $f^{p}(v_{h})\in S_{2}\setminus\psi(\overline{P}_{2})\subseteq S_{1}$
for any integer $p\geq 1$.

(a-1) Since
$S_{1}\setminus\psi^{-1}(Z)=V(C)\setminus\psi^{-1}(\overline{P}_{2})\setminus\psi^{-1}(Z)=V(C)\setminus\psi^{-1}(V(P_{2})\setminus\\{v_{0}\\})$,
the set $S_{1}\setminus\psi^{-1}(Z)$ is mapped by $\psi$ to $V(Q_{2})\cup
V(R_{2})\subseteq V(C)$. Observe that $f(\psi^{-1}(Z))=\psi(Z)\subseteq V(C)$
and $V(Z)\subseteq V(P_{1})\setminus\\{v_{0}\\}\subseteq V(G)\setminus V(C)$.
Since $S_{1}\setminus\psi^{-1}(Z)$ and $V(Z)$ are disjoint and $\psi$ is a
bijection from $V(G)$ to $V(G)$, we see that
$f(S_{1}\setminus\psi^{-1}(Z))=\psi(S_{1}\setminus\psi^{-1}(Z))$ and
$f(\psi^{-1}(Z))=\psi(Z)$ are disjoint. Since $V(\overline{P}_{1})$ is
disjoint with $(S_{1}\setminus\psi^{-1}(Z))\cup V(Z)$, this also means that
$f(S_{1})\subseteq V(C)\setminus\psi(\overline{P}_{1})=S_{2}$. Therefore
$f(S_{1})=S_{2}$, since $|S_{1}|=|S_{2}|$ and $f$ is a bijection from $S_{1}$
to $f(S_{1})$.

(a-2) We distinguish two cases.

Case of $z\neq v_{0}$, where
$v^{\dagger}=v_{k}\in\psi^{-1}(z)\in\psi^{-1}(Z)$: Then
$f(v^{\dagger})=f(v_{k})=\psi^{2}(v_{k})=\psi(z)=v_{h}$. Let $v\in
S_{1}\setminus\\{v_{k}\\}$. If $\psi(v)\in V(C)$, then $T(v)=H_{1}\langle
v\rangle$ and $T(f(v))=H_{2}\langle\psi(v)\rangle$ are
$(v,\psi(v))$-isomorphic. Note that for any vertex $u\in
V(Z)\setminus\\{z\\}$, $H_{1}\langle u\rangle=H_{2}\langle u\rangle$. Also
$v\neq v_{k}$ means that $\psi(v)\neq z$. If $\psi(v)\in
V(Z)\setminus\\{z\\}$, then $H_{1}\langle v\rangle$ and $H_{2}\langle\psi(v))$
are $(v,\psi(v))$-isomorphic and $H_{1}\langle\psi(v)\rangle$ and
$H_{2}\langle\psi^{2}(v)\rangle$ are $(\psi(v),\psi^{2}(v))$-isomorphic,
implying that $T(v)=H_{1}\langle v\rangle$ and
$T(f(v))=H_{2}\langle\psi^{2}(v)\rangle$ are $(v,\psi^{2}(v))$-isomorphic.

Case of $z=v_{0}$, where $v^{\dagger}=v_{0}$: In this case, $V(Z)=\emptyset$
and $f=\psi$. Then $f(v^{\dagger})=f(v_{0})=\psi(z)=v_{h}$. Therefore for any
vertex $v\in V(C)\setminus\\{v_{0}\\}$, $T(v)=H_{1}\langle v\rangle$ and
$T(f(v))=H_{2}\langle\psi(v)\rangle$ are $(v,\psi(v))$-isomorphic.

(a-3) By definition, $v_{h}=\psi(z)\in\psi(P_{1})\subseteq V(Q_{2})\cup
V(R_{2})\subseteq V(C)$. By (1), $v_{h}\in
V(C)\setminus\psi^{-1}(\overline{P}_{2})=S_{1}$. By (a-2), $f$ maps a vertex
$v\in S$ to a vertex $f(v)$ so that $T(v)$ and $T(f(v))$ are
$(v,f(v))$-isomorphic. Hence for any integer $i\geq 1$, $f^{i}(v_{h})$ is not
a vertex in $\psi^{-1}(\overline{P}_{2})$, since otherwise $T(v)$ would be
isomorphic to a tree $T(f(v))$ that is a proper subgraph of $T(v)$. Therefore
$f^{i}(v_{h})$, $i\geq 1$ is a vertex in
$V(C)\setminus\psi^{-1}(\overline{P}_{2})=S_{1}$.

We are ready to prove (2). By (a-3), it holds
$f^{0}(v_{h}),f(v_{h}),f^{2}(v_{2}),\ldots,f^{|S_{1}|+1}\in S_{1}$, and there
is an integer $i\in[1,|S_{1}|]$ such that $f^{j}(v_{h})=f^{i}(v_{h})$ for some
$j\in[0,i-1]$. Let $p$ denote the smallest such integer $i$, where $j=0$ and
$v_{h}=f^{p}(v_{h})$ since $f$ is a bijection by (a-1). By (a-2), if
$v_{0}\neq z$ (resp., $v_{0}=z$), then
$f^{p-1}(v_{h})=f^{-1}(v_{h})=v^{\dagger}=v_{k}$ (resp.,
$f^{p-1}(v_{h})=f^{-1}(v_{h})=v^{\dagger}=v_{0}$) and $T(v_{h})$ and
$T(v_{k})$ are $(v_{h},v_{k})$-isomorphic (resp., $T(v_{h})$ and
$T(v_{0})=H_{2}\langle z\rangle$ are $(v_{h},v_{0})$-isomorphic). This proves
(2).

In the following, we assume that $y_{1}=y_{2}$, from which it follows that
$x_{1}\neq x_{2}$, $j_{1}=n-j_{2}$ and
$|V(Q_{1})|=|V(Q_{2})|<|V(R_{1})|=|V(R_{2})|$. Hence
$\psi(R_{1}^{(1)})\in\\{V(P_{2}^{(2)}),V(R_{2}^{(2)})\\}$. We first prove that

$P_{1}^{(1)}$ and $P_{2}^{(2)}$ have an isomorphism $\eta$ such that
$\eta(x_{1})=x_{2}$ and $\eta(v_{0})=v_{0}$.  (3)

Recall that $c(x_{1}y_{1})=c(x_{2}y_{2})$. To prove (3), it suffices to show
that $G\langle x_{1}\rangle$ and $G\langle x_{2}\rangle$ are
$(x_{1},x_{2})$-isomorphic, which immediately holds when $\psi(x_{1})=x_{2}$.
When $\psi(x_{1})=v_{0}$ and $\psi(v_{0})=x_{2}$, we see that $G\langle
x_{1}\rangle$ and $G\langle x_{2}\rangle$ are $(x_{1},x_{2})$-isomorphic,
because $H_{1}\langle x_{1}\rangle=G\langle x_{1}\rangle$ and $H_{2}\langle
v_{0}\rangle=H_{1}\langle v_{0}\rangle$ are $(x_{1},v_{0})$-isomorphic and
$H_{1}\langle v_{0}\rangle$ and $H_{2}\langle x_{1}\rangle=G\langle
x_{2}\rangle$ are $(v_{0},x_{1})$-isomorphic. This proves (3).

We distinguish two cases.

(ii) Assume that $y_{1}=y_{2}$ and “$\psi(x_{1})=x_{2}$ or
$\psi(P_{1})\in\\{V(Q_{2}),V(R_{2})\\}$.” For two indices $i,j\in[0,n-1]$ with
$i\leq j$ (resp., $i>j$), let $G[i,j]$ denote the subpath of $G$ induced by
the vertices $v_{\ell}$ with $\ell\in[i,j]$ (resp.,
$\ell\in[i,n-1]\cup[0,j]$). Note that $R_{1}=G[j_{1},0]$ and
$R_{2}=G[0,j_{2}]$. In this case of (ii), we prove that

$\begin{array}[]{l}\mbox{ $G[j_{1},0]^{(1)}$ and $G[0,j_{2}]^{(2)}$ admit an
isomorphism $\eta$ }\\\ \mbox{such that $\eta(v_{j_{1}})=v_{j_{2}}$ and
$\eta(v_{0})=v_{0}$. }\end{array}$ (4)

When such an isomorphism $\eta$ exists, then $G$ has an automorphism $\xi$
such that $\xi(x_{1})=x_{2}$ and $\xi(v_{i})=v_{n-i\mod n}$ for each vertex
$v_{i}\in V(C)$.

In what follows, we prove (4). When $\psi(x_{1})=x_{2}$ and
$\psi(R_{1}^{(1)})=V(R_{2}^{(2)})$, we see that (4) holds.

We first consider the case of $\psi(P_{1}^{(1)})=V(R_{2}^{(2)})$, where
$\psi(R_{1})=V(P_{2})$ and $\psi(P_{1})=V(R_{2})$. We see that $R_{1}^{(1)}$
and $P_{2}^{(2)}$ are $(v_{0},v_{0})$-isomorphic (resp.,
$(x_{1},v_{0})$-isomorphic) and $P_{1}^{(1)}$ and $R_{2}^{(2)}$ are
$(v_{0},v_{0})$-isomorphic (resp., $(x_{1},v_{0})$-isomorphic) if
$\psi(x_{1})=x_{2}$ (resp., $\psi(x_{1})=v_{0}$). By (3), this means that
$R_{1}^{(1)}$ and $R_{2}^{(2)}$ are $(v_{0},v_{0})$-isomorphic, implying (4).

We next consider that $\psi(x_{1})=v_{0}$ and
$\psi(P_{1}^{(1)})=V(Q_{2}^{(2)})$, where $\psi(Q_{1})=V(P_{2})$ and
$\psi^{-1}(P_{2})=V(G[0,j_{1}])$ and $\psi(P_{1})=V(G[j_{2},0])$. In this
case, $G[0,j_{1}]^{(1)}$ and $G[j_{2},0]^{(2)}$ are
$(v_{0},v_{0})$-isomorphic. We observe that $G[j_{1},0]^{(1)}$ (resp.,
$G[0,j_{2}]^{(1)}$) is a repetition of $G[0,j_{1}]^{(1)}$ (resp.,
$G[j_{2},0]^{(1)}$) in the following sense. Let
$a=\lfloor\frac{j_{2}-j_{1}}{j_{1}}\rfloor$ and $b=(j_{2}-j_{1})-a\cdot
j_{1}$. Since $G[0,j_{1}]^{(1)}$ and $G[j_{1},2j_{1}]^{(1)}$ are
$(v_{0},v_{j_{1}})$-isomorphic under the isomorphism $\psi$, we see that for
each integer $j\in[0,a-1]$, $G[0,j_{1}]^{(1)}$ and $G[j\cdot j_{1},(j+1)\cdot
j_{1}]^{(1)}$ are $(v_{0},v_{(j+1)\cdot j_{1}})$-isomorphic. When $b\geq 1$,
$G[0,b]^{(1)}$ and $G[a\cdot j_{1},a\cdot j_{1}+b]^{(1)}$ are
$(v_{0},v_{a\cdot j_{1}})$-isomorphic. Symmetrically $G[j_{2},0]^{(2)}$ and
$G[n-2j_{2},n-j_{2}]^{(2)}$ are $(v_{0},v_{n-j_{2}})$-isomorphic, and we see
that $G[j_{1},0]^{(2)}$ and $G[n-(j+1)\cdot j_{1},n-j\cdot j_{1}]^{(2)}$ are
$(v_{0},v_{n-j\cdot j_{1}})$-isomorphic for each integer $j\in[0,a-1]$, where
for $b\geq 1$, $G[n-b,0]^{(2)}$ and $G[n-a\cdot j_{1}-b,n-a\cdot j_{1}]^{(2)}$
are $(v_{0},v_{n-a\cdot j_{1}})$-isomorphic. Recall that $G[0,j_{1}]^{(1)}$
and $G[j_{2},0]^{(2)}$ are $(v_{0},v_{0})$-isomorphic. Hence
$G[j_{1},0]^{(1)}$ and $G[0,j_{2}]^{(2)}$, which are repetitions of
$G[0,j_{1}]^{(1)}$ and $G[j_{2},0]^{(2)}$, respectively, are
$(v_{0},v_{0})$-isomorphic. This proves (4).

(iii) Finally assume that $y_{1}=y_{2}$, $\psi(x_{1})=v_{0}$ and
$\psi(P_{1})=V(P_{2})$. Since $P_{1}^{(1)}$ and $P_{2}^{(2)}$ are
$(x_{1},v_{0})$-isomorphic, we see that
$c(x_{1}y_{1})=c(x_{2}y_{2})=c(v_{0}w_{2})$, $G\langle w_{2}\rangle$ has an
automorphism $\phi$ such that $\phi(w_{2})=y_{1}$. Let $k=|E(Q_{1})|$. Now
$R_{1}^{(1)}$ and $R_{2}^{(2)}$ are $(x_{1},v_{0})$-isomorphic and
$Q_{1}^{(1)}$ and $Q_{2}^{(2)}$ are $(v_{0},x_{2})$-isomorphic. This means
that $G-G\langle w_{2}\rangle$ has an automorphism $\xi$ such that
$\xi(x_{1})=x_{2}$ and $\xi(v_{i})=v_{i+k\mod n}$, $v_{i}\in V(C)$.

Figure 4: Graphs augmented from $G$ by adding an edge $x_{i}y_{i}$, $i=1,2$:
(a) $H_{1}=G+x_{1}y_{1}$ with $z\neq v_{0}$, (b) $H_{2}=G+x_{2}y_{2}$ with
$z\neq v_{0}$, (c) $H_{1}=G+x_{1}y_{1}$ with $z=v_{0}$, (d)
$H_{2}=G+x_{2}y_{2}$ with $z=v_{0}$.

∎

In addition, we have the following lemma.

######  Lemma 15.

Let $G$ be a connected graph that contains exactly one cycle
$C=(v_{0},v_{1},\ldots,$ $v_{n-1},$ $v_{0})$, let $x_{1}$ and $x_{2}$ be
distinct vertices in $V(C)\setminus\\{v_{0}\\}$, where $x_{1}=v_{k}$, and let
$y$ be a vertex in $V(G\langle v_{0}\rangle)\setminus\\{v_{0}\\}$. For
$i=1,2$, let $p_{i}\in[1,\min\\{\mathrm{res}(x_{i}),\mathrm{res}(y)\\}]$, and
let $H_{i}$ denote $G+p_{i}\cdot x_{i}y$. If $H_{1}$ and $H_{2}$ are
isomorphic, then it holds that $x_{2}=v_{n-k}$.

###### Proof.

Let $B_{i}$, $i=1,2$, denote the block in $H_{i}$, and let $P_{1}$, $P_{2}$,
and $P_{3}$ be the paths in $H_{1}$ from $x_{1}$ to $v_{0}$, where $y\in
V(P_{1})$, $v_{1}\in V(P_{2})$ and $v_{n-1}\in V(P_{3})$. Let $Q_{1}$,
$Q_{2}$, $Q_{3}$ be the paths in $H_{2}$ from $x_{2}$ to $v_{0}$, where $y\in
V(Q_{1})$, $v_{1}\in V(Q_{2})$ and $v_{n-1}\in V(Q_{3})$. We have
$|V(C)|+V(P_{1})-2=|V(B_{1})|=|V(B_{2})|=|V(C)|+V(Q_{1})-2$. Hence, we get
$|P_{1}|=|Q_{1}|$ and $\\{|P_{2}|,|P_{3}|\\}=\\{|Q_{2}|,|Q_{3}|\\}$.

Suppose that $|P_{2}|=|P_{3}|$ and $|Q_{2}|=|Q_{3}|$ hold. Then we have
$|P_{2}|=|P_{3}|=|Q_{2}|=|Q_{3}|=n/2$. Since the length of a path is an
integer, in order to satisfy the condition, $n$ must be even, and then
$x_{1}=x_{2}=v_{n/2}$ holds. However, this contradicts that $x_{1}$ and
$x_{2}$ are distinct vertices. Therefore, we have $|P_{2}|\neq|P_{3}|$ and
$|Q_{2}|\neq|Q_{3}|$. Next, we see that $|P_{2}|=|Q_{2}|$ would again imply
that $x_{1}=x_{2}$, and therefore it holds that $|P_{2}|=|Q_{3}|$ and
$|P_{3}|=|Q_{2}|$. Let $k\in[1,n-1]$ be an integer such that $x_{1}=v_{k}$. In
order to satisfy the condition $|P_{2}|=|Q_{3}|$, $x_{2}$ must be $v_{n-k}$,
as required. ∎

Let $G$ be a monocyclic graph and $C=(v_{0},v_{1},\ldots,v_{n-1},v_{0})$
denote the cycle in $G$. If $G$ admits an automorphism $\xi$ such that
$\xi(v_{i})=v_{n-i\mod n}$ for each vertex $v_{i}\in V(C)$, as in Theorem
14(ii), then we say that $G$ admits an _axial symmetry_ $\xi$. Further, for a
vertex $y\in V(\langle v_{0}\rangle)\setminus\\{v_{0}\\}$, let $q$ be the
child of $v_{0}$ such that $G\langle q\rangle$ contains $y$. If there exists
an automorphism $\phi$ on $G\langle q\rangle$ such that $\phi(q)=y$, and an
automorphism $\xi$ on $G-G\langle q\rangle$ such that $\xi(v_{i})=v_{i+k\mod
n}$, $v_{i}\in V(C)$ and $k\geq 1$, as in Theorem 14(iii), then we say that
the pair $(G,q)$ admits a _rotational symmetry_ $(\xi,\phi)$ for $k\geq 1$.

Let $G$ be a monocyclic graph and $C=(v_{0},v_{1},\ldots,v_{n-1},v_{0})$
denote the cycle in $G$ such that the pendent tree $G\langle v_{0}\rangle$ has
the maximum number of vertices over all pendent trees in $G$ and is
represented as a left-heavy tree. Let $\mathrm{copy}:V(G\langle
v_{0}\rangle)\to\\{0,1\\}$ be a function such that for $v\in V(G\langle
v_{0}\rangle)$ it holds that $\mathrm{copy}(v)=1$ (resp.,
$\mathrm{copy}(v)=0$) if $v$ has a left sibling $u$ and for the parent
$q=\mathrm{p}(v)=\mathrm{p}(u)$ it holds that $G\langle q,v\rangle\approx
G\langle q,u\rangle$ (resp., $v$ does not have a sibling on its left, or for
the sibling $u$ on its left it holds $G\langle q,v\rangle\not\approx G\langle
q,u\rangle$) [24], and let $Y=\\{y\in V(G\langle
v_{0}\rangle)\setminus\\{v_{0}\\}\mid\mathrm{copy}(v)=0\text{ for }v\in
V(P(v_{0},y))\\}$. We define the _potential edge set_ $S(G)$ of non-adjacent
vertex pairs in $G$ as follows:

Case (i):

The pendent tree $G\langle v_{0}\rangle$ is not exceeding, or $G$ has more
than one pendent tree with at least $|V(G\langle v_{0}\rangle)|$ vertices.
Then, we define $S(G)\triangleq\emptyset.$

Case (ii):

The pendent tree $G\langle v_{0}\rangle$ is exceeding and there is no other
pendent tree of $G$ with at least $|V(G\langle v_{0}\rangle)|$ vertices.

Case (ii)(a):

$G$ admits an axial symmetry. Then we define

$S(G)\triangleq\\{\\{x,y\\}\mid x\in\\{v_{i}\mid i\in[\lfloor
n/2\rfloor]\\},y\in Y\\}.$

Case (ii)(b):

$G$ does not admit an axial symmetry. Then we define

$\displaystyle S(G)\triangleq\\{\\{x,y\\}\mid y\in Y,$ for the child $q$ of
$v_{0}$ such that $y\in V(G\langle q\rangle)$ $\displaystyle``(G,q)\text{
admits a rotational symmetry $(\xi,\phi)$ with $k\geq 1$'' or}$
$\displaystyle``(G,q)\text{ does not admit a rotational symmetry and}$
$\xi:V(C)\to V(C)$ is an identity mapping,” $\displaystyle x\in\\{v_{i}\mid
i\in[1,\lfloor n/2\rfloor]\\}$ $\displaystyle\cup\\{v_{n-i\mod n}\mid
i\in[1,\lfloor n/2\rfloor],\xi(v_{i})\neq v_{n-i\mod n}\\}.$

Then, we have the following lemma.

######  Lemma 16.

For a monocyclic graph $G$, the potential edge set $S(G)$ is proper.

###### Proof.

Let $C=(v_{0},v_{1},\ldots,v_{n-1},v_{0})$ denote the unique cycle in $G$,
such that the pendent tree $G\langle v_{0}\rangle$ has the maximum number of
vertices among all pendent trees in $G$, $G\langle v_{0}\rangle$ is
represented as a left-heavy tree, and let $\mathrm{copy}:V(G\langle
v_{0}\rangle)\to\\{0,1\\}$ be a function such that for $v\in V(G\langle
v_{0}\rangle)$ it holds that $\mathrm{copy}(v)=1$ (resp.,
$\mathrm{copy}(v)=0$) if $v$ has a left sibling $u$ and
$G\langle\mathrm{p}(v),v\rangle\approx G\langle\mathrm{p}(u),u\rangle$ (resp.,
$v$ does not have a sibling on its left, or for the sibling $u$ on its left it
holds $G\langle\mathrm{p}(v),v\rangle\not\approx
G\langle\mathrm{p}(u),u\rangle$) [24].

Case (i).

If $G\langle v_{0}\rangle$ is not exceeding, or $G$ has more than one pendent
tree with maximum number of vertices, then $S(G)=\emptyset$ is proper for $G$
since by Lemmas 9 and 10 $G$ has no children.

Case (ii).

By Theorem 14(i), for two non-adjacent vertex pairs $\\{x_{i},y_{i}\\}$,
$i=1,2$, in $G$ with $x_{1},x_{2}\in V(C)$ and $y_{1},y_{2}\in V(G\langle
v_{0}\rangle)\setminus\\{v_{0}\\}$ intra-duplication occurs if $G\langle
v_{0}\rangle$ admits an automorphism $\xi$ such that $\xi(y_{1})=\xi(y_{2})$.
By choosing vertices $y\in V(G\langle v_{0}\rangle)\setminus\\{v_{0}\\}$ such
that $\mathrm{copy}(v)=0$ holds for each $v\in V(P(v_{0},y))$, we know that no
two vertices $y_{1}$ and $y_{2}$ will be chosen such that $G\langle
v_{0}\rangle$ admits an automorphism $\xi$ with $\xi(y_{1})=y_{2}$ [24]. Next
we consider the case when for vertices $x_{1},x_{2}\in V(C)$ and $y\in
V(G\langle v_{0}\rangle)\setminus\\{v_{0}\\}$, and integers
$p_{i}\in[1,\min\\{\mathrm{res}(x_{i}),\mathrm{res}(y)\\}]$, $i=1,2$, it holds
that $G+p_{1}\cdot x_{1}y$ is isomorphic to $G+p_{2}\cdot x_{2}y$.

Case (ii)(a).

By Theorem 14(ii), $G$ admits an automorphism $\xi$ such that for
$i\in[1,\lfloor n/2\rfloor]$ it holds $\xi(v_{i})=v_{n-i\mod n}$, and
therefore it suffices to consider vertices $v_{i},i\in[1,\lfloor n/2\rfloor]$,
for the choice of $x$, thereby for each $x^{\prime}\in\\{v_{i}\mid
i\in[\lfloor n/2\rfloor+1,n-1]\\}$ there exists an $x$ such that
$\xi(x)=x^{\prime}$ and therefore $\mathrm{res}(x)=\mathrm{res}(x^{\prime})$,
and for $p\in[1,\min\\{\mathrm{res}(x),\mathrm{res}(y)\\}]$ $G+p\cdot xy$ and
$G+p\cdot x^{\prime}y$ are isomorphic. On the other hand, by Lemma 15 for
$x_{1},x_{2}\in\\{v_{i}\mid i\in[1,\lfloor n/2\rfloor]\\}$ and
$p_{i}\in[1,\min\\{\mathrm{res}(x_{i}),\mathrm{res}(y)\\}]$, $i=1,2$,
$G+p_{1}\cdot x_{1}y$ and $G+p_{2}\cdot x_{2}y$ are not isomorphic, satisfying
the conditions for a proper set.

Case (ii)(b).

In case $G$ does not admit an axial symmetry, for each choice of $y\in
V(G\langle v_{0}\rangle)\setminus\\{v_{0}\\}$ such that $\mathrm{copy}(v)=0$
holds for all $v\in V(P(v_{0},y))$, for the child $q$ of $v_{0}$ such that
$G\langle q\rangle$ contains $y$, we check whether the pair $(G,q)$ admits a
rotational symmetry $(\xi,\phi)$ for $k\geq 1$, as in Theorem 14(iii). In case
there does not exist an automorphism $\xi$ on $G-G\langle q\rangle$ such that
$\xi(v_{i})=v_{i+k\mod n}$, $v_{i}\in V(C)$ and $k\geq 1$, and an automorphism
$\phi$ on $G\langle q\rangle$ with $\phi(q)=y$, we take trivial automorphism
$\xi(x)=x,x\in V(C)$. Again, by the automorphism $\xi$, for two vertices
$x_{1},x_{2}\in V(C)$ either $x_{1}=\xi(x_{2})$ and then
$\mathrm{res}(x_{1})=\mathrm{res}(x_{2})$, $\\{x_{1},y\\}\in S(G)$ and
$\\{x_{2},y\\}\notin S(G)$ but for any
$p\in[1,\min\\{\mathrm{res}(x_{1}),\mathrm{res}(y)\\}]$ it holds that
$G+p\cdot x_{1}y\approx G+p\cdot x_{2}y$, or $x_{1}\neq\xi(x_{2})$, in which
case $\\{x_{1},y\\}\in S$ and $\\{x_{2},y\\}\in S$, but for any
$p_{i}\in[1,\min\\{\mathrm{res}(x_{i}),\mathrm{res}(y)\\}]$, $i=1,2$, it holds
that $G+p_{1}\cdot x_{1}y\not\approx G+p_{2}\cdot x_{2}y$, as required.

∎

We give a description of an algorithm to compute the potential edge set of a
given monocyclic graph $G$ as Procedure 5 GeneratePotentialEdgeSet.

Procedure 5 GeneratePotentialEdgeSet$(G)$

1:A monocyclic graph $G$ with a cycle $C=(v_{0},v_{1},\ldots,v_{n-1},v_{0})$,
such that $G\langle v_{0}\rangle$ has the maximum number of vertices over all
pendent trees in $G$, and a function $\mathrm{copy}:V(G\langle
v_{0}\rangle)\to\\{0,1\\}$ such that $\mathrm{copy}(v)=1$ if $v$ has a left
sibling $u$ and $G\langle\mathrm{p}(v),v\rangle\approx
G\langle\mathrm{p}(u),u\rangle$ and $\mathrm{copy}(v)=0$ otherwise.

2:The potential edge set $S(G)$ of $G$.

3:$S:=\emptyset$;

4:if $|V(G\langle v_{0}\rangle)|\geq|V(G)|/3$ and for $i\in[1,n-1]$,
$|V(G\langle v_{0}\rangle)|>|V(G\langle v_{i}\rangle)|$ then

5: for each child $c$ of $v_{0}$ such that $\mathrm{copy}(c)=0$ do

6: for each $y\in V(G\langle c\rangle)$ such that $\mathrm{copy}(v)=0$ for
$v\in V(P(v_{0},y))$ do

7: $S:=S\cup\left\\{\\{v_{i},y\\}\mid i\in[1,\lfloor n/2\rfloor]\right\\}$

8: if $G$ does not admit an axial symmetry then

9: Let $q\in V(G\langle v_{0}\rangle)$ be the child of $v_{0}$ such that $y\in
V(G\langle q\rangle))$;

10: if $(G,q)$ admits a rotational symmetry $(\xi,\phi)$ for $k\geq 1$ then

11: $S:=S\cup\\{\\{v_{n-i\mod n},y\\}\mid i\in[1,\lfloor
n/2\rfloor],\xi(v_{i})\neq v_{n-i\mod n}\\}$

12: else /* $(G,q)$ does not admit a rotational symmetry for $k\geq 1$ */

13: $S:=S\cup\left\\{\\{v_{i},y\\}\mid i\in[\lfloor
n/2\rfloor+1,n-1]\right\\}$

14: end if

15: end if

16: end for

17: end for

18:end if;

19:output $S$ as $S(G)$.

##  9 Experimental results

To test the effectiveness of our algorithm for enumerating mono-block
2-augmented trees, we have implemented it and performed computational
comparison with MOLGEN [12], a generator for chemical graphs.

In particular, we did experiments for two different types of instances, named
EULF-$L$-A and EULF-$L$-P, by considering a set $\mathcal{P}$ of colored
sequences with length at most a given integer $N$, given lower and upper
bounds, $\mathbf{g}_{a}:\mathcal{P}\to\mathbb{Z}_{+}$ and
$\mathbf{g}_{b}:\mathcal{P}\to\mathbb{Z}_{+}$, respectively, on the path
frequencies of the paths in $\mathcal{P}$, and integers $L$ and $d$. For a
given set $\mathcal{P}$ of colored sequences and a graph $G$, let
$\mathbf{f}_{\mathcal{P}}(G):\mathcal{P}\to\mathbb{Z}_{+}$ denote the number
$\mathrm{frq}(t,G)$ of rooted paths $P\subseteq G$ such that
$\gamma(P)=t\in\mathcal{P}$. Assuming that $\mathbf{g}_{a}\leq\mathbf{g}_{b}$,
and in particular, that $\mathbf{g}_{a}[t]=\mathbf{g}_{b}[t]$ is satisfied for
each colored sequence $t\in\mathcal{P}\cap\Sigma^{0,d}$, each of the instance
types EULF-$L$-A and EULF-$L$-P asks to enumerate chemical graphs $G$ such
that $\mathbf{g}_{a}\leq\mathrm{frq}_{\mathcal{P}}(G)\leq\mathbf{g}_{b}$, and
for any $P\subseteq G$ such that $\gamma(P)\notin\mathcal{P}$, it holds that
$|P|>L$ and $|P|\leq L$, for instance types EULF-$L$-A and EULF-$L$-P,
respectively.

We have chosen six compounds from the PubChem database which when represented
as hydrogen-suppressed chemical graphs have mono-block 2-augmented tree
structure, and constructed feature vectors based on the path frequencies of
the paths in the chemical graphs. All compounds have 13 non-hydrogen atoms,
maximum path length 11, and maximum bond multiplicity $d\in\\{2,3\\}$. All
compounds include the three chemical elements C (carbon), O (oxygen), and N
(nitrogen). The information on the chosen compounds, identified by their
Compound ID (CID) number in the PubChem database is given in Table 1.

Table 1: Information on the six compounds chosen from the PubChem database for our experiments Molecular formula | $d$ | CID
---|---|---
C9N1O3 | 2 | 301729
3 | 57320502
C9N2O2 | 2 | 6163405
3 | 131335510
C9N3O1 | 2 | 9942278
3 | 10103630

We construct instances of types EULF-$L$-A and EULF-$L$-P for different values
of parameter $L$ in the following way. We take a set $\Sigma$ of colors to be
$\Sigma=\\{\mathtt{C},\mathtt{O},\mathtt{N}\\}$, such that
$\mathrm{val}(\mathtt{C})=4$, $\mathrm{val}(\mathtt{O})=2$, and
$\mathrm{val}(\mathtt{N})=3$. For each hydrogen suppressed chemical graph $G$
that corresponds to a chemical compound in Table 1, we take $d\in\\{2,3\\}$ to
be the maximum bond multiplicity in the chemical graph, and for some choice of
values for $N\geq 0$ we construct a set of colored sequences
$\mathcal{P}\subseteq\Sigma^{\leq N,d}$ that consists of all colored sequences
$t$ with length $|t|\leq N$ such that $G$ contains a rooted path $P$ with
$\gamma(P)=t$. Finally, for an integer $s\in[0,2]$ we set lower and upper
bounds, ${\bf g}_{a}$ and ${\bf g}_{b}$ on feature vectors as follows: for
$t\in\mathcal{P}$, if $|t|\in\Sigma^{0,d}$ then ${\bf g}_{a}[t]={\bf
g}_{b}[t]=\mathrm{frq}(t,G)$, otherwise ${\bf
g}_{a}[t]=\max\\{0,\mathrm{frq}(t,G)-s\\}$ and ${\bf
g}_{b}[t]=\mathrm{frq}(t,G)+s$. The parameter $s$ effectively serves to
“relax” the path frequency specification.

On the other hand, we used MOLGEN [12] without aromaticity detection by
specifying the hydrogen suppressed formula, number of cycles to be two in
enumerated structures \- thereby enumerating chemical graphs with 2-augmented
tree structures with a maximum allowed bond multiplicity. Note that there is
no option in MOLGEN to specify whether the enumerated structures have a mono-
block structure or not.

We implemented our algorithm in the C++ programming language, and compiled and
executed on the Linux 14.04.6 operating system by the gcc compiler version
4.8.4 and optimization level O3. All experiments were done on a PC with Intel
Xeon CPU E5-1660 v3 running at 3.00 GHz, with 32 GB memory.

###  9.1 Experimental Results for EULF-$L$-A

To test the behavior of our algorithm for instance types EULF-$L$-A,
especially the effect the choice of problem parameters have on the running
time and the number of enumerated chemical graphs, we choose values for
parameter $N\in[2,6]$, and we took values for the parameter
$L\in\\{2,\lceil{N/2}\rceil,N\\}$.

The results from our experiments for EULF-$L$-A are summarized in Figs. 5 to
10. We observe that our algorithm has a clear advantage when we are given a
path frequency specification for instances of type EULF-$L$-A over using
MOLGEN to generate molecules with a specified formula. We also observe some
trends over the values of the parameters $N$, $L$, and $s$. Namely, the number
of generated molecules, as well as the time it takes our algorithm, reduces as
the length $N$ of the longest path given in the set of paths, as well as the
parameter $L$ increase, but grows with an increasing value $s$ that we choose
to relax the path frequency specification.

(a)

(d)

(b)

(e)

(c)

(f)

Figure 5:  Plots showing the computation time and number of chemical graphs
enumerated by our algorithm for instance type EULF-$L$-A, as compared to
MOLGEN. The sample structure from PubChem is with CID 301729, molecular
formula C9N1O3, and maximum bond multiplicity $d=2$. (a)-(c) Running time;
(d)-(f) Number of enumerated chemical graphs.

(a)

(d)

(b)

(e)

(c)

(f)

Figure 6:  Plots showing the computation time and number of chemical graphs
enumerated by our algorithm for instance type EULF-$L$-A, as compared to
MOLGEN. The sample structure from PubChem is with CID 57320502, molecular
formula C9N1O3, and maximum bond multiplicity $d=3$. (a)-(c) Running time;
(d)-(f) Number of enumerated chemical graphs.

(a)

(d)

(b)

(e)

(c)

(f)

Figure 7:  Plots showing the computation time and number of chemical graphs
enumerated by our algorithm for instance type EULF-$L$-A, as compared to
MOLGEN. The sample structure from PubChem is with CID 6163405, molecular
formula C9N2O2, and maximum bond multiplicity $d=2$. (a)-(c) Running time;
(d)-(f) Number of enumerated chemical graphs.

(a)

(d)

(b)

(e)

(c)

(f)

Figure 8:  Plots showing the computation time and number of chemical graphs
enumerated by our algorithm for instance type EULF-$L$-A, as compared to
MOLGEN. The sample structure from PubChem is with CID 131335510, molecular
formula C9N2O2, and maximum bond multiplicity $d=3$. (a)-(c) Running time;
(d)-(f) Number of enumerated chemical graphs.

(a)

(d)

(b)

(e)

(c)

(f)

Figure 9:  Plots showing the computation time and number of chemical graphs
enumerated by our algorithm for instance type EULF-$L$-A, as compared to
MOLGEN. The sample structure from PubChem is with CID 9942278, molecular
formula C9N3O1, and maximum bond multiplicity $d=2$. (a)-(c) Running time;
(d)-(f) Number of enumerated chemical graphs.

(a)

(d)

(b)

(e)

(c)

(f)

Figure 10:  Plots showing the computation time and number of chemical graphs
enumerated by our algorithm for instance type EULF-$L$-A, as compared to
MOLGEN. The sample structure from PubChem is with CID 10103630, molecular
formula C9N3O1, and maximum bond multiplicity $d=3$. (a)-(c) Running time;
(d)-(f) Number of enumerated chemical graphs.

In addition, to check the limits as to the maximum number of vertices in
graphs that can be enumerated in a reasonable time, we conducted experiments
over a range $n\in[9,40]$ for the number of vertices in a target chemical
graph. For a fixed number $n$ of vertices, we tested two types of instances,
one with molecular formula $\mathtt{C}_{n}$, and the other with molecular
formula $\mathtt{C}_{n-4}\mathtt{N}_{2}\mathtt{O}_{2}$, and set an execution
time limit of $3,600$ seconds. The results are summarized in Fig. 11. From
Fig. 11 (a) and (b), we see that the time limit is quickly reached even when
the number $n$ of number of vertices is less than 15, but that the program
still enumerates structures within the time limit up to $n=30$, after which
there are cases when not even a single graph is enumerated during the time
limit.

(a)

(c)

(b)

(d)

Figure 11:  Plots showing the computation time and number of chemical graphs
enumerated by our algorithm for instance type EULF-$L$-A, over ranges for
$N\in[0,2]$, $L=N$, $d=3$ and $s=0$. (a), (b) Running time, T.O. stands for
“Time Out”; (c), (d) Number of enumerated chemical graphs.

###  9.2 Experimental Results on EULF-$L$-P

We conduct similar computational experiments to test the performance of our
algorithm for Problem EULF-$L$-P as in Section 9.1. We took values for
$N\in[8,10]$, and $L\in\\{2,3\\}$.

The results from our experiments for instance type EULF-$L$-P are summarized
in Figs. 12 to 17. Our results for instance type EULF-$L$-P indicate that
there exist very few chemical graphs that satisfy the path frequency
specification for our choice of a set $\mathcal{P}$ of colored paths obtained
from the six compounds from the PubChem database, and parameter $L$. In fact,
the only two instances where our algorithm enumerates any chemical graphs are
for two of our chosen compounds; with CID 301729, molecular formula C9N1O3 and
bond multiplicity at most 2 (Fig. 12 (c) and (d)), and the compound with CID
10103630, molecular formula C9N3O1 and bond multiplicity at most 3 (Fig. 17
(c) and (d)). This could be due to the very nature of mono-block 2-augmented
structures, namely, due to the biconnectedness of a block, a single path
frequency specification exhibits a strong influence on the structure of a
chemical graph.

In addition, we observe that the running time of our algorithm, even when
there are no enumerated chemical graphs, grows rapidly with the value of the
parameter $L$. It is an interesting idea for future research to improve our
algorithm in such a way that the non-existence of any chemical graphs that
satisfy a given path frequency specification is determined much quicker.

(a)

(c)

(b)

(d)

Figure 12:  Plots showing the computation time and number of chemical graphs
enumerated by our algorithm for instance type EULF-$L$-P, as compared to
MOLGEN. The sample structure from PubChem is with CID 301729, molecular
formula C9N1O3, and maximum bond multiplicity $d=2$. (a), (b) Running time;
(c), (d) Number of enumerated chemical graphs.

(a)

(c)

(b)

(d)

Figure 13:  Plots showing the computation time and number of chemical graphs
enumerated by our algorithm for instance type EULF-$L$-P, as compared to
MOLGEN. The sample structure from PubChem is with CID 57320502, molecular
formula C9N1O3, and maximum bond multiplicity $d=3$. (a), (b) Running time;
(c), (d) Number of enumerated chemical graphs (our algorithm detects that
there are no chemical graphs that satisfy the given path frequency
specification).

(a)

(c)

(b)

(d)

Figure 14:  Plots showing the computation time and number of chemical graphs
enumerated by our algorithm for instance type EULF-$L$-P, as compared to
MOLGEN. The sample structure from PubChem is with CID 6163405, molecular
formula C9N2O2, and maximum bond multiplicity $d=2$. (a), (b) Running time;
(c), (d) Number of enumerated chemical graphs (our algorithm detects that
there are no chemical graphs that satisfy the given path frequency
specification).

(a)

(c)

(b)

(d)

Figure 15:  Plots showing the computation time and number of chemical graphs
enumerated by our algorithm for instance type EULF-$L$-P, as compared to
MOLGEN. The sample structure from PubChem is with CID 131335510, molecular
formula C9N2O2, and maximum bond multiplicity $d=3$. (a), (b) Running time;
(c), (d) Number of enumerated chemical graphs (our algorithm detects that
there are no chemical graphs that satisfy the given path frequency
specification).

(a)

(c)

(b)

(d)

Figure 16:  Plots showing the computation time and number of chemical graphs
enumerated by our algorithm for instance type EULF-$L$-P, as compared to
MOLGEN. The sample structure from PubChem is with CID 9942278, molecular
formula C9N3O1, and maximum bond multiplicity $d=2$. (a), (b) Running time;
(c), (d) Number of enumerated chemical graphs (our algorithm detects that
there are no chemical graphs that satisfy the given path frequency
specification).

(a)

(c)

(b)

(d)

Figure 17:  Plots showing the computation time and number of chemical graphs
enumerated by our algorithm for instance type EULF-$L$-P, as compared to
MOLGEN. The sample structure from PubChem is with CID 10103630, molecular
formula C9N3O1, and maximum bond multiplicity $d=3$. (a), (b) Running time;
(c), (d) Number of enumerated chemical graphs.

##  10 Conclusion and Future Work

We formulated two problem settings of enumerating chemical graphs that satisfy
given lower and upper bounds on path frequencies in a given set of paths,
EULF-$L$-A, and EULF-$L$-P. The problem of enumerating chemical graphs has an
important practical application in inverse QSAR/QSPR, and can be used as a
part of a framework for inferring novel chemical structures [3, 9, 4] together
with a method for solving the inverse problem on artificial neural networks
based on linear programming due to Akutsu and Nagamochi [2].

We focused on enumerating chemical graphs with a mono-block $2$-augmented tree
structure. We designed a branch-and-bound algorithm for the problem by
developing a new procedure to add edges between a pair of non-adjacent
vertices of a monocyclic graph. Our procedure relies on a carefully chosen
parent-child relationship between mono-block $2$-augmented trees and
monocyclic graphs to avoid inter-duplication, and a way of choosing a proper
set of non-adjacent vertex pairs in a monocyclic graph, such that adding edges
between each pair in the set will not cause intra-duplication, nor any
possible mono-block $2$-augmented trees to be omitted.

Experimental results reveal that our algorithm offers a big advantage in terms
of running time and the number of generated structures for instance type
EULF-$L$-A when we have a path frequency specification over using MOLGEN [12]
to generate chemical graphs with a particular molecular formula. Namely, while
MOLGEN may produce on the order of billions of chemical graphs with
2-augmented tree structure with a particular chemical formula and maximum bond
multiplicity, for a given path specification our algorithm produces much fewer
structures, and we also have the advantage to generate only mono-block
structures.

However, for instance type EULF-$L$-P, the experimental results reveal that
our algorithm takes much time to finish even when there are no chemical graphs
that satisfy a given path frequency specification. It would be very
interesting to equip our algorithm with a procedure that detects this
situation much earlier in the computation process, or even design an algorithm
based on a different idea - namely one that starts building a chemical graph
from one of the paths with a non-zero lower bound in a given set.

## References

  * [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman.  The Design and Analysis of Computer Algorithms.  1974\.
  * [2] T. Akutsu and H. Nagamochi.  A mixed integer linear programming formulation to artificial neural networks.  In Proceedings of the 2nd International Conference on Information Science and Systems, pages 215–220. ACM, 2019.
  * [3] N. A. Azam, R. Chiewvanichakorn, F. Zhang, A. Shurbevski, H. Nagamochi, and T. Akutsu.  A method for the inverse QSAR/QSPR based on artificial neural networks and mixed integer linear programming.  In Proceedings of the 13th International Joint Conference on Biomedical Engineering Systems and Technologies – Volume 3: BIOINFORMATICS, pages 101–108, 2020.
  * [4] N. A. Azam, R. Ito, C. Wang, A. Shurbevski, H. Nagamochi, and T. Akutsu.  A novel method for the inverse QSAR/QSPR to monocyclic chemical compounds based on artificial neural networks and integer programming, 2020.  BIOCOMP2020 (submitted).
  * [5] R. S. Bohacek, C. McMartin, and W. C. Guida.  The art and practice of structure-based drug design: A molecular modeling perspective.  Medicinal Research Reviews, 16(1):3–50, 1996.
  * [6] L. Bytautas and D. J. Klein.  Formula periodic table for acyclic hydrocarbon isomer classes: combinatorially averaged graph invariants.  Physical Chemistry Chemical Physics, 1(24):5565–5572, 1999.
  * [7] L. Bytautas and D. J. Klein.  Isomer combinatorics for acyclic conjugated polyenes: enumeration and beyond.  Theoretical Chemistry Accounts, 101(6):371–387, 1999.
  * [8] A. Cayley.  On the analytical forms called trees, with application to the theory of chemical combinations.  Report of the British Association for the Advancement of Science, 45:257–305, 1875.
  * [9] R. Chiewvanichakorn, C. Wang, Z. Zhang, A. Shurbevski, H. Nagamochi, and T. Akutsu.  A method for the inverse QSAR/QSPR based on artificial neural networks and mixed integer linear programming, 2020.  ICBBB2020, paper K0013.
  * [10] Y. Dinitz, A. Itai, and M. Rodeh.  On an algorithm of Zemlyachenko for subtree isomorphism.  Information Processing Letters, 70(3):141–146, 1999.
  * [11] H. Fujiwara, J. Wang, L. Zhao, H. Nagamochi, and T. Akutsu.  Enumerating treelike chemical graphs with given path frequency.  Journal of Chemical Information and Modeling, 48(7):1345–1357, 2008\.
  * [12] R. Gugisch, A. Kerber, A. Kohnert, R. Laue, M. Meringer, C. Rücker, and A. Wassermann.  MOLGEN 5.0, a molecular structure generator.  In Advances in Mathematical Chemistry and Applications, pages 113–138. Elsevier, 2015.
  * [13] T. Imada and H. Nagamochi.  Indexing all rooted subgraphs of a rooted graph.  IEICE Transactions on Information and Systems, 95(3):712–721, 2012\.
  * [14] Y. Ishida, L. Zhao, H. Nagamochi, and T. Akutsu.  Improved algorithms for enumerating tree-like chemical graphs with given path frequency.  Genome Informatics, 21:53–64, 2008.
  * [15] C. Jordan.  Sur les assemblages de lignes.  Journal für die reine und angewandte Mathematik, 70:185–190, 1869.
  * [16] H. Mauser and M. Stahl.  Chemical fragment spaces for de novo design.  Journal of Chemical Information and Modeling, 47(2):318–324, 2007\.
  * [17] T. Miyao, H. Kaneko, and K. Funatsu.  Inverse QSPR/QSAR analysis for chemical structure generation (from y to x).  Journal of Chemical Information and Modeling, 56(2):286–299, 2016\.
  * [18] S.-i. Nakano and T. Uno.  Efficient generation of rooted trees.  Technical Report NII-2003-005E, National Institute of Informatics, 2003\.
  * [19] S.-i. Nakano and T. Uno.  Generating colored trees.  Lecture Notes in Computer Science, 3787:249–260, 2005.
  * [20] J. E. Peironcely, M. Rojas-Chertó, D. Fichera, T. Reijmers, L. Coulier, J.-L. Faulon, and T. Hankemeier.  OMG: open molecule generator.  Journal of Cheminformatics, 4(1):21, 2012.
  * [21] M. Shimizu, H. Nagamochi, and T. Akutsu.  Enumerating tree-like chemical graphs with given upper and lower bounds on path frequencies.  BMC Bioinformatics, 12(14):S3, 2011.
  * [22] M. I. Skvortsova, I. I. Baskin, O. L. Slovokhotova, V. A. Palyulin, and N. S. Zefirov.  Inverse problem in QSAR/QSPR studies for the case of topological indices characterizing molecular shape (Kier indices).  Journal of Chemical Information and Computer Sciences, 33(4):630–634, 1993.
  * [23] M. Suzuki, H. Nagamochi, and T. Akutsu.  A 2-phase algorithm for enumerating tree-like chemical graphs satisfying given upper and lower bounds.  IPSJ SIG Tech. Reports, 28(17):1–8, 2012.
  * [24] M. Suzuki, H. Nagamochi, and T. Akutsu.  Efficient enumeration of monocyclic chemical graphs with given path frequencies.  Journal of Cheminformatics, 6(1):31, 2014.
  * [25] M. Vogt and J. Bajorath.  Chemoinformatics: a view of the field and current trends in method development.  Bioorganic & Medicinal Chemistry, 20(18):5317–5323, 2012.