# A Pub-Sub Architecture to Promote Blockchain Interoperability ††thanks: This
project has been supported by _The Linux Foundation_ as part of the
_Hyperledger Summer Internships_ program under the _Towards Blockchain
Interoperability with Hyperledger_ project.

Sara Ghaemi1, Sara Rouhani2, Rafael Belchior3, Rui S. Cruz3, Hamzeh Khazaei4,
Petr Musilek1  1University of Alberta, Edmonton, Canada, {sghaemi,
<EMAIL_ADDRESS>2University of Saskatchewan, Saskatoon, Canada,
<EMAIL_ADDRESS>3Instituto Superior Técnico, Universidade de Lisboa,
Lisboa, Portugal, {rafael.belchior<EMAIL_ADDRESS>4York
University, Toronto, Canada<EMAIL_ADDRESS>
###### Abstract

The maturing of blockchain technology leads to heterogeneity, where multiple
solutions specialize in a particular use case. While the development of
different blockchain networks shows great potential for blockchains, the
isolated networks have led to data and asset silos, limiting the applications
of this technology. Blockchain interoperability solutions are essential to
enable distributed ledgers to reach their full potential. Such solutions allow
blockchains to support asset and data transfer, resulting in the development
of innovative applications.

This paper proposes a novel blockchain interoperability solution for
permissioned blockchains based on the publish/subscribe architecture. We
implemented a prototype of this platform to show the feasibility of our
design. We evaluate our solution by implementing examples of the different
publisher and subscriber networks, such as Hyperledger Besu, which is an
Ethereum client, and two different versions of Hyperledger Fabric. We present
a performance analysis of the whole network that indicates its limits and
bottlenecks. Finally, we discuss the extensibility and scalability of the
platform in different scenarios. Our evaluation shows that our system can
handle a throughput in the order of the hundreds of transactions per second.

###### Index Terms:

Distributed Ledger Technology, Blockchain, Interoperability, Publish/Subscribe

##  I Introduction

The distributed ledger technology (DLT) enables a set of independent untrusted
nodes to establish an agreement on the state of a shared ledger. Blockchain, a
type of DLT, is mostly known for its use cases in cryptocurrencies such as
Bitcoin [1], Ethereum [2], and XRP[3], among others. However, the technology
can be used for more diverse applications and industries. Some examples are
biomedical and health care [4, 5], Internet of Things (IoT) [6, 7], public
administration [8, 9], and cloud computing [10, 11]. Since each industry has
its own unique sets of requirements, many isolated permissioned and
permissionless blockchains have been introduced, posing limits regarding its
interoperability.

Currently, developers commit to a single blockchain solution, and they cannot
use the capabilities of more than one blockchain (vendor lock-in). These
isolated, incompatible networks have resulted in silos of data and assets,
which cannot be used from other networks. Blockchain interoperability
solutions are needed to enable asset and information transfer from one
blockchain to another. However, interoperability for blockchains encounters
challenges that make it different from interoperability for other software
networks.

First, each interoperability solution should take into account the differences
in the architecture of blockchain networks. Although all blockchains have an
immutable ledger that stores the history of assets, they usually reach a
consensus on the order of transactions using different algorithms. As a
result, their underlying network and their validation mechanisms can be
different from other blockchains. Each blockchain network that participates in
the interoperation is independent and in full control of their assets and
information. Moreover, the interoperability solutions should not require
significant changes in the underlying blockchain networks, and it should be
usable with minimal effort for existing blockchains.

This paper aims to tackle this problem by proposing a blockchain
interoperability solution based on the publish/subscribe architecture across
permissioned blockchains. We have implemented a broker blockchain that acts as
a middleman in the interoperability process between the source and the
destination networks. It is worth noting that since the broker is itself a
blockchain network, it is not a central authority and peers from the source
and destination blockchains can also participate in the governance of this
network. The _broker_ blockchain keeps a copy of the information that needs to
be shared in the form of a _topic_. A topic has a name, message, publisher,
and a set of subscribers. The _publisher_ is the source blockchain network
that wants to share the information. It is responsible for creating the topic
on the broker and publishing it to the corresponding topic whenever the
information needs an update. The _subscribers_ are the destination networks
that need some information from the source network. As soon as the subscriber
network subscribes to a topic, the broker network notifies it whenever a
change happens. This solution enables interoperability between blockchains
with minimal effort.

We used a performance benchmark tool to analyze the performance of the
implemented prototype of the platform. The throughput and average latency for
different functionalities of the broker network were investigated. The results
indicate that our network can handle hundreds of transactions per second.
Moreover, the evaluations identified the PublishToTopic functionality to be
the broker network’s bottleneck.

The rest of this paper is organized as follows. Section II gives a summary of
the related work on blockchain interoperability and blockchain-based
publish/subscribe protocols. Section III introduces the system design details
for the proposed interoperability solution. Section IV demonstrates the
implementation and deployment details of the platform, while section V
presents its performance evaluation. Section VI outlines some discussions on
the design and evaluation of the platform and section VII concludes the paper.

##  II Related Work

In this section, we discuss the related work in the field of blockchain
interoperability, as well as blockchain-based publish/subscribe protocols.

###  II-A Blockchain Interoperability

The emergence of the blockchain interoperability research area has brought
attention from both the industry and academia. Blockchain interoperability
projects have been tackled as early as in 2016 [12].

A recent survey classifies blockchain interoperability studies in three
categories: Cryptocurrency-directed interoperability approaches, Blockchain
Engines, and Blockchain Connectors [12]. Cryptocurrency-directed approaches
are mostly industry solutions that provide interoperability across public
blockchains. This category has a focus on asset interoperability and is
divided into sidechains, hash lock time contracts, notary schemes, and hybrid
solutions. Sidechains allow for offloading transactions to a secondary chain,
enhance performance, and provide features that the main chain would not
provide. Sidechains also enable the representation of a token from the
mainchain at the secondary chain. Some sidechain solutions include the BTC
Relay [13], Zendoo [14], and RSK [15]. Hash lock time contract solutions
enable cross-chain atomic operations using smart contracts. Wanchain uses this
scheme and provides loan services with cryptocurrencies [16]. Notary schemes
are centralized or decentralized entities that mediate token exchange (e.g.,
cryptocurrency exchanges). Finally, hybrid solutions combine characteristics
from previous approaches. The cryptocurrency-directed approaches only work for
transferring different types of cryptocurrencies between blockchain network.
As a result, these approaches cannot be used for permissioned blockchains with
arbitrary assets and smart contracts, which are the focus of this paper.

The second category is blockchain engines, which enable creating customized
blockchains that can interoperate by providing reusable data, network,
consensus, and contract layers. Platforms like Polkadot [17] and Cosmos [18]
provide such infrastructure, with “free interoperability” among the instances
they allow to create. These approaches are fundamentally different from what
has been proposed in this paper. Instead of enabling blockchain
interoperability for currently running blockchains, blockchain engines propose
blockchain networks that are interoperable by design. As a result, these
solutions cannot be used for currently running permissioned blockchains.

The Blockchain Connector category is composed of interoperability solutions
that are not cryptocurrency-directed or blockchain engines. They include
trusted relays, blockchain agnostic protocols, blockchain of blockchains
solutions, and blockchain migrators. Each of these categories responds to a
particular set of use cases. Trusted relays allow discovering the target
blockchains, often appearing in a permissioned blockchain environment where
trusted escrow parties route cross-blockchain transactions. An interesting
trusted relay approach is Hyperledger Cactus [19], the most recent Hyperledger
project aiming to connect a client to several blockchains, whereby
transactions are endorsed by trusted validators. Cactus focuses on providing
multiple use case scenarios via a trusted consortium. Another trusted relay is
proposed by Abebe et al. [20], which is an interoperability solution between
Fabric networks using Hyperledger Fabric chaincode and a protocol-buffer based
communication protocol. Blockchain agnostic protocols enable cross-blockchain
communication between arbitrary distributed ledger technologies, including
refactoring and making changes to each blockchain. Blockchain of blockchains
are approaches that allow users to build decentralized applications using
multiple blockchains. Finally, blockchain migrators enable the state of one
blockchain to be migrated to another blockchain. Simple blockchain migrations
have already been performed, paving the direction for complex blockchain
migrations [12].

Our pub-sub solution is considered a trusted relay (although decentralized),
as it contains a blockchain mediating communication across heterogeneous
blockchains [12]. While trusted relays can provide a straightforward way of
achieving interoperability, most of them are not trustless (e.g., contain a
centralization point). Our solution is a decentralized trusted relay that
implements a pub/sub system, anchored on the trust that underlying blockchains
offer.

###  II-B Blockchain-based Publish/Subscribe Protocol

The blockchain technology has been applied to the pub/sub paradigm in a few
previous studies. However, those studies adopt blockchain to address the
existing problems in other areas, such as IoT [21], supply chain [22], multi-
tenant edge cloud [23], and digital trading [24].

Huang et al. [23] exploit blockchain technology to enhance the security of
pub/sub communications in multi-tenant edge clouds. Most topic-based and
broker-enabled pub/sub streaming systems use centralized cloud servers to
store sensitive metadata and access control lists (ACL), which can compromise
the confidentiality, anonymity, and integrity of tenants’ data. Alternatively,
critical data such as ACL and identity information, as well as the hash of raw
messages, and operation logs, can be stored on the blockchain to guarantee
data security and integrity. Their smart contracts implement access control
mechanisms to authorize requests from publishers and subscribers.

Trinity [22] proposes a blockchain-based distributed publish/subscribe broker
to solve the existing flaws of centralized brokers in IoT and supply chain
monitoring applications. Trinity has three main components: blockchain
network, broker, and clients. The blockchain network is responsible for
consensus in the system and persistent storage. The broker handles the
communications between the blockchain network and clients. The clients are the
publishers and subscribers of the topics. The blockchain network is pluggable,
and the authors have used Tendermint, Hyperledger Fabric, Ethereum, and IOTA.
The broker has used the Mosquitto MQTT broker, which provides a single point
of failure.

Zhao et al. [25] have proposed Secure Pub-Sub (SPS), which provides fair
payment based on a reputation for publishers and subscribers in cyber-physical
systems. They use the Bitcoin’s network to enable payments between the
entities, and they propose a reputation mechanism that helps calculate the
price of data.

Lv et al. [21] presents a decentralized privacy-preserving pub/sub model for
IoT systems to solve centralized brokers’ problems such as single point of
failure, data tampering due to corrupter brokers, and heavy encryption
algorithms. The presented model applies public-key encryption with equality
test [26] and ElGamal [27] to protect participants’ (both publishers and
subscribers) privacy. A system prototype is implemented and evaluated against
the feasibility of the proposed model.

Bu et al. [24] and Zupan et al. [28] have proposed blockchain-based pub/sub
brokers to address the drawbacks of traditional pub/sub systems such as
privacy and accountability. However, they have not explained their
implementation and evaluation in their studies.

All these studies adopt blockchain to improve the centralized predicaments in
traditional pub/sub systems in distinct application domains, whereas our paper
focuses on establishing robust and practical interoperability between
permissioned blockchains with different architectures and infrastructures. To
the best of our knowledge, our paper is the first study that enhances
blockchain interoperability utilizing the pub/sub communication model across
heterogeneous blockchains (Hyperledger Fabric/Hyperledger Besu).

##  III System Design

In this section, we first discuss the design principles that a blockchain
interoperability solution should follow. We then propose our interoperability
solution and explain its components and message flow.

Figure 1: Architecture of the platform and the message flow.

###  III-A Design Principles

Blockchain interoperability aims to enable applications to use the assets and
information available on blockchains other than their main blockchain network
[12]. This allows for a greater range of applications. A blockchain
interoperability solution should take into account the following design
principles:

  * •

The blockchain networks are independent, and they may have different
architectures.

  * •

The blockchain networks are in full control of their assets and information.

  * •

The transfer protocol should be technology agnostic.

  * •

The interoperability solution should not require significant changes in the
source and destination networks.

  * •

The blockchain networks should be able to incorporate the solution with
minimal effort.

Following the mentioned principles, we present our solution, which allows
interoperability based on a publish/subscribe architecture.

###  III-B Components

The platform proposed in this paper aims to solve the interoperability problem
of permissioned blockchains using the publish/subscribe pattern. When a
blockchain wants to use the data from another blockchain, there needs to be a
way to fetch and transfer this data between the networks securely. Moreover,
if the data changes in the source network, the destination network should be
notified of the change. Figure 1 shows the architecture of the platform and
the message flow.

The publisher blockchain is the blockchain network that sends the data, also
referred to as the source network. For a publisher to participate in this
platform, it needs to run the appropriate connector smart contract on its
blockchain and enroll as a publisher in the broker. The publisher can then
create as many topics as they want and use the connector smart contract to
publish the changes to the topic.

The subscriber blockchain is the blockchain network that received the data,
also referred to as the destination network. Similar to the publisher, the
subscriber also needs to run the appropriate connector smart contract and
enroll as a subscriber. It can then subscribe to any topic available on the
broker blockchain. Every time the topic changes, the broker notifies the
subscriber by invoking the connector smart contract. There can exist many
subscribers for a topic.

The broker blockchain is the core component of the platform. It is a
blockchain network that stores all the information about the topics and the
blockchains that participate in the interoperability process. Since the broker
is a blockchain, operations regarding interoperation are immutable and
traceable, providing a robust basis for accountability. The broker has two
different smart contracts, the connector smart contract and the topics smart
contract. The connector smart contract stores the information about the
participating blockchain networks and how the broker can interact with them.
The topics smart contract is responsible for storing the information about the
topics such as their publisher, subscribers, and the latest message.

###  III-C Message Flow

The complete interoperation process in the platform is shown in Figure 1. For
simplicity, only one publisher and one subscriber blockchain are shown in this
figure. However, for each topic, there can be an unlimited number of
subscribers and, in general, there is no limit on the number of publisher and
subscriber blockchains. A detailed explanation of each step in Figure 1
follows:

  1. 1.

For any blockchain network to interact with the broker blockchain, it must
enroll in the connector smart contract. During this process, the information
that the broker needs to be able to interact with the blockchain is registered
in the connector smart contract. As a result, the publisher is required to
enroll in the connector smart contract as a publisher. This step only needs to
be performed once, when the publisher wants to create its first topic. It can
then create topics or publish to existing ones without the need to be enrolled
again.

  2. 2.

A publisher that is registered in the connector smart contract can create a
new topic. In this step, the publisher needs to specify a name for the topic
and the initial topic message. This step only needs to be executed once for
each topic.

  3. 3.

Similar to the publisher blockchain, the subscriber blockchain should also
enroll in the connector smart contract. This step only needs to be done once,
when the subscriber wants to subscribe to a topic for the first time.

  4. 4.

To receive a notification when a topic has been changed, the subscriber should
subscribe to the topic by sending a request to the topics smart contract. This
results in the subscriber being added to the list of all subscribers for the
topic. This step only needs to be performed once for each topic.

  5. 5.

Whenever needed, the application in the publisher blockchain can update the
topic by sending a request to the connector smart contract.

  6. 6.

The connector smart contract sends a publish request to the topics smart
contract for the existing topic.

  7. 7.

As soon as a publish request is received by the topics smart contract, the
smart contract fetches the information about all the subscribers of the topic
from the connector smart contract. It includes information on how the broker
can interact with each of the subscribers.

  8. 8.

The topics smart contract then uses the data fetched from the connector smart
contract to notify all the subscribers of the change in the topic. This
happens by sending an update request to the connector smart contract in each
of the subscriber networks.

  9. 9.

In each subscriber network, the connector smart contract receives the update
for the topic and notifies the application.

##  IV Implementation and Deployment

A prototype of the proposed platform has been implemented as a proof-of-
concept to demonstrate the feasibility of the design. This project is a
Hyperledger Labs open-source project111https://github.com/hyperledger-
labs/pubsub-interop, under the Apache License, Version 2.0. To show the
interoperability capabilities of the platform, we implemented two example
subscriber networks, as well as an example publisher network. The broker and
the example publisher are implemented using two different Hyperledger Fabric
V2 [29] networks. The two example subscribers are implemented using
Hyperledger Fabric V1.4 [30, 31], and Hyperledger Besu [32]. In this section,
the implementation and deployment details of the broker and the example
networks are discussed.

###  IV-A Broker Blockchain

The broker blockchain acts as a messaging broker between other blockchains to
enable interoperability. When choosing the blockchain solution to implement
the broker network, we had to ensure that the solution fits well with the
needs of this platform. First, since we aim to address interoperability in
permissioned blockchains, the broker also needs to be permissioned. Moreover,
many permissioned blockchains are enterprise-level, and they may have privacy
and governance concerns, which our broker aims to addresses using blockchain
that enables immutability and traceability. We need a blockchain solution for
the broker network that considers these needs. Finally, the smart contracts
that need to be implemented on the broker blockchain are complicated, and the
blockchain needs to support this kind of smart contract.

Hyperledger Fabric is an open-source permissioned blockchain that has been
designed for enterprise use cases. Unlike the open permissionless blockchains
that have scalability issues, Fabric enables high transaction throughput and
low transaction confirmation latency. The architecture of Hyperledger Fabric
is highly modular and configurable, which enables customization for each
specific use case. Many blockchains only support smart contracts written in
non-standard and domain-specific programming languages, making it impossible
to implement smart contracts that require a Turing-complete language. On the
other hand, Hyperledger Fabric supports smart contracts in general-purpose
programming languages such as Go, Node.js, and Java [29].

In the broker network, we leverage the capabilities of Hyperledger Fabric V2.2
to implement a messaging broker. We implement two chaincodes called the topics
and the connector to support the features needed for the broker. The topics
chaincode is responsible for keeping all the topics and their corresponding
details. In Hyperledger Fabric, everything is stored as a key-value pair. In
the topics smart contract, the key is a unique topic ID. The value is an
object that includes the following properties: name, publisher, subscribers,
and message. The name of a topic is a string value set by the publisher when
creating the topic. Each topic has one publisher, the blockchain network that
has registered the topic on the broker, which is the only blockchain that can
make changes to the topic. The subscribers’ property stores a list of all the
blockchains that have subscribed to the topic. It is worth mentioning that the
publisher and the subscribers’ properties only accept objects stored on the
connector blockchain.

The connector chaincode is responsible for storing the connection details of
other blockchain networks. Similar to the topics chaincode, the key in the
key-value pair used in this chaincode is a unique ID for each blockchain. The
value is an object that has the following properties: name, type, server IP,
port, extra information. The name is a string value that can be selected when
enrolling in the network. Type shows what kind of blockchain technology this
network is using. Currently, support for Fabric and Besu has been implemented,
and other blockchains will be added in future versions. The server IP and port
are used by the broker blockchain to access the publisher or subscriber using
an HTTP request. The extra information property stores network-specific
details that may be needed when interacting with the blockchains. For
instance, for a Hyperledger Besu network, this includes the private key,
address, and the contract application binary interface (ABI) that the broker
should use to send a request to the Besu network. This kind of implementation
allows our solution to be extendable to other blockchains, independent of
their underlying network.

To better understand how the topics and connector chaincodes work, we need to
discuss their implemented functionalities. Figure 2 shows the UML class
diagram of the implemented chaincodes. The Hyperledger Fabric contract API
provides an interface for developing smart contracts and applications. Each
developed chaincode should extend the contract class from this API and then
implement the required logic. In each smart contract, the InitLedger function
is used to create a set of initial assets on the ledger when the chaincode is
deployed. In the topics chaincode, the CreateTopic function is used to create
a new asset of type topic. The QueryTopic and the QueryAllTopics functions can
be used to query one specific topic and all the existing topics, respectively.
The connector chaincode implements the same initialize, create, and query
functionalities but for assets of type blockchain.

Figure 2: UML class diagram of the implemented chaincodes.

Other than the mentioned functions, the topics blockchain also implements
SubscribeToTopic, UnsubscribeFromTopic, and PublishToTopic functionalities.
When a destination blockchain wants to get notified of a topic’s change, it
subscribes to that topic by invoking the SubscribeToTopic function. The
subscriber can also unsubscribe from the topic at any time by invoking the
UnsubscribeFromTopic function. Finally, the PublishToTopic function is used by
the source blockchain network when they want to update the topic’s message. An
invoke request to this function triggers update requests to all the
subscribers of the topic. Algorithm 1 shows the detailed implementation of the
PublishToTopic method. First, the broker retrieves the latest version of the
topic from the ledger. In the case that no topic was found, it immediately
throws an error. Next, the topic’s message is updated with the new message
value and the topic’s state is put to the ledger. The next step is for the
broker to notify all the subscribers. For each of the subscribers of the
topic, the blockchain object is queried from the connector contract. This
inter-chaincode communication is also shown in Figure 2. Then, given the type
of subscriber blockchain, the steps to invoke the remote network are followed.

Input: topicID, newMessage

Result: Subscribers are notified of the new message

1 topicState $\leftarrow$ getState(topicID)

2 if  _!topicState_ then

3 throw error

4

5 end if

6topicState.message $\leftarrow$ newMessage

7 putState(topicID, topicState)

8 for  _subID in topicState.subscribers _ do

9 subState $\leftarrow$ query $subID$ from connector contract

10 if  _subState.type = Fabric_ then

11 follow steps to invoke a remote Fabric network

12 else if  _subState.type = Besu_ then

13 follow steps to invoke a remote Besu network

14 end if

15

16 end for

Algorithm 1 PublishToTopic Method

###  IV-B Subscriber Blockchains

The subscriber, or destination blockchain, is the blockchain that requires
information from another blockchain to run a task. For the subscriber to be
able to participate in the platform, it needs to have the appropriate
connector smart contract deployed on it. We have implemented subscriber
connector contracts for Hyperledger Fabric V1.4 and Hyperledger Besu. However,
the connector is a simple smart contract that can also be developed by the
owners of the subscriber blockchain. This smart contract needs to keep track
of the topics that the subscriber has subscribed to and store their latest
version for other smart contracts to access at any time. Two example
subscriber networks have been implemented to demonstrate the interoperability
capabilities of the platform.

The first example subscriber is implemented using Hyperledger Fabric V1.4. The
second example subscriber is implemented using Hyperledger Besu, an open-
source Ethereum client that supports private and permissioned blockchains.
Besu can create networks that work based on a proof of work (PoW) or a proof
of authority (PoA) consensus algorithm. In this work, we implemented a PoW
network using Besu, which can be thought of as a private Ethereum network. We
then implemented a connector smart contract in Solidity to keep a record of
the subscribed topics.

###  IV-C Publisher Blockchains

The publisher, or the source blockchain, is the blockchain network that needs
to send information to other blockchains. Similar to what we have in the
subscriber blockchain, a connector smart contract is also required for the
publishers. However, the connector is slightly different in the publisher. The
publisher connector should not only keep track of the topics, but it should
also connect to the broker blockchain to publish the topics. We implemented an
example publisher network using Hyperledger Fabric V2.2.

##  V Experimental Evaluation

In this section, we focus on evaluating the performance of the implemented
prototype of the broker blockchain. The goal is to see how the throughput and
latency of the system changes in different scenarios. We have conducted two
series of experiments to achieve this goal. The first set of experiments aims
to show the performance metrics of different functionalities in the broker
blockchain. The second set of experiments focuses on the publish function,
which is the most important and time-consuming component of the broker
blockchain.

We have used Hyperledger Caliper [33] to run the experiments. Hyperledger
Caliper is an open-source blockchain performance benchmark tool that allows
performance measurement for different blockchains, such as Hyperledger Fabric,
Ethereum, Hyperledger Besu. In Hyperledger Caliper, the workloads or
benchmarks are responsible for generating the content of each transaction that
is sent to the blockchain network. Given the network and benchmark
configurations, Caliper uses a set of independent workers to send scheduled
requests to the blockchain network and monitor the response. When the tests
are finished, Caliper generates a performance report consisting of the average
throughput and minimum, maximum, and average latency throughout the test. The
throughput shows the number of transactions that were processed in the system
in a given time. The latency shows the amount of time it takes for a
transaction to be finished and added to the ledger.

Table I summarizes the specifications of each component in the experimental
evaluation. We have set up Hyperledger Caliper on a separate machine to ensure
that its process does not affect the performance of the broker network. We use
five workers, a fixed rate controller, and a test duration of 60 seconds for
each benchmark round. The broker network is implemented using Hyperledger
Fabric V2.2 with two peer organizations and an orderer organization, each with
an independent certificate authority. Each of the peer organizations hosts one
peer node, and the orderer uses Raft implementation. Two chaincodes have been
implemented that run on one channel. The Fabric subscriber, implemented using
Fabric V1.4, has two organizations, each hosting two peers. The whole
subscriber network uses one Solo orderer and one Fabric certificate authority.
The Besu subscriber implements a private Ethereum network with PoW consensus
algorithm. The publisher has been implemented using Hyperledger Fabric V2.2
with the same configurations as the broker network.

TABLE I: Experimental evaluation setup Component | Type | CPU | RAM | Disk
---|---|---|---|---
Caliper Benchmark | N/A | 8 vCPU | 30 GB | 288 GB
Broker | Fabric V2.2 | 8 vCPU | 30 GB | 288 GB
Fabric Subscriber | Fabric V1.4 | 2 vCPU | 7.5 GB | 36 GB
Besu Subscriber | Besu | 2 vCPU | 7.5 GB | 36 GB
Publisher | Fabric V2.2 | 2 vCPU | 7.5 GB | 36 GB

The first set of experiments focuses on the performance evaluation of broker
blockchain. In these experiments, we conduct a series of tests using
Hyperledger Caliper for each functionality that broker blockchain offers.
Figure 2 summarizes all these functionalities. Each type of transaction goes
through a specific set of steps in Hyperledger Fabric, which highly influences
the response time for that transaction. For instance, an invoke transaction
goes through endorse, order and commit steps. On the other hand, a query
transaction is not transferred to the orderer, and the response is immediately
sent back by the peer. The create actions in the connector and topics smart
contract are invoke actions that have very similar implementations. The same
goes for the query actions in the two smart contracts. As a result, it would
be repetitive to run performance evaluation experiments for both smart
contracts. Therefore, we run the experiments on the topics smart contract.

The topics smart contract has five important functionalities: create a topic,
query a topic, publish to a topic, subscribe to a topic, and unsubscribe from
a topic. For each of these actions, we run a set of experiments by changing
the transaction send rate in the Hyperledger Caliper benchmark. The goal is to
see how the system’s throughput and average latency changes when the send rate
is changed. Figure 3 shows the details of these experiments. It can be seen
that the send rate follows the same pattern for all the actions except for
PublishToTopic. The reason for this difference is that the PublishToTopic
action takes more time and needs more resources to run compared to other
actions. Consequently, broker blockchain’s hardware limits are reached when
the network receives more than roughly 100 publish transactions in each
second. We discuss the behaviour of the network with different PublishToTopic
requests in the second set of experiments shown in Figure 4. As a result of
this limitation, we lowered the send rate for the PublishToTopic action in our
experiments.

Figure 3: The trend of system throughput and average latency for various
functionalities throughout time with the change of request send rate. The
words publish, sub, unsub, query, and create in the plots stand for
PublishToTopic, SubscribeToTopic, UnsubscribeFromTopic, QueryTopic, and
CreateTopic functions, respectively.

It can be seen in Figure 3 that the SubscribeToTopic, UnsubscribeFromTopic,
and CreateTopic have similar behaviours under the same send rate. These three
actions are of type invoke. Since an invoke transaction proposes a change in
the blockchain, it needs to go through the consensus algorithm, which can be
time-consuming. Since the three actions are of the same type, and none need
heavy computations in execution, the system throughput and latency for all of
them are similar. As shown in the experimentation results, when the send rate
is lower than a threshold (around 160 TPS in this case), the throughput is the
same as the send rate, and the average latency is only a few hundred
milliseconds (around 100 to 300 milliseconds). This shows that with send rates
below the threshold, all transactions are processed immediately. When the
number of create, subscribe, or unsubscribe transactions sent in each second
is more than the threshold, the broker network’s processing limit is reached.
The throughput is limited to the broker’s maximum capacity (around 160 TPS),
and the transactions are queued before being processed, which results in an
increase in the latency. Figure 3 shows that when the send rate for the
create, subscribe, or unsubscribe transactions is around 210 TPS, the average
latency increases to about 11 seconds. The latency keeps increasing with
higher send rates and reaches approximately 50 seconds with a send rate of 360
TPS.

The QueryTopic action is different from the previous ones. Since a query
transaction does not go through the consensus protocol, its process is much
faster. The send rate pattern used for the query is similar to that of create,
subscribe, and unsubscribe. However, the throughput and average latency act
very differently. The throughput follows the same pattern as the send rate,
and the average latency is around 10 milliseconds throughout the whole
experiment. These results show that this experiment does not reach the process
limit for QueryTopic.

Finally, the PublishToTopic is similar to create, subscribe, and unsubscribe
because they are all invoke transactions. However, the publish action requires
stronger computations. As mentioned earlier, since the publish action needs
more time and computational resources, we use a different send rate pattern.
If we were to use the same send rate, the broker blockchain’s hardware limits
would be reached, resulting in the experiments being halted. We discuss this
in more detail in the second set of experiments shown in Figure 4. To ensure
that the performance of the remote source and destination networks do not
influence the performance evaluation of the broker network, we only send dummy
requests to the subscriber networks during the experiments. It can be observed
from Figure 3 that the publish action reaches the processing limit of the
broker network much faster than the other invoke transactions. With send rates
of about 70 TPS and more, the throughput is limited to 65 TPS. The average
latency for the publish action has more fluctuations compared to other invoke
actions. The main reason for this fluctuation is that in the publish method,
depending on the number of subscribers that the topic has, the processing time
can vary. In this experiment, the average latency gets as high as 80 seconds,
with the send rate of 110 TPS.

Figure 4: The trend of system throughput, average latency, and request success
rate throughout time with the change of send rate.

Given the limits of the PublishToTopic action, we decided to run some
additional experiments on this type of transaction. This experiment aims to
find the broker network’s limits and discover what happens when the limit is
reached. In the previous experiment, we discovered that the processing limit
for the publish transactions is reached at the sent rate of around 70 TPS. We
also observed that the latency increases and the throughput is limited for
send rates above 70 TPS and below 110 TPS. However, we would like to know what
happens if the send rate is more than 110 TPS. In this experiment, we linearly
increase the send rate from 50 to 150 TPS and observe the throughput, latency,
and transaction success rate. Figure 4 shows the results of this experiment.
Similar to the previous experiment, we see that the throughput is limited, and
the latency is increased when the send rate reaches 70 TPS. Nevertheless, the
interesting change happens at the 120 TPS send rate. At this point, a
significant drop in the throughput and a significant rise of latency are
observed. Moreover, the transaction success rate is not 100% anymore. From
this point on, a portion of the transactions fail since the broker network has
reached its hardware limits.

##  VI Discussion and Future Work

To enable blockchain interoperability, we have proposed the use of a broker
blockchain as a middleman. The broker blockchain acts as a decentralized
trusted relay between the source and destination network. Using a relay
enables the interoperating networks to transfer data with minimal effort.
Verifying the data and handling the communications between different
blockchain networks can be delegated to the relay. As a result, there is no
need for source and destination networks to make fundamental changes to their
underlying structure. The relay network is also a blockchain network; while
exploiting all desirable features offered by blockchain, it runs smart
contracts implementing the interoperability functionality. Therefore, the
broker blockchain allows the interoperation to be seamless, transparent, and
secure.

The platform proposed in this paper stores the destination and source
blockchains as assets on the distributed ledger. As a result, a large number
of blockchains can be supported as there are no limits on the number of
assets. A study on the performance of Hyperledger Fabric V1.1 shows that the
network can scale to 100+ peers [34, 35]. As the broker network has been
implemented using Fabric V2.2, we expect this number to be even higher in our
network. Therefore, at least 100 peers can participate in the governance of
the broker blockchain.

In the current prototype of our platform, every participant can subscribe to
all existing topics, and there is no access control mechanism implemented. The
private data feature presented by Hyperledger Fabric can be utilized to
establish private channels in the broker blockchain and keep data topics
separate from other organizations. Furthermore, an access control mechanism
can be added to our pub/sub system to control the flow of data at a more
granular level, for instance, the decentralized access control proposed by
Rouhani et al. [36].

It is also possible to conduct authorization processes with minimal
information disclosure if one uses the novel self-sovereign based access
control model [37]. This way, we could model each blockchain as an agent to
prove that they own specific credentials needed for the access control
process. Moreover, the publisher network may choose only to make a topic
available to a subset of subscribers. Access control can be used to manage the
blockchains that can access each topic.

##  VII Conclusion

With blockchain technology gaining popularity in academia and industry, many
blockchain networks are being introduced worldwide. These networks are highly
isolated and incompatible with each other, resulting in silos of data and
assets. Blockchain interoperability solutions can revolutionize this
technology by enabling data and asset transfers between homogeneous and
heterogeneous blockchains. In this paper, we proposed a blockchain
interoperability solution based on the publish/subscribe architecture. Our
solution consists of a broker blockchain that keeps a record of the data being
transferred between blockchain networks. The blockchains that aim to
participate in the interoperability can connect to the broker network as
publishers or subscribers, depending on their role. A prototype of the broker
blockchain has been implemented using Hyperledger Fabric. Moreover, an example
publisher and two example subscribers have been implemented using Hyperledger
Besu and two versions of Hyperledger Fabric to show that the design works for
heterogeneous blockchains. The network’s performance has been analyzed using a
benchmark tool to identify the platform’s limits and bottlenecks. The
implementation and evaluations indicate the feasibility of the idea with
satisfactory performance, and the bottleneck is identified to be the process
of publishing a new message to a topic. Finally, a discussion on the
extensibility, scalability, and possible improvements of the system is
presented.

## References

  * [1] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system.” https://bitcoin.org/bitcoin.pdf, 2008.  Last accessed 2020-07-17.
  * [2] G. Wood et al., “Ethereum: A secure decentralised generalised transaction ledger,” Ethereum project yellow paper, vol. 151, no. 2014, pp. 1–32, 2014.
  * [3] B. Chase and E. MacBrough, “Analysis of the xrp ledger consensus protocol,” arXiv preprint arXiv:1802.07242, 2018.
  * [4] T.-T. Kuo, H.-E. Kim, and L. Ohno-Machado, “Blockchain distributed ledger technologies for biomedical and health care applications,” Journal of the American Medical Informatics Association, vol. 24, no. 6, pp. 1211–1220, 2017.
  * [5] S. Rouhani, L. Butterworth, A. D. Simmons, D. G. Humphery, and R. Deters, “Medichain tm: a secure decentralized medical data asset management system,” in 2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData), pp. 1533–1538, IEEE, 2018.
  * [6] T. M. Fernández-Caramés and P. Fraga-Lamas, “A review on the use of blockchain for the internet of things,” IEEE Access, vol. 6, pp. 32979–33001, 2018.
  * [7] C. Fan, H. Khazaei, Y. Chen, and P. Musilek, “Towards a scalable dag-based distributed ledger for smart communities,” in 2019 IEEE 5th World Forum on Internet of Things (WF-IoT), pp. 177–182, IEEE, 2019.
  * [8] R. Belchior, M. Correia, and A. Vasconcelos, “JusticeChain: Using Blockchain To Protect Justice Logs,” in CoopIS 2019: 27th International Conference on Cooperative Information Systems, 2019.
  * [9] R. Belchior, A. Vasconcelos, and M. Correia, “Towards Secure, Decentralized, and Automatic Audits with Blockchain,” in European Conference on Information Systems, 2020.
  * [10] S. Ghaemi, H. Khazaei, and P. Musilek, “Chainfaas: An open blockchain-based serverless platform,” IEEE Access, vol. 8, pp. 131760–131778, 2020.
  * [11] J. H. Park and J. H. Park, “Blockchain security in cloud computing: Use cases, challenges, and solutions,” Symmetry, vol. 9, no. 8, p. 164, 2017.
  * [12] R. Belchior, A. Vasconcelos, S. Guerreiro, and M. Correia, “A survey on blockchain interoperability: Past, present, and future trends,” arXiv preprint arXiv:2005.14282, 2020.
  * [13] Ethereum Foundation and Consensys, “BTC-relay: Ethereum contract for Bitcoin SPV,” 2015.
  * [14] A. Garoffolo, D. Kaidalov, and R. Oliynykov, “Zendoo: a zk-SNARK Verifiable Cross-Chain Transfer Protocol Enabling Decoupled and Decentralized Sidechains,” tech. rep., 2020.
  * [15] S. Lerner tech. rep., RSK, 2015.
  * [16] J. Lu, B. Yang, Z. Liang, Y. Zhang, S. Demmon, E. Swartz, and L. Lu, 2017.
  * [17] G. Wood, “Polkadot: Vision for a Heterogeneous Multi-Chain Framework,” Whitepaper, 2017.
  * [18] J. Kwon and E. Buchman, “Cosmos Whitepaper,” tech. rep., 2016.
  * [19] H. Montgomery, H. Borne-Pons, J. Hamilton, M. Bowman, P. Somogyvari, S. Fujimoto, T. Takeuchi, T. Kuhrt, and R. Belchior, “Hyperledger Cactus Whitepaper.” https://github.com/hyperledger/cactus/blob/master/whitepaper/whitepaper.md, 2020\.  Last accessed 2020-09-28.
  * [20] E. Abebe, D. Behl, C. Govindarajan, Y. Hu, D. Karunamoorthy, P. Novotny, V. Pandit, V. Ramakrishna, and C. Vecchiola, “Enabling enterprise blockchain interoperability with trusted data transfer (industry track),” in Proceedings of the 20th International Middleware Conference Industrial Track, pp. 29–35, 2019.
  * [21] P. Lv, L. Wang, H. Zhu, W. Deng, and L. Gu, “An iot-oriented privacy-preserving publish/subscribe model over blockchains,” IEEE Access, vol. 7, pp. 41309–41314, 2019.
  * [22] G. S. Ramachandran, K.-L. Wright, L. Zheng, P. Navaney, M. Naveed, B. Krishnamachari, and J. Dhaliwal, “Trinity: A byzantine fault-tolerant distributed publish-subscribe system with immutable blockchain-based persistence,” in 2019 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), pp. 227–235, IEEE, 2019.
  * [23] B. Huang, R. Zhang, Z. Lu, Y. Zhang, J. Wu, L. Zhan, and P. C. Hung, “Bps: A reliable and efficient pub/sub communication model with blockchain-enhanced paradigm in multi-tenant edge cloud,” Journal of Parallel and Distributed Computing, 2020.
  * [24] G. Bu, T. S. L. Nguyen, M. P. Butucaru, and K. L. Thai, “Hyperpubsub: Blockchain based publish/subscribe,” in 2019 38th Symposium on Reliable Distributed Systems (SRDS), pp. 366–3662, IEEE, 2019.
  * [25] Y. Zhao, Y. Li, Q. Mu, B. Yang, and Y. Yu, “Secure pub-sub: Blockchain-based fair payment with reputation for reliable cyber physical systems,” IEEE Access, vol. 6, pp. 12295–12303, 2018.
  * [26] G. Yang, C. H. Tan, Q. Huang, and D. S. Wong, “Probabilistic public key encryption with equality test,” in Cryptographers’ Track at the RSA Conference, pp. 119–131, Springer, 2010.
  * [27] T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” IEEE transactions on information theory, vol. 31, no. 4, pp. 469–472, 1985.
  * [28] N. Zupan, K. Zhang, and H.-A. Jacobsen, “Hyperpubsub: a decentralized, permissioned, publish/subscribe service using blockchains,” in Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference: Posters and Demos, pp. 15–16, 2017.
  * [29] Hyperledger, “Hyperledger fabric v2.2 documentation.” https://hyperledger-fabric.readthedocs.io/en/release-2.2/, 2020.  Last accessed 2020-10-22.
  * [30] Hyperledger, “Hyperledger fabric v1.4 documentation.” https://hyperledger-fabric.readthedocs.io/en/release-1.4/, 2019.  Last accessed 2020-10-22.
  * [31] E. Androulaki, A. Barger, V. Bortnikov, C. Cachin, K. Christidis, A. De Caro, D. Enyeart, C. Ferris, G. Laventman, Y. Manevich, et al., “Hyperledger fabric: a distributed operating system for permissioned blockchains,” in Proceedings of the thirteenth EuroSys conference, pp. 1–15, 2018.
  * [32] Hyperledger, “Hyperledger besu documentation.” https://besu.hyperledger.org, 2020.  Last accessed 2020-10-22.
  * [33] T. L. Foundation, “Hyperledger Caliper.” https://www.hyperledger.org/use/caliper, 2020.  Last accessed 2020-11-5.
  * [34] C. Fan, S. Ghaemi, H. Khazaei, and P. Musilek, “Performance evaluation of blockchain systems: A systematic survey,” IEEE Access, vol. 8, pp. 126927–126950, 2020.
  * [35] E. Androulaki, A. Barger, V. Bortnikov, C. Cachin, K. Christidis, A. De Caro, D. Enyeart, C. Ferris, G. Laventman, Y. Manevich, S. Muralidharan, C. Murthy, B. Nguyen, M. Sethi, G. Singh, K. Smith, A. Sorniotti, C. Stathakopoulou, M. Vukolić, S. W. Cocco, and J. Yellick, “Hyperledger fabric: A distributed operating system for permissioned blockchains,” in Proceedings of the Thirteenth EuroSys Conference, EuroSys ’18, (New York, NY, USA), Association for Computing Machinery, 2018.
  * [36] S. Rouhani, R. Belchior, R. S. Cruz, and R. Deters, “Distributed Attribute-Based Access Control System Using a Permissioned Blockchain,” arXiv preprint, 2020.
  * [37] R. Belchior, B. Putz, G. Pernul, M. Correia, A. Vasconcelos, and S. Guerreiro, “SSIBAC : Self-Sovereign Identity Based Access Control,” in The 3rd International Workshop on Blockchain Systems and Applications, IEEE, 2020.


# On isomorphism classes of leaf-induced subtrees in topological trees.

Audace A. V. Dossou-Olory  and  Ignatius Boadi  audace a. v. dossou-olory
department of mathematics and applied mathematics
university of johannesburg
p.o. box 524
auckland park
johannesburg 2006
south africa
and département d’hydrologie et de gestion des ressources en eau
centre d’excellence d’afrique pour l’eau et l’assainissement
institut national de l’eau<EMAIL_ADDRESS>ignatius boadi
african institute for mathematical sciences
ghana
summerhill estates
east legon hills
santoe accra
ghana<EMAIL_ADDRESS>
###### Abstract.

A subtree can be induced in a natural way by a subset of leaves of a rooted
tree. We study the number of nonisomorphic such subtrees induced by leaves
(leaf-induced subtrees) of a rooted tree with no vertex of outdegree 1
(topological tree). We show that only stars and binary caterpillars have the
minimum nonisomorphic leaf-induced subtrees among all topological trees with a
given number of leaves. We obtain a closed formula and a recursive formula for
the families of $d$-ary caterpillars and complete $d$-ary trees, respectively.
An asymptotic formula is found for complete $d$-ary trees using polynomial
recurrences. We also show that the complete binary tree of height $h>1$
contains precisely $\lfloor 2(1.24602...)^{2^{h}}\rfloor$ nonisomorphic leaf-
induced subtrees.

###### Key words and phrases:

topological trees, non-isomorphic leaf-induced subtrees, complete $d$-ary
trees, $d$-ary caterpillars, stars, graph theory, enumerative combinatorics,
networks

##  1\. Introduction and preliminary

Analogous to sampling in statistics, subtrees of trees are very useful when
networks are being analyzed. Since networks can be large and also data
structures are usually complex and large, subtrees are needed because they are
usually manageable to analyze than the whole structure. Also, to determine the
reliability of a network when there is vertex or edge failure, one can look at
the number of subtrees of the graph which represents the network. The larger
the number of subtrees of this graph, the more reliable this network is; see,
as examples, [4, 5, 6]. Furthermore, leaf-induced subtrees are applicable in
web analytics, especially in analyzing access patterns of visitors of a
particular website [14]. EvoMiner, an efficient algorithm for frequent subtree
mining (FST) of subtrees of pyhologenetic trees is introduced in [15]. FST is
particularly useful when considering ancestry of current generation which are
naturally the leaves of a rooted tree [16].

When a vertex of a tree is designated as the root, we have a rooted tree. A
topological tree is a rooted tree with no vertex of outdegree one (or degree
two, except possibly the root). They are also referred to as series-reduced or
homeomorphically irreducible trees [20, 21]. By definition, the tree that has
only one vertex is a topological tree. A topological tree with each vertex
having outdegree at most $d$ is a $d$-ary tree. In a strict or full $d$-ary
tree, each vertex has outdegree 0 or $d$. They are applicable mainly in
computer science where they are used in designing and building data
structures. This leads to efficient data organization, easy access and
modification. In [7], $d$-ary trees are used to develop an efficient solution
to the Empirical Cumulative Distribution Function (ECDF) searching problem.
The ECDF searching problem arises in multivariate statistics where given $N$
points in $d$-dimensional space, a point $X=\\{x_{1},x_{2},\ldots,x_{d}\\}$
dominates another point $Y=\\{y_{1},y_{2},\ldots,y_{d}\\}$ if for all
$i\in\\{1,2,\ldots,d\\}$, $x_{i}\geq y_{i}$. The ECDF searching problem
primarily deals with finding the ratio of the number of $Ys$ dominated by a
given $X$, to $N$, the number of data points [11]. Data structures using
$d$-ary trees are designed in [7] which enables efficient ways of conducting
ECDF queries.

A caterpillar is a tree whose internal vertices lie on a single path (called
the backbone) and all leaves are attached directly to the internal vertices.
The caterpillar is found to be an extremal graph when determining the maximum
or minimum of various distance-based graph invariants [9, 10]. For example,
Dadedzi et al. found in [10] that the caterpillar has the greatest distance
spectral radius among trees with a given degree sequence. Caterpillars are
applicable in layouts of communication and electrical networks where the
internal vertices represent major outlets and leaves represent consumers. They
are also widely used in chemical graph theory; see, as example, [2]. They are
applied in modeling interactions and in analysis of benzenoid hydrocarbons.
Caterpillars are sometimes called Gutman trees, since Ivan Gutman introduced
them to chemical graph theory and made extensive use of them in his works;
see, as examples, [1, 3]. They are also sometimes called benzenoid trees [8].
When one of the internal vertices of a caterpillar is designated as the root,
we have a rooted caterpillar.

We mainly focus on two families of topological trees in this work:

  1. (1)

$d$-ary caterpillars: A $d$-ary caterpillar is defined as a strict $d$-ary
tree which is also a rooted caterpillar. A $d$-ary caterpillar is denoted by
$F^{d}_{n}$, where $n$ is the number of leaves. In Figure 1, we show the
ternary caterpillar with $7$ leaves, $F^{3}_{7}$. At each level of a $d$-ary
caterpillar, there are $d-1$ leaves and one internal vertex except at the
highest level, where there are $d$ leaves and one internal vertex. Thus, the
number of leaves of a $d$-ary caterpillar of height h is $1+h(d-1)$.

Figure 1. The ternary caterpillar with $7$ leaves, $F^{3}_{7}$.

  2. (2)

The complete $d$-ary tree of height $h$, denoted by $C^{d}_{h}$ is a strict
$d$-ary tree which has all leaves at distance $h$ from the root, thus all
leaves lie at the same level in the tree. In Figure 2, we show the complete
ternary tree whose height is two, $C_{2}^{3}$. In a complete $d$-ary tree,
there are $d$ vertices at level 1. Each of these vertices are then connected
to $d$ vertices at level 2, yielding $d^{2}$ vertices at level 2. Hence at
level $h$, there are $d^{h}$ vertices. Since all leaves of a complete $d$-ary
tree are at level $h$, the number of leaves of $C^{d}_{h}$ is $d^{h}$. When
$h=0$, we have the one-vertex tree and when $h=1$, we have the star with $d$
leaves.

Figure 2. The complete ternary tree with height 2, $C^{3}_{2}$.

Two graphs are isomorphic if you can label both graphs with the same labels
such that any selected vertex has the same neighbors in both graphs.

By a leaf-induced subtree of a rooted tree, we mean a subtree induced by
selected leaves of a tree. A subtree can be induced in a natural way by a
subset of leaves of a rooted tree. The number of nonisomorphic such leaf-
induced subtrees of a given rooted tree is the main subject of this work. The
subject of leaf-induced subtrees of rooted trees has been well studied [12,
13, 17, 18, 19, 22, 23, 24]. To form a leaf-induced subtree of a given rooted
tree $T$, we consider the power set of the leaves of $T$ excluding the null
set. If $S$ is a member of this set, then the subtree induced by the leaves in
$S$ is obtained by

  1. (1)

extracting the smallest subtree of $T$ containing no leaf other than those in
$S$. To do this, we first locate the vertex which is the most recent common
ancestor of the leaves in $S$. We then select all vertices and edges
connecting the leaves in $S$ to the vertex identified as the most recent
common ancestor [13, 19],

  2. (2)

contracting all vertices of outdegree 1 in the smallest subtree from step 1
[13, 19]. Suppose $g$ is a vertex with outdegree 1 in the subtree obtained
from step 1 and it has neighbors $f$ and $h$, then we have edges $\\{f,g\\}$
and $\\{g,h\\}$; we contract $g$ and create the edge $\\{f,h\\}$. This is done
for all instances of vertices with outdegree 1 to create a leaf-induced
subtree.

A single leaf can be selected and used to create a leaf-induced subtree which
is the one-vertex tree. By definition, any leaf-induced subtree of a rooted
tree is a topological tree.

######  Definition 1.1.

We define $N(T)$ as the number of nonisomorphic leaf-induced subtrees of a
topological tree $T$.

Clearly, there is only one (up to isomorphism) subtree induced by a given
subset of leaves of a topological tree. Hence, the total number of leaf-
induced subtrees of a topological tree with $n$ leaves is just $2^{n}-1$
(excluding the empty set). We consider subtrees induced by leaves of a
topological tree and select only one representative from every isomorphism
class. In Example 1, we construct two isomorphic leaf-induced subtrees of the
tree in Figure 3.

######  Example 1.

Consider the tree labeled 1 in Figure 3. Let
$L=\\{l_{1},l_{3},l_{4},l_{6}\\}$. We first extract the smallest subtree
containing all the vertices and edges lying on the paths connecting the leaves
in $L$ to their most recent common ancestor. Hence we get the leaf-induced
subtree labeled 2 in Figure 3.

Figure 3. A topological tree and a subtree induced by some of its leaves.

##  2\. main results

We present formulas for the number of nonisomorphic leaf-induced subtrees of a
$d$-ary caterpillar and a complete $d$-ary tree. We also give the minimum
number of nonisomorphic leaf-induced subtrees of a topological tree with $n$
leaves together with the characterization of all extremal trees.

All topological trees with up to four leaves are either stars or binary
caterpillars except the trees shown in Figure 4.

Figure 4. Some topological trees with 4 leaves.

There are 4 leaf-induced subtrees of $C^{2}_{2}$ and 5 of each of $Q_{4}$ and
$E^{3}_{4}$. Theorem 2.1 states the minimum number of leaf-induced subtrees
among all topological trees with $n>4$ leaves and also states the
corresponding extremal trees.

######  Theorem 2.1.

Let $n\geq 5$ be an integer. Every $n$-leaf topological tree $T$ has at least
$n$ nonisomorphic leaf-induced subtrees, with equality if and only if $T$ is a
star or a binary caterpillar.

###### Proof.

Consider the star $S_{n}$, with $n$ leaves. Since all leaf-induced subtrees of
$S_{n}$ are themselves stars (see Figure 5), we obtain $n$ nonisomorphic leaf-
induced subtrees for $S_{n}$. Consider the binary caterpillar with $n$ leaves
$f_{n}^{2}$. All leaf-induced subtrees of $F_{n}^{2}$ are also binary
caterpillars. Hence we obtain $n$ nonisomorphic leaf-induced subtrees for
$F^{2}_{n}$ (see Figure 6).

Figure 5. All leaf-induced subtrees of $S_{n}$. Figure 6. All leaf-induced
subtrees of $F^{2}_{n}$.

Finally, we show that a topological tree $T$ with $n\geq 5$ leaves which is
neither a star nor a binary caterpillar has at least $n+1$ nonisomorphic leaf-
induced subtrees. Since $T$ is neither a star, nor a binary caterpillar, its
root should have outdegree at most $n-1$ and at most $n-2$ leaves attached to
it. The key to the proof of this part of the theorem is to show that there
exists at least two nonisomorphic leaf-induced subtrees with $k$ leaves for
some $k\in\\{3,\ldots,n\\}$. We consider two possible cases:

  1. (1)

If $T$ contains a vertex of outdegree at least three, then the leaf-induced
subtrees with three leaves, $S_{3}$ and $F^{2}_{3}$ are both present (see the
trees labeled $3$ in Figures 5 and 6 respectively). Hence we have at least
$n+1$ nonisomorphic leaf-induced subtrees for $T$.

  2. (2)

If $T$ is a binary tree, then it must be of height at least three since it has
at least five leaves. The trees $C_{2}^{2}$ (see Figure 4) and $F_{2}^{2}$
(see the tree labeled 4 in Figure 6) each with four leaves, are leaf-induced
subtrees of $T$. Hence we have at least $n+1$ nonisomorphic leaf-induced
subtrees for $T$.

∎

## 2.1 $d$-ary Caterpillars

######  Theorem 2.2.

Let $d\geq 3$ be a fixed positive integer. For the $d$-ary caterpillar
$F_{n}^{d}$, we have

$N(F^{d}_{n})=\dfrac{(d-1)^{\frac{n+d-2}{d-1}}-1}{d-2}.$

###### Proof.

Since $F_{n}^{d}$ is a strict $d$-ary tree, it has precisely $(n-1)/(d-1)$
internal vertices which is also its height. Consider the internal vertex at
the highest level which has $d$ leaves.

  1. (1)

We can attach from 2 to $d$ leaves to this vertex to get $d-1$ leaf-induced
subtrees. Hence in addition to the one-leaf rooted subtree, we have 1 +
$(d-1)$ leaf-induced subtrees.

  2. (2)

For each of the $d-1$ leaf induced subtrees from step $1$, we move to the next
internal vertex above the vertex considered in step 1 and attach from 1 to
$d-1$ leaves of this vertex to give $(d-1)(d-1)=(d-1)^{2}$ leaf-induced
subtrees resulting in $1+(d-1)+(d-1)^{2}$ leaf-induced subtrees.

  3. (3)

For each of the $(d-1)^{2}$ leaf-induced subtrees from step 2, we move to the
next vertex and attach from 1 to $d-1$ leaves to give
$(d-1)^{2}(d-1)=(d-1)^{3}$ leaf -induced subtrees yielding
$1+(d-1)+(d-1)^{2}+(d-1)^{3}$ leaf-induced subtrees in total.

This process is repeated for the new subtrees formed up the backbone of the
tree until we reach the root. The number of times this operation is done is
equal to the height of the tree. We therefore have

$\displaystyle N(F^{d}_{n})$
$\displaystyle=1+(d-1)+(d-1)^{2}+\cdots+(d-1)^{\frac{n-1}{d-1}}$
$\displaystyle=\dfrac{(d-1)^{\frac{n+d-2}{d-1}}-1}{d-2}.$

∎

## 2.2 Complete $d$-ary Trees

In this section, we develop a recursive formula and an asymptotic formula for
$N(C_{h}^{d})$. Lemma 1 below will be used in deriving the asymptotic formula
for $N(C_{h}^{d})$.

######  Lemma 1.

Let $d\geq 2$ be a fixed integer and $a_{0},a_{1},a_{2},\ldots,a_{d}$ be real
numbers such that $a_{i}\geq 0,$ and $a_{d}\neq 0$. If $(A_{n})_{n\geq 0}$ is
a polynomial sequence defined recursively by

$A_{0}>0,A_{n}=\sum_{k=0}^{d}a_{k}.A_{n-1}^{k},$

then

(1)
$\log(A_{n})=\dfrac{d^{n}-1}{d-1}\log(a_{d})+d^{n}\bigg{(}\log(A_{0})+\sum_{j=0}^{n-1}d^{-1-j}.\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{j}^{k-d}\bigg{)}\bigg{)}$

for every $n\geq 1.$ Moreover, if $(A_{n})_{n\geq 0}$ is an increasing
sequence and $\lim\limits_{n\rightarrow\infty}A_{n}=\infty$, we also obtain

(2)
$\small{A_{n}=(1+o(1))a_{d}^{-\frac{1}{d-1}}\exp\bigg{(}d^{n}\bigg{(}\dfrac{\log(a_{d})}{d-1}+\log(A_{0})+\sum_{j=0}^{\infty}d^{-1-j}\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{n-1}^{k-d}\bigg{)}\bigg{)}\bigg{)}}$

as $n\rightarrow\infty$.

###### Proof.

To prove (1), consider the recursion

$\displaystyle A_{n}$
$\displaystyle=a_{0}+a_{1}A_{n-1}+a_{2}A_{n-1}^{2}+\cdots+a_{d}A_{n-1}^{d},$
$\displaystyle\dfrac{A_{n}}{A^{d}_{n-1}}$
$\displaystyle=a_{d}+\dfrac{a_{d-1}}{A_{n-1}}+\dfrac{a_{d-2}}{A_{n-1}^{2}}+\cdots+\dfrac{a_{0}}{A^{d}_{n-1}},$
$\displaystyle\log\bigg{(}\dfrac{A_{n}}{A_{n-1}^{d}}\bigg{)}$
$\displaystyle=\log\bigg{(}a_{d}\bigg{(}1+\dfrac{a_{d-1}}{a_{d}A_{n-1}}+\dfrac{a_{d-2}}{a_{d}A_{n-1}^{2}}+\cdots+\dfrac{a_{0}}{a_{d}A^{d}_{n-1}}\bigg{)}\bigg{)},$
$\displaystyle\log A_{n}-d\log A_{n-1}$ $\displaystyle=\log
a_{d}+\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{n-1}^{k-d}\bigg{)},$
(3) $\displaystyle\log A_{n}$ $\displaystyle=d\log A_{n-1}+\log
a_{d}+\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{n-1}^{k-d}\bigg{)}.$

From (3), we get

(4) $\displaystyle\log A_{n-1}$ $\displaystyle=d\log A_{n-2}+\log
a_{d}+\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{n-2}^{k-d}\bigg{)}.$

Substituting (4) into (3), we get

$\displaystyle\log A_{n}$ $\displaystyle=d^{2}\log A_{n-2}+(d+1)\log
a_{d}+d\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{n-2}^{k-d}\bigg{)}+\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{n-1}^{k-d}\bigg{)}.$

Clearly, we have

(5) $\log A_{n-j}=d\log A_{n-j-1}+\log
a_{d}+\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{n-j-1}^{k-d}\bigg{)}$

for every $j$ such that $n-j>0.$ Using (5) to find expressions for
$A_{n-j},j=1,2,\ldots,n-1$ and substituting into (3), we get

$\displaystyle\log A_{n}$ $\displaystyle=(d^{n-1}+d^{n-2}+\cdots+d+1)\log
a_{d}+d^{n}\log
A_{0}+d^{n-1}\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{0}^{k-d}\bigg{)}$
$\displaystyle\quad+\cdots+d\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{n-2}^{k-d}\bigg{)}+\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{n-1}^{k-d}\bigg{)}$
(6) $\displaystyle=\dfrac{d^{n}-1}{d-1}\log a_{d}+d^{n}\log
A_{0}+d^{n}\bigg{(}\sum_{j=0}^{n-1}d^{-1-j}\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{j}^{k-d}\bigg{)}\bigg{)}.$

This proves (1). Consider the series

$\displaystyle
d^{n}\sum_{j=n}^{\infty}d^{-1-j}\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{j}^{k-d}\bigg{)}.$

Note that we have $k<d$. Recall that $a_{k}/a_{d}\geq 0$. Since $\sup_{j\geq
n}A_{j}^{k-d}=A_{n}^{k-d}$, we have

$\displaystyle 0\leq
d^{n}\sum_{j=n}^{\infty}d^{-1-j}\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{j}^{k-d}\bigg{)}$
$\displaystyle\leq
d^{n}\sum_{j=n}^{\infty}d^{-1-j}.\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{n}^{k-d}\bigg{)}$
$\displaystyle=\dfrac{1}{d-1}.\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{n}^{k-d}\bigg{)}$

and

$\displaystyle\lim\limits_{n\rightarrow\infty}\bigg{(}\dfrac{1}{d-1}.\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{n}^{k-d}\bigg{)}\bigg{)}$
$\displaystyle=0.$

Hence

$d^{n}\sum_{j=n}^{\infty}d^{-1-j}\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{j}^{k-d}\bigg{)}=o(1).$

Now, let

(7)
$R_{n}(d)=\sum_{j=n}^{\infty}d^{-1-j}\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{j}^{k-d}\bigg{)}.$

We rewrite (6) as

$\displaystyle\log A_{n}$ $\displaystyle=\dfrac{d^{n}-1}{d-1}\log
a_{d}+d^{n}\log
A_{0}+d^{n}\bigg{(}\sum_{j=0}^{n-1}d^{-1-j}\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{j}^{k-d}\bigg{)}+R_{n}(d)-R_{n}(d)\bigg{)}$
$\displaystyle=\dfrac{d^{n}-1}{d-1}\log a_{d}+d^{n}\log
A_{0}+d^{n}\bigg{(}\sum_{j=0}^{\infty}d^{-1-j}\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{j}^{k-d}\bigg{)}-R_{n}(d)\bigg{)},$

which holds for all $n\geq 1$. Let

$K(d)=\sum_{j=0}^{\infty}d^{-1-j}\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{j}^{k-d}\bigg{)}.$

Then we have

$\displaystyle\log A_{n}$
$\displaystyle=d^{n}\bigg{(}\log(A_{0})+\dfrac{\log(a_{d})}{d-1}+K(d)\bigg{)}-\dfrac{\log(a_{d})}{d-1}+o(1),$
$\displaystyle A_{n}$
$\displaystyle=\exp\bigg{(}d^{n}\bigg{(}\log(A_{0})+\dfrac{\log(a_{d})}{d-1}+K(d)\bigg{)}-\dfrac{\log(a_{d})}{d-1}+o(1)\bigg{)}$
$\displaystyle=\exp(o(1)).\exp\bigg{(}\log\bigg{(}a_{d}^{\frac{-1}{d-1}}\bigg{)}\bigg{)}.\exp\bigg{(}d^{n}\bigg{(}\log(A_{0})+\dfrac{\log(a_{d})}{d-1}+K(d)\bigg{)}\bigg{)}.$

Using Taylor series expansion for $\exp(o(1))$, we have

$\displaystyle=(1+o(1))a_{d}^{-\frac{1}{d-1}}\exp\bigg{(}d^{n}\bigg{(}\log(A_{0})+\dfrac{\log(a_{d})}{d-1}+K(d)\bigg{)}\bigg{)}$

as $n\rightarrow\infty$. This completes the proof of the lemma. ∎

######  Theorem 2.3.

The number of nonisomorphic leaf-induced subtrees of the complete $d$-ary
tree, $C_{h}^{d}$ is given by

(8) $N(C_{h}^{d})=-N(C_{h-1}^{d})+\begin{pmatrix}d+N(C_{h-1}^{d})\\\
d\end{pmatrix}$

with $N(C_{0}^{d})=1$. Furthermore,

(9) $N(C_{h}^{d})=(1+o(1))(d!)^{\frac{1}{d-1}}\kappa(d)^{d^{h}}$

for some effectively computable constant $\kappa(d)>1$ as
$h\rightarrow\infty$.

###### Proof.

Fix $h\geq 1$. Call $v$ the root of $C^{d}_{h}$ and $A_{h}$ the set of all
nonisomorphic leaf-induced subtrees of $C_{h}^{d}$ whose root is $v$ and has
root degree $r$ is uniquely determined by a choice of a $r$-element multiset
$A_{h-1}$ (since all $r$ branches lie in $A_{h-1}$). So for every
$r\in\\{2,3,\ldots,d\\}$, there are precisely

$\begin{pmatrix}N(C^{d}_{h-1})+r-1\\\ r\end{pmatrix}$

such subtrees (with root degree $r$). Therefore, taking into consideration the
subtree consisting only of the single leaf, and using the fact that the
elements of $A_{h-1}$ are already counted this way, we get

$N(C_{h}^{d})=1+\sum_{r=2}^{d}\begin{pmatrix}N(C^{d}_{h-1})+r-1\\\
r\end{pmatrix}$

nonisomorphic leaf-induced subtrees. Let $j=N(C^{d}_{h-1})+r-1$. We get

$\displaystyle N(C^{d}_{h})$
$\displaystyle=1+\sum_{j=N(C^{d}_{h-1})+1}^{N(C^{d}_{h-1})+d-1}\begin{pmatrix}j\\\
j+1-N(C^{d}_{h-1})\end{pmatrix}$
$\displaystyle=1+\sum_{j=N(C^{d}_{h-1})+1}^{N(C^{d}_{h-1})+d-1}\begin{pmatrix}j\\\
N(C^{d}_{h-1})-1\end{pmatrix}\quad\text{since $\begin{pmatrix}n\\\
r\end{pmatrix}=\begin{pmatrix}n\\\ n-r\end{pmatrix}$}$
$\displaystyle=-N(C^{d}_{h-1})+N(C^{d}_{h-1})+1+\sum_{j=N(C^{d}_{h-1})+1}^{N(C^{d}_{h-1})+d-1}\begin{pmatrix}j\\\
N(C^{d}_{h-1})-1\end{pmatrix}$
$\displaystyle=-N(C^{d}_{h-1})+\sum_{j=-1+N(C^{d}_{h-1})}^{N(C^{d}_{h-1})+d-1}\begin{pmatrix}j\\\
N(C^{d}_{h-1})-1\end{pmatrix}.$

It can be shown by induction on $d$ that

$\sum_{j=-1+N(C^{d}_{h-1})}^{N(C^{d}_{h-1})+d-1}\begin{pmatrix}j\\\
N(C^{d}_{h-1})-1\end{pmatrix}=\begin{pmatrix}d+N(C_{h-1}^{d})\\\
N(C_{h-1}^{d})\end{pmatrix}.$

Hence we have

$N(C^{d}_{h})=-N(C^{d}_{h-1})+\begin{pmatrix}d+N(C_{h-1}^{d})\\\
N(C_{h-1}^{d})\end{pmatrix}=-N(C^{d}_{h-1})+\begin{pmatrix}d+N(C_{h-1}^{d})\\\
d\end{pmatrix}.$

Observe that $N(C_{h}^{d})$ increases with $h$ since the nonisomorphic leaf-
induced subtrees of $C^{d}_{h}$ include all nonisomorphic leaf-induced
subtrees of $C^{d}_{h-1}$. To prove (9), first set $A_{h}=N(C_{h}^{d})$. We
have

$\displaystyle A_{h}$ $\displaystyle=-A_{h-1}+\begin{pmatrix}d+A_{h-1}\\\
d\end{pmatrix}$ $\displaystyle=-A_{h-1}+\dfrac{(A_{h-1}+d)!}{(A_{h-1}!)(d!)}$
$\displaystyle=-A_{h-1}+\dfrac{(A_{h-1}+d)(A_{h-1}+d-1)(A_{h-1}+d-2)\cdots(A_{h-1}+2)(A_{h-1}+1)}{d!}$
$\displaystyle=-A_{h-1}+\dfrac{A_{h-1}^{d}+\bigg{(}\sum_{i=1}^{d}i\bigg{)}A_{h-1}^{d-1}+\cdots+\bigg{(}\sum_{i=1}^{d}\prod_{j=1,j\neq
i}^{d}j\bigg{)}A_{h-1}+d!}{d!}$
$\displaystyle=\dfrac{-A_{h-1}d!+A_{h-1}^{d}+\bigg{(}\sum_{i=1}^{d}i\bigg{)}A_{h-1}^{d-1}+\cdots+\bigg{(}\sum_{i=2}^{d}\prod_{j=1,j\neq
i}^{d}j\bigg{)}A_{h-1}+d!A_{h-1}+d!}{d!}$
$\displaystyle=\dfrac{A_{h-1}^{d}+\bigg{(}\sum_{i=1}^{d}i\bigg{)}A_{h-1}^{d-1}+\cdots+\bigg{(}\sum_{i=2}^{d}\prod_{j=1,j\neq
i}^{d}j\bigg{)}A_{h-1}+d!}{d!}.$

By setting $a_{i}$ as the coefficients of $A_{h-1}^{i}$,
$i\in\\{0,1,2,3,\ldots,d\\}$, noting that $A_{0}=1$ and $a_{d}=1/d!$ and using
the identity derived in (3), we have

(10) $\displaystyle\log A_{h}$ $\displaystyle=d\log A_{h-1}-\log
d!+\log\bigg{(}1+d!\sum_{k=0}^{d-1}a_{k}A_{h-1}^{k-d}\bigg{)}.$

From Lemma 1, we get

$N(C_{h}^{d})=(1+o(1))(d!)^{\frac{1}{d-1}}\kappa(d)^{d^{h}},$

where

(11) $\displaystyle\kappa(d)$ $\displaystyle=\exp\bigg{(}-\dfrac{\log
d!}{d-1}+K(d)\bigg{)}$

and

(12) $\displaystyle K(d)$
$\displaystyle=\sum_{j=0}^{\infty}d^{-1-j}.\log\bigg{(}1+d!\sum_{k=0}^{d-1}a_{k}(N(C^{d}_{j})^{k-d})\bigg{)}.$

From (10), we get

$\displaystyle\log A_{h+1}$ $\displaystyle=d\log A_{h}-\log
d!+\log\bigg{(}1+d!\sum_{k=0}^{d-1}a_{k}A_{h}^{k-d}\bigg{)},$ (13)
$\displaystyle\log\bigg{(}\dfrac{d!A_{h+1}}{A_{h}^{d}}\bigg{)}$
$\displaystyle=\log\bigg{(}1+d!\sum_{k=0}^{d-1}a_{k}A_{h}^{k-d}\bigg{)}.$

Recall that $A_{h}=N(C_{h}^{d})$. Substituting (13) into (12), we get

(14) $\displaystyle K(d)$
$\displaystyle=\sum_{j=0}^{\infty}d^{-1-j}.\log\bigg{(}d!.\dfrac{N(C^{d}_{j+1})}{N(C^{d}_{j})^{d}}\bigg{)}.$

We have

$-\dfrac{\log d!}{d-1}+K(d)=-\dfrac{\log
d!}{d-1}+\sum_{j=0}^{\infty}d^{-1-j}.\log\bigg{(}d!.\dfrac{N(C^{d}_{j+1})}{N(C^{d}_{j})^{d}}\bigg{)}.$

Since $N(C^{d}_{j+1})>N(C^{d}_{j})^{d}$, we obtain

$\displaystyle-\dfrac{\log d!}{d-1}+K(d)$ $\displaystyle>-\dfrac{\log
d!}{d-1}+\sum_{j=0}^{\infty}d^{-1-j}.\log d!$ $\displaystyle=-\dfrac{\log
d!}{d-1}+\dfrac{\log d!}{d-1}$ $\displaystyle=0.$

Hence $\kappa(d)>1$. ∎

The value of $\kappa(d)$ derived in (11) for every $d$ can be numerically
evaluated. Table 1 gives values of $\kappa(d)$ for $d\in\\{2,3,\ldots,10\\}$.

Table 1. Approximated values of $\kappa(d)$. $d$ | $\kappa(d)$
---|---
2 | 1.246020832983661
3 | 1.254860390384554
4 | 1.2189114976086313
5 | 1.1888457507131132
6 | 1.165394603276801
7 | 1.1469724134908297
8 | 1.1322182196849957
9 | 1.1201639471936817
10 | 1.1101387293827483

From Table 1, when $d=2$, we get

$N(C_{h}^{2})\sim 2(1.246020832983661)^{2^{h}}$

as $h\rightarrow\infty$.

Propositions 2.4 and 2.5 below give further results about $\kappa(d)$.

######  Proposition 2.4.

The sequence $\kappa(d)_{d\geq 2}$ converges to 1 as $d\rightarrow\infty$.

###### Proof.

From equations (11) and (12), we have

(15) $\log(\kappa(d))=-\dfrac{\log d!}{d-1}+\dfrac{\log
d!+\log(d)}{d}+\sum_{j\geq 1}\dfrac{\log
d!+\log(N(C^{d}_{j+1}))-d.\log(N(C^{d}_{j}))}{d^{j+1}}.$

From (8), we can write

$\displaystyle N(C^{d}_{j+1})$
$\displaystyle=-N(C^{d}_{j})+\begin{pmatrix}d+N(C^{d}_{j})\\\
d\end{pmatrix}=\sum_{k=0}^{d}a_{k}.N(C^{d}_{j})^{k}$
$\displaystyle\leq\sum_{k=0}^{d}a_{k}.N(C^{d}_{j})^{d}$ $\displaystyle
N(C^{d}_{j+1})$ $\displaystyle\leq N(C^{d}_{j})^{d}\sum_{k=0}^{d}a_{k}$ (16)
$\displaystyle\dfrac{N(C^{d}_{j+1})}{N(C^{d}_{j})^{d}}$
$\displaystyle\leq\sum_{k=0}^{d}a_{k}=d.$

We make a substitution of (16) into (15). We have

$\displaystyle 0\leq\log(\kappa(d))$ $\displaystyle\leq-\dfrac{\log
d!}{d-1}+\dfrac{\log d!+\log(d)}{d}+\sum_{j\geq 1}\dfrac{\log
d!+\log(d)}{d^{j+1}}$ $\displaystyle=-\dfrac{\log d!}{d-1}+\dfrac{\log
d!+\log(d)}{d}+(\log d!+\log(d))\sum_{j\geq 1}\dfrac{1}{d^{j+1}}$
$\displaystyle=-\dfrac{\log d!}{d-1}+\dfrac{\log d!+\log(d)}{d}+\dfrac{\log
d!+\log(d)}{d(d-1)}$ $\displaystyle=\dfrac{\log d}{d-1}$

It is clear that

$\lim\limits_{d\rightarrow\infty}\dfrac{\log d}{d-1}=0.$

Hence $\kappa(d)\rightarrow 1$ as $d\rightarrow\infty$. ∎

######  Proposition 2.5.

Given $d\geq 2$, there exists a positive integer $H\geq 2$ such that

$N(C^{d}_{h})=\big{\lfloor}d!^{\frac{1}{d-1}}\kappa(d)^{d^{h}}\big{\rfloor}$

for every $h\geq H$.

###### Proof.

From (7), we can show that the relation

$0<R_{n}(d)\leq\dfrac{d^{-n}}{d-1}.\log\bigg{(}1+\sum_{k=0}^{d-1}\dfrac{a_{k}}{a_{d}}.A_{n}^{k-d}\bigg{)}$

holds for every $d\geq 2$ and every $n\geq 1$. We deduce the double inequality

(17) $\displaystyle
d^{n}\bigg{(}\sum_{j=0}^{\infty}d^{-1-j}.\log\bigg{(}1+d!\sum_{k=0}^{d-1}a_{k}.A_{j}^{k-d}\bigg{)}-\dfrac{d^{-n}}{d-1}.d!\sum^{d-1}_{k=0}a_{k}.A_{n}^{k-d}\bigg{)}-\dfrac{d^{n}-1}{d-1}\log
d!$ $\displaystyle\leq\log(A_{n})\leq
d^{n}\bigg{(}\sum_{j=0}^{\infty}d^{-1-j}.\log\bigg{(}1+d!\sum_{k=0}^{d-1}a_{k}.A_{j}^{k-d}\bigg{)}\bigg{)}-\dfrac{d^{n}-1}{d-1}\log
d!$

From (17), we obtain

(18) $\displaystyle
d^{n}\bigg{(}\sum_{j=0}^{\infty}d^{-1-j}.\log\bigg{(}1+d!\sum_{k=0}^{d-1}a_{k}.A_{j}^{k-d}\bigg{)}\bigg{)}-\dfrac{d!}{d-1}A_{n}^{-1}\sum^{d-1}_{k=0}a_{k}-\dfrac{d^{n}}{d-1}\log
d!$ $\displaystyle+\dfrac{1}{d-1}\log d!\leq\log(A_{n})\leq
d^{n}\bigg{(}\sum_{j=0}^{\infty}d^{-1-j}.\log\bigg{(}1+d!\sum_{k=0}^{d-1}a_{k}.A_{j}^{k-d}\bigg{)}\bigg{)}-\dfrac{d^{n}}{d-1}\log
d!+\dfrac{1}{d-1}\log d!$

Given that $\sum^{d-1}_{k=0}a_{k}=\dfrac{dd!-1}{d!}$ and substituting (14)
into (18), we obtain

$\displaystyle d^{n}\bigg{(}-\dfrac{\log
d!}{d-1}+K(d)\bigg{)}-\dfrac{d!}{d-1}.A_{n}^{-1}.\dfrac{dd!-1}{d!}+\log
d!^{\frac{1}{d-1}}$ $\displaystyle\leq\log(A_{n})\leq
d^{n}\bigg{(}-\dfrac{\log d!}{d-1}+K(d)\bigg{)}+\log d!^{\frac{1}{d-1}}$
$\displaystyle
d!^{\frac{1}{d-1}}\kappa(d)^{d^{n}}.\exp\bigg{(}-\dfrac{d!}{d-1}.A_{n}^{-1}.\dfrac{dd!-1}{d!}\bigg{)}\leq
A_{n}\leq d!^{\frac{1}{d-1}}\kappa(d)^{d^{n}}$

Replacing $A_{n}$ with $N(C_{h}^{d})$ and using the basic inequality
$e^{t}\geq 1+t$, we obtain

(19)
$d!^{\frac{1}{d-1}}\kappa(d)^{d^{h}}-\dfrac{d!^{\frac{d}{d-1}}}{d-1}.\dfrac{\kappa(d)^{d^{h}}}{N(C^{d}_{h})}\bigg{(}d-\dfrac{1}{d!}\bigg{)}\leq
N(C^{d}_{h})\leq d!^{\frac{1}{d-1}}\kappa(d)^{d^{h}}$

We substitute $N(C_{h}^{d})$ in the left-hand side of (19) with

$d!^{\frac{1}{d-1}}\kappa(d)^{d^{h}}-\dfrac{d!^{\frac{d}{d-1}}}{d-1}.\dfrac{\kappa(d)^{d^{h}}}{N(C^{d}_{h})}\bigg{(}d-\dfrac{1}{d!}\bigg{)}.$

Iterating this substitution process a (finite) number of times leads to

$d!^{\frac{1}{d-1}}\kappa(d)^{d^{h}}-\delta(d)\leq N(C^{d}_{h})\leq
d!^{\frac{1}{d-1}}\kappa(d)^{d^{h}}$

for some constant $0<\delta(d)<1.$ An immediate consequence of this double
inequality is that

$N(C^{d}_{h})=\big{\lfloor}d!^{\frac{1}{d-1}}\kappa(d)^{d^{h}}\big{\rfloor}$

holds for all $h\geq H$ for certain $H$. ∎

For $d=2$, the previous condition $A_{h}>(dd!-1)(d-1)$ becomes $A_{h}>3$,
which means that $N(C^{2}_{h})\geq 4$, hence $H=2$. We deduce that

$N(C^{2}_{h})=\lfloor
2(1.2460208329836625089431529441999359284665241772983812581\ldots)^{2^{h}}\rfloor$

for every $h\geq 2$.

## References

  * [1] Ivan Gutman and Edward C Kirby.  Benzenoids with branching graphs that are trees.  _Croatica Chemica Acta_ , 73(4):943–955, 2000.
  * [2] Stephan Wagner and Hua Wang.  Introduction to chemical graph theory.  CRC Press, 2018.
  * [3] Ivan Gutman and Sven J. Cyvin.  Introduction to the theory of benzenoid hydrocarbons.  Springer Science & Business Media, 2012.
  * [4] Yuzhi Xiao, Haixing Zhao, Zhen Liu and Yaping Mao.  Trees with large numbers of subtrees.  International Journal of Computer Mathematics, 94(2):372–385, 2017.
  * [5] Laszlo A. Székely and Hua Wang.  Binary trees with the largest number of subtrees.  Discrete applied mathematics, 155(3): 374–385, 2007.
  * [6] Laszlo A. Székely and Hua Wang.  On subtrees of trees.  Advances in Applied Mathematics, 34(1): 138–155, 2005.
  * [7] Maurizio Talamo and Giorgio Gambosi.  An application of m-ary trees to the design of data structures for geometric searching problems.  RAIRO-Theoretical Informatics and Applications, 23(2):165–176, 1989.
  * [8] Sherif El-Basil.  Applications of caterpillar trees in chemistry and physics.  Journal of Mathematical Chemistry, 1(2):153–174, 1987.
  * [9] Nina S. Haug, Stephan Wagner and Hua Wang.  Greedy trees, caterpillars, and Wiener-type graph invariants.  MATCH Communications in Mathematical and Computer Chemistry, 68(1):273–292, 2012.
  * [10] Kenneth Dadedzi, Valisoa R. Misanantenaina and Stephan Wagner.  On the distance spectral radius of trees with given degree sequence.  Discussiones Mathematicae Graph Theory, 40(2):295–524, 2020.
  * [11] Jon L. Bentley and Michael I. Shamos.  A problem in multivariate statistics: Algorithm, data structure and applications.  Carnegie-Mellon Univ Pittsburg PA Dept of Computer Science, 1978.
  * [12] Audace A. V. Dossou-Olory.  Leaf-induced subtrees of leaf-Fibonacci trees.  Discrete Mathematics Letter, 1: 1–7. 2019.
  * [13] Éva Czabarka, Audace A. V. Dossou-Olory and Laszlo A. Székely.  Inducibility of $d$-ary trees.  Discrete Mathematics, 343(2): 111671, 2020.
  * [14] Alexandre Blondin Massé et al.  Fully leafed induced subtrees.  In International Workshop on Combinatorial Algorithms, 90-101, 2018.
  * [15] Akshay Deepak et al.  EvoMiner: frequent subtree mining in phylogenetic databases.  Knowledge and Information Systems, 41(3): 559–590, 2014.
  * [16] Xin-Hui Zou et al.  Analysis of 142 genes resolves the rapid diversification of the rice genus.  Genome biology, 9(3): 1-13, 2008.
  * [17] Audace A. V. Dossou-Olory and Stephan Wagner.  On the inducibility of small trees.  Discrete Mathematical and Theoretical Computer Science, 21(4): 5804, 2019.
  * [18] Audace A. V. Dossou-Olory.  The minimum asymptotic density of binary caterpillars.  Graphs and Combinatorics, 35(1):303–320, 2019.
  * [19] Éva Czabarka, Laszlo A. Székely and Stephan Wagner.  Inducibility in binary trees and crossings in random tanglegrams.  SIAM Journal on Discrete Mathematics, 31(3): 1732-1750, 2017.
  * [20] Francois Bergeron, Gilbert Labelle and Pierre Leroux.  Combinatorial species and tree-like structures.  Cambridge University Press, No. 67, 1998.
  * [21] Elizabeth S. Allman and John A. Rhodes.  Mathematical models in biology: an introduction.  Cambridge University Press, 2004.
  * [22] Audace A. V. Dossou-Olory and Stephan Wagner.  Inducibility of topological trees.  Quaestiones Mathematicae 42, no. 6 (2019): 749-764.
  * [23] Audace A. V. Dossou-Olory and Stephan Wagner.  Further results on the inducibility of $d$-ary trees.  Australas J. Comb. 81: 1-4 2021.
  * [24] Audace A. V. Dossou-Olory.  On the inducibility of rooted trees.  PhD dissertation, Stellenbosch: Stellenbosch University, 2018.