# Free boson realization of the Dunkl intertwining operator in one dimension

Luc Vinet$1,2$*** E-mail<EMAIL_ADDRESS>, Alexei Zhedanov$3$†††
E-mail<EMAIL_ADDRESS>
$1$ Centre de Recherches Mathématiques, Université de Montréal,
P.O. Box 6128, Centre-ville Station, Montréal (Québec),
$2$ Institut de valorisation des données (IVADO),
Montréal (Québec), H2S 3H1, Canada H3C 3J7, Canada.
$3$ School of Mathematics, Renmin University of China, Beijing, 100872, China

###### Abstract

The operator that intertwines between the $\mathbb{Z}_{2}$ \- Dunkl operator
and the derivative is shown to have a realization in terms of the oscillator
operators in one dimension. This observation rests on the fact that the Dunkl
intertwining operator maps the Hermite polynomials on the generalized Hermite
polynomials.

Dedicated to the memory of Jiři Patera

##  1 Introduction

Dunkl operators [1] are differential-difference operators associated to
reflection groups. One of their key features is that they form a commutative
set. These operators are proving of high importance in many areas and in
particular in the study of orthogonal polynomials [2] and of quantum many-body
systems of the Calogero-Sutherland type (see for example [3]). Reviews of
Dunkl theory can be found in [4], [5], [6], [7]. In its simplest expression in
one dimension, where the reflection group is $\mathbb{Z}_{2}$, the Dunkl
operator $D_{\mu}$ provides a one-parameter deformation of the ordinary
derivative $\frac{d}{dx}$:

$D_{\mu}=\frac{d}{dx}+\frac{\mu}{x}(1-R),\quad\mu\in\mathbb{R},$ (1.1)

with $R$ the reflection operator: $Rf(x)=f(-x)$.

A key element in this framework is the Dunkl intertwining operator $V_{\mu}$
which as it name indicates intertwines between the Dunkl derivative and the
ordinary one:

$D_{\mu}V_{\mu}=V_{\mu}\frac{d}{dx}.$ (1.2)

This operator $V_{\mu}$ has been introduced in [8]. In the $\mathbb{Z}_{2}$
case that we shall be considering in this note, it is readily checked that
$V_{\mu}$ can be defined by the following action in the monomial basis:

$V_{\mu}\big{(}x^{2n+\epsilon}\big{)}=\frac{\big{(}\frac{1}{2}\big{)}_{n+\epsilon}}{(\mu+\frac{1}{2})_{n+\epsilon}}\;x^{2n+\epsilon},\qquad
n=0,\dots,\quad\epsilon=0,1,$ (1.3)

with $(a)_{n}=\frac{\Gamma(a+n)}{\Gamma[n]}$ the standard Pochhammer symbol.
With the help of beta integrals, it is shown [8] (see also the reviews [5],
[7]) that this amounts to the following representation:

$V_{\mu}f(x)=2^{-2\mu}\frac{\Gamma(2\mu+1)}{\Gamma(\mu)\Gamma(\mu+1)}\int_{-1}^{1}f(xt)(1-t)^{\mu-1}(1+t)^{\mu}dt.$
(1.4)

In the general theory, the intertwining operators are of significant interest
in particular because they provide through the Dunkl kernel the simultaneous
eigenfunctions of the commuting Dunkl operators. This motivates the
challenging search for explicit expressions that extend (1.4) to other
reflection groups. Dunkl himself has obtained formulas for the reflection
groups $A_{2}$ [9] and $B_{2}$ [10] and this remains a topic of intensive
investigations; see for examples the recent reports [11], [12], [13] and the
background references therein for an overview of the state of the art.

The free field formalism makes use of bosonic or fermionic operators that obey
Wick’s rule to construct representations for algebras arising in various
models. This typically proves fundamentally instructive and generally quite
practical from the computational viewpoint. The literature on this is vast, to
pick a reference we might cite a paper [14] co-authored by one of us that
provides a models of the q-hypergeometric functions in this picture.

The purpose of the present note is to offer a free field realization of the
Dunkl intertwiner operator $V_{\mu}$ in one dimension using observations made
by Odake in [15] on the connection between the wave functions of the harmonic
and singular oscillators. The analysis is rooted in the fact that the Hermite
polynomials are mapped [8], [16], [17] onto the generalized Hermite
polynomials [18], [19], [20] by the intertwining operator $V_{\mu}$.

The paper is organized as follows. The generalized Hermite polynomials are
introduced next through the eigenfunctions of the Dunkl oscillator. The key
finding is provided in Section 3 where the action of the intertwiner $V_{\mu}$
in the standard Hermite polynomial basis is explicitly obtained. This is then
translated in terms of the oscillator annihilation operator in Section 4 to
obtain the desired free boson realization of $V_{\mu}$. Remarks on possible
generalizations are offered in guise of conclusion.

##  2 The Dunkl oscillator and the generalized Hermite polynomials

The one-dimensional Dunkl oscillator is governed by the Hamiltonian [21]

$H_{\mu}=\frac{1}{2}\big{(}-D_{\mu}^{2}+x^{2}\big{)}=\frac{1}{2}\Big{[}-\frac{d^{2}}{dx^{2}}-\frac{2\mu}{x}\;\frac{d}{dx}+\frac{\mu}{x^{2}}(1-R)+x^{2}\Big{]}.$
(2.1)

Its eigenfunctions $\psi^{(\mu)}_{2n+\epsilon}(x)$ with eigenvalues
$E=2n+\epsilon+\mu+\frac{1}{2}$ are given by

$\psi^{(\mu)}_{2n+\epsilon}(x)=\kappa_{n}e^{-\frac{1}{2}x^{2}}H_{2n+\epsilon}^{\mu}(x),\quad
n=0,1,\dots$ (2.2)

with $\kappa_{n}$ a normalization constant. The functions
$H_{2n+\epsilon}^{\mu}(x)$ are the generalized Hermite polynomials which can
be defined in terms of the Laguerre polynomials [22]:

$L_{n}^{\alpha}(x)=\frac{(\alpha+1)_{n}}{n!}{{}_{1}}F_{1}\left({-n\atop\alpha+1};x\right)=\frac{(\alpha+1)_{n}}{n!}\>\sum_{k=0}^{n}\frac{(-n)_{k}}{(\alpha+1)_{k}}\frac{x^{k}}{k!};$
(2.3)

they read [16], [20]

$H_{2n+\epsilon}^{\mu}(x)=\frac{(-1)^{n}(2n+\epsilon)!}{(\mu+\frac{1}{2})_{n+\epsilon}}x^{\epsilon}L_{m}^{\mu-\frac{1}{2}+\epsilon}(x^{2}).$
(2.4)

When $\mu=0$, the Dunkl oscillator manifestly reduces to the ordinary harmonic
oscillator whose Hamiltonian as is well known can be written in the form
$H_{\mu=0}\equiv N+\frac{1}{2}$ = with $N$ and the annihilation and creation
operators given by

$N=a^{\dagger}a,\qquad a=\frac{1}{\sqrt{2}}(x+\frac{d}{dx}),\qquad
a^{\dagger}=\frac{1}{\sqrt{2}}(x-\frac{d}{dx}).$ (2.5)

Moreover the generalized Hermite polynomials reduce to the ordinary Hermite
polynomials $H_{n}(x)$. From (2.4) and the explicit expression of the Laguerre
polynomials, one readily obtains the following formula that will prove useful
for the Hermite polynomials:

$H_{2n+\epsilon}(x)=\sum_{k=0}^{n}C_{nk}^{(\epsilon)}x^{2k+\epsilon},\qquad
n=0,1,\dots$ (2.6)

with the coefficients $C_{nk}^{(\epsilon)}$ given by

$C_{nk}^{(\epsilon)}=\frac{(-1)^{n-k}\;2^{2k+\epsilon}\;(2n+\epsilon)!}{(2k+\epsilon)!\;(n-k)!}.$
(2.7)

The Hermite polynomials are well known to possess the Appell property

$\frac{d}{dx}H_{n}(x)=2nH_{n-1}(x)$ (2.8)

which is readily derived from the explicit expression given in (2.6), (2.7).
They also satisfy [22] the eigenvalue equation

$\hat{N}H_{n}(x)=\frac{1}{2}\big{(}-\frac{d^{2}}{dx^{2}}+2x\big{)}H_{n}(x)=nH_{n}(x).$
(2.9)

Note that $\frac{d}{dx}$ and $\hat{N}$ are related to the standard bosonic
operators by a simple conjugation:

$\hat{a}=\frac{1}{\sqrt{2}}\dfrac{d}{dx}=e^{\frac{1}{2}x^{2}}ae^{-\frac{1}{2}x^{2}}\qquad\hat{N}=e^{\frac{1}{2}x^{2}}a^{\dagger}ae^{-\frac{1}{2}x^{2}}.$
(2.10)

##  3 The Dunkl intertwiner and the Hermite polynomials

As an essential step towards bosonizing the Dunkl intertwiner, we shall obtain
its action in the basis of the Hermite polynomials. This will in fact provide
an expansion of the generalized Hermite polynomials $H^{\mu}_{n}(x)$ in terms
of the ordinary ones with $\mu=0$. The strategy is simple: apply the
definition (1.3) of $V_{\mu}$ to (2.6) and use the inversion of this last
formula to revert to Hermite polynomials. To that end, let us start with the
following:

###### Lemma 3.1

The relation

$\sum^{m}_{n=0}\frac{(-m)_{n}(-n)_{k}}{n!}=m!\;\delta_{m,k}$ (3.1)

holds for $m$ and $k$ non-negative integers.

Proof. First note that the sum effectively starts at $n=k$. Observe then that

$\sum_{n=k}^{m}\frac{(-m)_{n}(-n)_{k}}{n!}=(-1)^{k}(-m)_{k}\sum_{k=0}^{m-k}(-1)^{k}{m-k\choose
k}=(-1)^{k}(-m)_{k}(1-1)^{m-k},$ (3.2)

from where we see that

$\sum_{n=k}^{m}\frac{(-m)_{n}(-n)_{k}}{n!}=(-1)^{m}(-m)_{m}\;\delta_{m,k}$
(3.3)

and therefore that the lemma is true. A first application provides the
inversion of formula (2.6), namely the expansion of monomials in terms of
Hermite polynomials [23], [24]. It is given by

$x^{2k+\epsilon}=\sum_{l=0}^{k}D_{k\ell}^{(\epsilon)}H_{2\ell+\epsilon},\qquad
k=0,1,\dots$ (3.4)

with the the coefficients $D_{k\ell}^{(\epsilon)}$ reading

$D_{k\ell}^{(\epsilon)}=\frac{(2k+\epsilon)!}{2^{2k+\epsilon}(2\ell+\epsilon)!(k-\ell)!}.$
(3.5)

This can be confirmed by showing that the matrix $D$ with entries given in
(3.5) is the inverse of the matrix $C$ made out of the coefficients provided
by (2.7). Indeed using

$(n-k)!=\frac{n!}{(-1)^{k}(-n)_{k}},$ (3.6)

it is readily checked that

$\displaystyle\sum_{k=0}^{n}C_{nk}D_{k\ell}$
$\displaystyle=\sum_{k=0}^{n}(-1)^{n-k}\frac{(2n)!}{(2\ell)!}\frac{1}{(n-k)!(k-\ell)!}$
(3.7)
$\displaystyle=(-1)^{n-\ell}\frac{(2n)!}{(2\ell)!}\frac{1}{n!}\sum_{k=0}^{n}\frac{(-n)_{k}(-k)_{l}}{k!}=\delta_{n,\ell},$
(3.8)

calling upon Lemma 3.1 at the last step.

In preparation for the computation of $V_{\mu}H_{2n+\epsilon}(x)$, let us
record a few useful formulas.

###### Lemma 3.2

The equation

$\frac{(\frac{1}{2})_{k+\epsilon}}{(\mu+\frac{1}{2})_{k+\epsilon}}=\frac{(\frac{1}{2})_{n+\epsilon}}{(\mu+\frac{1}{2})_{n+\epsilon}}\sum_{s=0}^{n-k}\frac{1}{s!}(\mu)_{s}\frac{(-n+k)_{s}}{(-n-\epsilon+\frac{1}{2})_{s}}$
(3.9)

is an identity for $k$ and $n$ integers such that $k\leq n$.

Proof. Note that

$\sum_{s=0}^{n-k}\frac{1}{s!}(\mu)_{s}\frac{(-n+k)_{s}}{(-n-\epsilon+\frac{1}{2})_{s}}={{}_{2}}F_{1}\left({-n+k,\>\mu\atop-n-\epsilon+\frac{1}{2}}\;;1\right)=\frac{(-n-\epsilon+\frac{1}{2}-\mu)_{n-k}}{(-n-\epsilon+\frac{1}{2})_{n-k}}$
(3.10)

using Gauss’ summation formula [25]. Now from the following properties of the
Pochhammer symbols:

$\displaystyle(a)_{n-k}$ $\displaystyle=\frac{(-1)^{k}(a)_{n}}{(1-n-a)_{k}},$
(3.11) $\displaystyle(-n+\frac{1}{2}-a)_{n}$
$\displaystyle=(-1)^{n}(a+\frac{1}{2})_{n},$ (3.12)
$\displaystyle\frac{(a+\epsilon)_{k}}{(a+\epsilon)_{n}}$
$\displaystyle=\frac{(a)_{k+\epsilon}}{(a)_{n+\epsilon}},$ (3.13)

we immediately have that

$\frac{(-n-\epsilon+\frac{1}{2}-\mu)_{n-k}}{(-n-\epsilon+\frac{1}{2})_{n-k}}=\frac{(\mu+\frac{1}{2})_{n+\epsilon}}{(\mu+\frac{1}{2})_{k+\epsilon}}\cdot\frac{(\frac{1}{2})_{k+\epsilon}}{(\frac{1}{2})_{n+\epsilon}},$
(3.14)

which in view of (3.10) yields (3.9). We shall also need:

###### Lemma 3.3

The formula

$(2n-2\ell+\epsilon)!\;(-n-\epsilon+\frac{1}{2})_{\ell}=\frac{(-1)^{\ell}\;(2n+\epsilon)!\;(n-\ell)!}{2^{2\ell}n!}$
(3.15)

is valid for $\ell\leq n$ and $\epsilon=0,1$.

Proof. Start with

$(2n-2\ell+\epsilon)!=\frac{(2n+\epsilon)!}{(-2n-\epsilon)_{\ell}}.$ (3.16)

Observe then that

$(-2n-\epsilon)_{2\ell}=2^{2\ell}\;(-n)_{\ell}\;(-n-\epsilon+\frac{1}{2})_{\ell}$
(3.17)

by verifying for instance the relation for $\epsilon=0$ and $\epsilon=1$.
Combining with (3.16) leads to (3.15) bearing in mind (3.6). We are now ready
to present the central result.

###### Theorem 3.1

The action of the Dunkl intertwining operator $V_{\mu}$ in the basis of the
Hermite polynomials $H_{n}(x)$ is given by

$V_{\mu}H_{2n+\epsilon}(x)=\frac{(\frac{1}{2})_{n+\epsilon}}{(\mu+\frac{1}{2})_{n+\epsilon}}\,\sum_{\ell=0}^{n}(-1)^{\ell}\,2^{2\ell}\,{n\choose\ell}\,(\mu)_{\ell}\,H_{2(n-\ell)+\epsilon}(x).$
(3.18)

Proof. From (2.6), (1.3) and (3.4) we have

$V_{\mu}H_{2n+\epsilon}(x)=\sum_{k=0}^{n}\frac{(\frac{1}{2})_{k+\epsilon}}{(\mu+\frac{1}{2})_{k+\epsilon}}\sum_{\ell=0}^{k}C_{nk}^{(\epsilon)}\,D_{k\ell}^{(\epsilon)}\,H_{2\ell+\epsilon}(x).$
(3.19)

Exchanging the sums and using the expressions for $C_{nk}^{(\epsilon)}$ and
$D_{l\ell}^{(\epsilon)}$ given by (2.7) and (3.5) respectively, one finds
after some simplifications that

$V_{\mu}H_{2n+\epsilon}(x)=\sum_{\ell=0}^{n}\frac{1}{(2\ell+\epsilon)!}\,H_{2\ell+\epsilon}(x)\,\sum_{k=\ell}^{n}\frac{(\frac{1}{2})_{k+\epsilon}}{(\mu+\frac{1}{2})_{k+\epsilon}}\,\frac{(-1)^{n-k}(2n+\epsilon)!}{(n-k)!\,(k-\ell)!}.$
(3.20)

At this point we call upon Lemma 3.2 to write

$\displaystyle V_{\mu}H_{2n+\epsilon}(x)$
$\displaystyle=(-1)^{n}\frac{(\frac{1}{2})_{n+\epsilon}}{(\mu+\frac{1}{2})_{n+\epsilon}}\,(2n+\epsilon)!\sum_{\ell=0}^{n}\frac{1}{(2\ell+\epsilon)!}\,H_{2\ell+\epsilon}(x)$
$\displaystyle\cdot\sum_{k=\ell}^{n}\frac{(-1)^{k}}{(n-k)!\,(k-\ell)!}\,\sum_{s=0}^{n-k}\frac{1}{s!}(\mu)_{s}\frac{(-n+k)_{s}}{(-n-\epsilon+\frac{1}{2})_{s}}.$
(3.21)

The second sum can be made to start at $k=0$ since all the terms with
$k\leq\ell$ vanish. One then exchanges the sums over $k$ and $s$ to have

$\displaystyle V_{\mu}H_{2n+\epsilon}(x)$
$\displaystyle=\frac{(-1)^{n}}{n!}\,\frac{(\frac{1}{2})_{n+\epsilon}}{(\mu+\frac{1}{2})_{n+\epsilon}}\,(2n+\epsilon)!\sum_{\ell=0}^{n}\frac{(-1)^{\ell}}{(2\ell+\epsilon)!}\,H_{2\ell+\epsilon}(x)$
$\displaystyle\cdot\sum_{s=0}^{n}\frac{1}{s!}\,\frac{(\mu)_{s}}{(-n-\epsilon+\frac{1}{2})_{s}}\cdot\sum_{k=0}^{n-s}\frac{1}{k!}\,(-n)_{k}\,(-k)_{\ell}\,(-n+k)_{s}$
(3.22)

with the help of (3.6). This is where we use again Lemma 3.1 to find for the
last sum:

$\sum_{k=0}^{n-s}\frac{1}{k!}\,(-n)_{k}\,(-k)_{\ell}\,(-n+k)_{s}=(-n)_{s}\sum_{k=0}^{n-s}\frac{(-k)_{\ell}\,(-n+s)_{k}}{k!}=(-n)_{s}\,(n-s)!\,\delta_{n-s,\ell}.$
(3.23)

Inserting (3.23) in (3.22) yields:

$\displaystyle V_{\mu}H_{2n+\epsilon}(x)$ $\displaystyle=$
$\displaystyle\frac{(-1)^{n}}{n!}\,\frac{(\frac{1}{2})_{n+\epsilon}}{(\mu+\frac{1}{2})_{n+\epsilon}}\,(2n+\epsilon)!\sum_{\ell=0}^{n}\frac{(-1)^{\ell}}{(2\ell+\epsilon)!}\,\frac{(\mu)_{n-\ell}}{(n-\ell)!}\,\frac{(-n)_{n-\ell}\;\ell!}{(n-\epsilon+\frac{1}{2})_{n-\ell}}H_{2\ell+\epsilon}(x).$
(3.24)

Now effect the change of summation index $\ell\rightarrow n-\ell$ to obtain:

$V_{\mu}H_{2n+\epsilon}(x)=\frac{(\frac{1}{2})_{n+\epsilon}}{(\mu+\frac{1}{2})_{n+\epsilon}}\,(2n+\epsilon)!\,\sum_{\ell=0}^{n}\frac{(\mu)_{\ell}}{\ell!}\,\frac{1}{(2n-2\ell+\epsilon)!\,(-n-\epsilon+\frac{1}{2})_{\ell}}H_{2(n-\ell)+\epsilon}(x),$
(3.25)

where $(-1)^{\ell}(-n)_{\ell}(n-\ell)!$ has cancelled $n!$ as is familiar from
(3.6). This is where Lemma 3.3 now comes in handy and allows to rewrite the
denominator under the sum and to find the result (3.18) of Theorem 3.1 after
the cancellation of the factor $(2n+\epsilon)!$.

###### Corollary 3.1

Equation (3.18) provides the connection formula between the generalized
Hermite polynomials and the standard Hermite polynomials.

Proof. Following Dunkl [8], it is easy to check that

$H_{2n+\epsilon}^{\mu}(x)=V_{\mu}H_{2n+\epsilon}(x),$ (3.26)

from where the statement is established. Indeed, from (1.3), (2.3) and (2.4),
we see for instance when $\epsilon=1$ that

$\displaystyle V_{\mu}H_{2n+1}(x)=$
$\displaystyle(-1)^{n}\frac{(2n+1)!}{(\frac{1}{2})_{n+1}}\,\frac{(\frac{3}{2})_{n}}{n!}\,\sum_{k=0}^{n}\frac{(-n)_{k}}{(\frac{3}{2})_{k}}\,\frac{V_{\mu}(x^{2k+1})}{k!}$
$\displaystyle=$
$\displaystyle(-1)^{n}\frac{(2n+1)!}{(\frac{1}{2})}\,\frac{1}{n!}\,\sum_{k=0}^{n}\frac{(-n)_{k}}{(\frac{3}{2})_{k}}\,\frac{(\frac{1}{2})_{k+1}}{k!\,(\mu+\frac{1}{2})_{k+1}}\,x^{2k+1}$
$\displaystyle=$
$\displaystyle(-1)^{n}\frac{(2n+1)!}{(\mu+\frac{1}{2})\,n!}\,x\,\sum_{k=0}^{n}\frac{(-n)_{k}}{k!}\,\frac{1}{(\mu+\frac{3}{2})_{k}}\,x^{2k}$
$\displaystyle=$
$\displaystyle(-1)^{n}\,\frac{(2n+1)!}{(\mu+\frac{1}{2})_{n+1}}\,x\,L_{n}^{(\mu+\frac{1}{2})}(x^{2})\,=\,H_{2n+1}^{\mu}(x),$
(3.27)

and the computation is even more straigtforward for $\epsilon=0$.

##  4 The boson operator realization

Borrowing ideas presented in [15], we offer in this section a realization of
the Dunkl intertwining operator $V_{\mu}$ in terms of bosonic operators. This
follows from Theorem 3.1 which gives the action of $V_{\mu}$ on the Hermite
polynomials that provide a well known representation basis for the oscillator
operators. Recall the actions (2.8), (2.9) on $H_{n}(x)$ of the bosonic
operators $\hat{a}$ and $\hat{N}$ defined in (2.10). We shall also make use of
the projector

$P=\frac{1}{2}(I-R),\qquad P^{2}=P$ (4.1)

with $R$ the reflection operator that appears in the Dunkl derivative. Owing
to the fact that the Hermite polynomials are symmetric, we have

$P\,H_{2n+\epsilon}(x)=\epsilon\,H_{2n+\epsilon}.$ (4.2)

Consider now the operator

$\hat{b}=(\hat{N}+P+1)^{-1}\,\hat{a}^{2}$ (4.3)

which clearly will lower degrees by two. It is checked that for
$\epsilon=0,1$:

$\displaystyle\hat{b}\,H_{2n+\epsilon}(x)$
$\displaystyle=\frac{2(2n+\epsilon)(2n+\epsilon-1)}{(2n+2\epsilon-1)}\,H_{2n+\epsilon-2}$
$\displaystyle=2^{2}\,n\,H_{2n+\epsilon-2}.$ (4.4)

Note that $(\hat{N}+P+1)^{-1}$ is defined since the operator of which it is
meant to be the inverse does not have zero for eigenvalue. Iterating, we have

$\hat{b}^{\ell}\,H_{2n+\epsilon}(x)=2^{2\ell}\,\frac{n!}{(n-\ell)!}\,H_{2(n-\ell)+\epsilon}.$
(4.5)

This allows to write eq. (3.18) of Theorem 3.1 in the form:

$V_{\mu}\,H_{2n+\epsilon}=\frac{(\frac{1}{2})_{n+\epsilon}}{(\mu+\frac{1}{2})_{n+\epsilon}}\,\sum_{\ell=0}^{n}\frac{(-1)^{\ell}}{\ell!}\,\hat{b}^{\ell}\,H_{2n+\epsilon}(x).$
(4.6)

We here observe that the sum in the formula above can be extended to infinity
since

$\hat{b}^{\ell}\,H_{2n+\epsilon}(x)=0\qquad\text{for}\qquad\ell=n+1,n+2,\dots.$
(4.7)

We thus arrive at an expression for $V_{\mu}$ in terms of oscillator
operators.

###### Theorem 4.1

On the Hilbert space $L^{2}(\mathbb{R},e^{-x^{2}}dx)$, the Dunkl intertwining
operator $V_{\mu}$ admits the following bosonic realization

$V_{\mu}={{}_{1}}F_{0}\left({\mu\atop-};-\hat{b}\right),$ (4.8)

with ${{}_{1}}F_{0}$ referring to the usual notation of hypergeometric
functions [22, 25].

##  5 Conclusion

This paper has offered observations on the Dunkl intertwining operator
$V_{\mu}$ in one dimension. It has provided its action in the basis of Hermite
polynomials and, as a result, identified its realization in terms of bosonic
operators. Knowing that the operator $V_{\mu}$ maps the Hermite polynomials on
the generalized Hermite polynomials, this therefore gave the connection
formula relating the two families of polynomials.

This study has a kinship with the work performed in [26] aimed at constructing
the higher families of the Askey scheme [22] from the lower ones and at adding
parameters (like $\mu$ here) from the action of functions of operators
identified from connection formulas.

It suggests also that more cases would deserve an analysis similar to the one
performed here. Indeed we may mention two cases of polynomial families related
by the Dunkl intertwiner: the pair formed by the generalized Gegenbauer
polynomials and the ordinary ones [16] and as well the tandem made out of the
little $-1$ Jacobi polynomials and special Jacobi polynomials [17]. Exploring
connection formulas in these instances would certainly be worthwhile.

From the standpoint of 1-D quantum mechanical systems, the Dunkl intertwiner
maps the wave functions of the harmonic oscillator into those of the Dunkl
oscillator. It is not difficult to see that a gauge transform of the Dunkl
oscillator Hamiltonian corresponds to the singular (or radial) oscillator with
a reflection dependent centrifugal term [27]. Sticking to one parity sector,
say the even one, at the price of not having a unified framework, one finds
that the wave functions of the singular oscillator are obtained from those of
the harmonic oscillator with an even number of excitations. This is the view
taken in [15]. This observation is in keeping with the fact that on the one
hand, the states of the harmonic oscillator with a fixed parity support
metaplectic representations of $\mathfrak{su}(1,1)$ which is then mapped onto
the $\mathfrak{su}(1,1)$ irreducible representation space spanned by the
states of the singular oscillator. On the other hand, the Dunkl oscillator
like the harmonic oscillator exhibits $\mathfrak{osp}(1|2]$ supersymmetry as
expressed by the mapping of the entire Hilbert space of both systems into one
another by the Dunkl intertwiner.

Finally, looking at multivariate situations should retain attention. There
have been various studies like [28] connecting integrable models such as the
Calogero-Sutherland one and the Virasoro algebra (or generalizations) through
bosonization. This had significant impact on the study of symmetric functions.
We may then ask the question of what bearing could bosonization further have
on the study of Dunkl intertwining operators in this context. We hope to have
modestly instilled interest in these various questions.

## Acknowledgments

The work of LV is supported in part by a Discovery Grant from the Natural
Sciences and Engineering Research Council (NSERC) of Canada. AZ who is funded
by the National Foundation of China (Grant No.11771015) gratefully
acknowledges the hospitality of the CRM over an extended period and the award
of a Simons CRM professorship.

## References

  * [1] C. F. Dunkl.  Differential-difference operators associated to reflection groups.  Transactions of the American Mathematical Society, 311(1):167–183, 1989.
  * [2] C. F. Dunkl and Y. Xu.  Orthogonal polynomials of several variables.  Number 155. Cambridge University Press, 2014.
  * [3] L. Lapointe and L. Vinet.  Exact operator solution of the Calogero-Sutherland model.  Communications in mathematical physics, 178(2):425–452, 1996.
  * [4] J.-Ph. Anker.  An introduction to Dunkl theory and its analytic aspects.  In Analytic, Algebraic and Geometric Aspects of Differential Equations, pages 3–58. Springer, 2017.
  * [5] C. F. Dunkl.  Reflection groups in analysis and applications.  Japan. J. Math, 3:215–246, 2008.
  * [6] G.J. Heckman.  Dunkl operators.  Astérisque, pages 223–223, 1997.
  * [7] M. Rösler.  Dunkl operators: theory and applications.  In Orthogonal polynomials and special functions, pages 93–135. Springer, 2003.
  * [8] C. F. Dunkl.  Integral kernels with reflection group invariance.  Canadian Journal of Mathematics, 43(6):1213–1227, 1991.
  * [9] C. F. Dunkl.  Intertwining operators associated to the group $S_{3}$.  Transactions of the American Mathematical Society, 347(9):3347–3374, 1995.
  * [10] C. F. Dunkl.  An intertwining operator for the group $B_{2}$.  Glasgow Mathematical Journal, 49(2):291–319, 2007.
  * [11] M. Rösler and M. Voit.  Positive intertwiners for Bessel functions of type B.  arXiv:1912.12711, 2019.
  * [12] Y. Xu.  Intertwining operator associated to symmetric groups and summability on the unit sphere.  arXiv:2004.08727, 2020.
  * [13] H. De Bie and P. Lian.  The Dunkl kernel and intertwining operator for dihedral groups.  Journal of Functional Analysis, 280(7):108932, 2021.
  * [14] A. Morozov and L. Vinet.  q-Hypergeometric functions in the formalism of free fields.  Modern Physics Letters A, 8(30):2891–2902, 1993.
  * [15] S. Odake.  Free Oscillator Realization of the Laguerre Polynomial.  arXiv:2008.10756, 2020.
  * [16] Y. Ben Cheikh and M. Gaied.  Characterization of the Dunkl-classical symmetric orthogonal polynomials.  Applied mathematics and computation, 187(1):105–114, 2007.
  * [17] L. Vinet and A. Zhedanov.  A ‘missing’ family of classical orthogonal polynomials.  Journal of Physics A: Mathematical and Theoretical, 44(8):085201, 2011.
  * [18] G. Szegő.  Orthogonal polynomials, volume 23.  American Mathematical Soc., 1939.
  * [19] T. S. Chihara.  An introduction to orthogonal polynomials.  Courier Corporation, 2011.
  * [20] M. Rosenblum.  Generalized Hermite polynomials and the Bose-like oscillator calculus.  In Non selfadjoint operators and related topics, pages 369–396. Springer, 1994.
  * [21] V. X. Genest, M. E. H. Ismail, L. Vinet, and A. Zhedanov.  The Dunkl oscillator in the plane: I. Superintegrability, separated wavefunctions and overlap coefficients.  Journal of Physics A: Mathematical and Theoretical, 46(14):145201, 2013.
  * [22] R. Koekoek, P. A. Lesky, and R. F. Swarttouw.  Hypergeometric orthogonal polynomials and their q-analogues.  Springer Science & Business Media, 2010.
  * [23] Y. L. Luke.  Mathematical functions and their approximations.  Academic Press, 2014.
  * [24] J. Sánchez-Ruiz and J. S. Dehesa.  Expansions in series of orthogonal hypergeometric polynomials.  Journal of computational and applied mathematics, 89(1):155–170, 1998.
  * [25] G. Gasper and M. Rahman.  Basic hypergeometric series, volume 96.  Cambridge university press, 2004.
  * [26] M. Atakishiyeva and N. Atakishiyev.  On lifting q-difference operators in the Askey scheme of basic hypergeometric polynomials.  Journal of Physics A: Mathematical and Theoretical, 43(14):145201, 2010.
  * [27] V. X. Genest, J.-M. Lemay, L. Vinet, and A. Zhedanov.  The Hahn superalgebra and supersymmetric Dunkl oscillator models.  Journal of Physics A: Mathematical and Theoretical, 46(50):505204, 2013.
  * [28] H. Awata, Y. Matsuo, S. Odake, and J. Shiraishi.  Excited states of the Calogero-Sutherland model and singular vectors of the $W_{N}$ algebra.  Nuclear Physics B, 449(1-2):347–374, 1995.


11institutetext: Indian Statistical Institute, Kolkata, India

# Burning a binary tree and its generalization

Sandip Das  Sk Samim Islam  Ritam M Mitra  Sanchita Paul Corresponding author

###### Abstract

Graph burning is a graph process that models the spread of social contagion.
Initially, all the vertices of a graph $G$ are unburnt. At each step, an
unburnt vertex is put on fire and the fire from burnt vertices of the previous
step spreads to their adjacent unburnt vertices. This process continues till
all the vertices are burnt. The burning number $b(G)$ of the graph $G$ is the
minimum number of steps required to burn all the vertices in the graph. The
burning number conjecture by Bonato et al. states that for a connected graph
$G$ of order $n$, its burning number $b(G)\leq\lceil\sqrt{n}\rceil$. It is
easy to observe that in order to burn a graph it is enough to burn its
spanning tree. Hence it suffices to prove that for any tree $T$ of order $n$,
its burning number $b(T)\leq\lceil\sqrt{n}\rceil$ where $T$ is the spanning
tree of $G$. It was proved in 2018 that
$b(T)\leq\lceil\sqrt{n+n_{2}+1/4}+1/2\rceil$ for a tree $T$ where $n_{2}$ is
the number of degree $2$ vertices in $T$. In this paper, we provide an
algorithm to burn a tree and we improve the existing bound using this
algorithm. We prove that $b(T)\leq\lceil\sqrt{n+n_{2}+8}\rceil-1$ which is an
improved bound for $n\geq 50$. We also provide an algorithm to burn some
subclasses of the binary tree and prove the burning number conjecture for the
same.

###### Keywords:

Binary Tree Graph Burning Algorithm.

##  1 Introduction

Graph burning is a process that captures the spread of social contagion and
was introduced by Bonato, Janssen, and Roshanbin [4] in 2014. The way ideas
and feelings spread among people on social networks is a hot topic in social
network research. For instance, check out these studies [1, 10, 11, 12, 15,
16]. A recent study focused on how emotions spread on Facebook [13]. What’s
interesting is that it found that the structure of the network itself is
crucial. Surprisingly, you don’t need to meet someone in person or see their
body language for emotions to spread. Instead, people in the network share
these feelings with their friends or followers, and it keeps spreading over
time. Now, here’s the question: If you wanted to make this emotional spread
happen as quickly as possible across the whole network, who should you start
with, and in what order? To address this problem, we study graph burning. We
can think that each person or profile is a vertex of a graph. Two people can
share their feelings in one step if there is an edge between them. We say a
vertex is burnt if the feeling is spread to the vertex.

Below, we describe the process of burning a simple graph $G(V,E)$ where
$|V|=n$. Graph burning consists of discrete steps. After each step, each
vertex is either burnt or unburnt, once a vertex is burnt it remains burnt
till the end. Initially, all the vertices are unburnt. In the first step, we
burn a vertex. At each subsequent step, two things happen: first, one new
unburned vertex is chosen to burn; second, the fire spreads from each burnt
vertex of the previous step to its neighboring vertices and burns the unburned
vertices from the neighbors. If a vertex is burned, then it remains in that
state until the end of the process. The process ends when all the vertices are
burnt. The burning number, denoted by $b(G)$, is the minimum number of steps
taken for this process to end. The burning problem asks, given a graph G and
an integer $k\geq 2$, whether $b(G)\leq k$. An intuitive way to look at this
process is to cover the vertices of the graph $G$ by $k$ balls of radius
$0,1,\ldots,k-1$, placed at appropriate vertices such that $b(G)$ is
minimized. A ball of radius $r$ placed at a vertex $v$ can cover vertices that
are at a distance of at most $r$ from $v$. For example, it is straightforward
to see that $b(K_{n})=2$. However, even for a relatively simple graph such as
the path $P_{n}$ on $n$ nodes, computing the burning number is more complex;
in fact, $b(P_{n})=\lceil\sqrt{n}\rceil$ as [4] proved. Suppose that in the
process of burning a graph $G$, we eventually burn the whole graph $G$ in $k$
steps, and for each $i$, $1\leq i\leq k$, we denote the node where we set the
fire in the $i$th step by $x_{i}$. We call such a node simply a source of
fire. The sequence $(x_{1},x_{2},\ldots,x_{k})$ is called a burning sequence
for $G$.

Graph burning can be likened to the way viruses propagate within populations.
When left uncontrolled, a limited number of infected individuals within a
population can lead to the widespread transmission of the virus. Similarly,
one can draw an analogy to a forest fire, which, when left to burn without
intervention, can devastate entire forests across a vast expanse.

Bessy et al. [2] showed that the Graph Burning problem is NP-complete when
restricted to the trees of maximum degree three. This implies that the burning
graph problem is NP-complete for binary trees, chordal graphs, bipartite
graphs, planar graphs, and disconnected graphs. Moreover, they showed the NP-
completeness of the burning problem even for trees with a structure as simple
as spider graphs, and also for disconnected graphs such as path-forests.
Furthermore, there is a polynomial time approximation algorithm with
approximation factor $3$ for general graphs. Hence, determining the precise
burning number of a graph is currently not the primary focus. Now, a question
can be raised: Is there any tight relation between the burning number and the
number of vertices of a graph? Bonato, Janssen, and Roshanbin [5] proposed the
Burning Number Conjecture that relates these two numbers of a graph.

Burning Number Conjecture (BNC): Let $G$ be a connected graph of order $n$,
then $b(G)\leq\lceil\sqrt{n}\rceil$.

In order to burn a connected graph, it is sufficient to burn its spanning
trees [5]. Therefore, in the study of graph burning, much focus has been spent
on the trees. Note that, if $T$ is a spanning tree of a graph $G$, then
$b(G)\leq b(T)$, since the number of steps required to burn $T$ is at least
the number of steps required to burn $G$. Therefore, if the BNC holds for all
the trees, then it definitely holds for all the graphs. Now the main challenge
is to solve the BNC for the trees. Till now the BNC has been solved for some
subclasses of trees including Spider [7, 9], Double spider [17], Caterpillars
[14].

Our Contribution: In this paper, we study the graph burning problem on several
types of binary trees.

A perfect binary tree is a special type of binary tree in which all the leaf
nodes are at the same level and all internal nodes have exactly two children.
In Section 3, we provide a relation between the height and the burning number
of a perfect binary tree:

######  Theorem 1.1 ()

Let $T$ be a perfect binary tree of height $h$, then $b(T)=h+1$.

Using Theorem 1.1, we show that the BNC is true for the perfect binary tree.

Section 4 is based on the study of the graph burning problem on the complete
binary tree. A complete binary tree is a binary tree in which every level,
except the last, is completely filled, and all nodes in the last level are
filled from as left as possible. We provide a relation between the height and
the burning number of a complete binary tree:

######  Theorem 1.2 ()

Let $T$ be a binary tree of height $h$ which needs exactly $1$ more leaf to be
perfect. Then $b(T)=h+1$.

######  Theorem 1.3 ()

Let $T$ be a complete binary tree of height $h$ which does not have at least
$2$ leaves in it’s last level. Then $b(T)=h$.

Using Theorem 1.2 and Theorem 1.3, we show that the BNC is true for the
complete binary tree.

A full binary tree is a binary tree in which all of the nodes have either $0$
or $2$ children. In other words, except for the leaf nodes, all other nodes
have two children, and it is not necessary for all leaf nodes to be at the
same level. In section 5, we show that the burning number of a full binary
tree which is not perfect is upper bounded by its height. We state that in the
following theorem:

######  Theorem 1.4 ()

Let $T$ be a full binary tree of height $h$, which is not perfect, then
$b(T)\leq h$.

In the same section, we provide an algorithm to burn the full binary tree
which is not perfect, that yields the following Theorem which says the BNC is
true for the same:

######  Theorem 1.5 ()

Let $T$ be a full binary tree of $n$ vertices, which is not perfect. Then we
have $b(T)\leq\lceil\sqrt{n}\rceil$.

Moreover, we provide a tighter bound of the burning number for the full binary
tree which is not perfect having the number of vertices more than $17$. We
state that in the following theorem:

######  Theorem 1.6 ()

Let $T$ be a full binary tree on $n$ vertices, which is not perfect, then
$b(T)\leq\lceil\sqrt{n+9}\rceil-1$.

In 2018, Bessy et al. proved [3] that
$b(T)\leq\lceil\sqrt{n+n_{2}+1/4}+1/2\rceil$ for a tree $T$ where $n_{2}$ is
the number of degree $2$ vertices in $T$. Using Theorem 5, we improve this
bound for the trees having the number of vertices at least $50$. The improved
bound is the following:

######  Theorem 1.7 ()

Let $T$ be a tree of order n and $n_{2}$ be the number of degree 2 vertices.
Then $b(T)\leq\lceil\sqrt{n+n_{2}+8}\rceil-1$.

##  2 Preliminaries

Since every connected graph is spanned by a tree, burning the spanning tree is
sufficient to burn the connected graph’s vertices. Binary trees are the most
commonly known trees, which have several applications in data structure and
algorithms [8]. Binary trees have the characteristic feature that they are
rooted trees, and every vertex has at most two children. The depth of a node
in a tree is the number of edges present in the path from the root node to
that node. For a binary tree $T$, any two vertices are said to be at the same
level if they are at the same depth from the root. The root is considered to
be at the 1st level, and any other vertex that is at level $i$ is said to be
$i-1$ distant from the root. Any non-leaf node is said to be an internal node.
We call the internal nodes that are the parents of leaves as parent-leaves. We
call one node to be the sibling of other if they have a common parent. The
height of a node is the number of edges present in the path connecting that
node to a leaf node. For any other definition, we follow the standard notation
of West [18].

Given a positive integer $k$, the $k$-th closed neighbourhood of $v$ in a tree
$T=(V,E)$ is defined by $N_{k}[v]=\\{u\in V:d(u,v)\leq k\\}$.

##  3 Perfect Binary Tree

A perfect binary tree is a special type of binary tree in which all the leaf
nodes are at the same level and all internal nodes have exactly two children.
In simple terms, this means that all leaf nodes are at the maximum depth of
the tree. It is to be noted that a perfect binary tree of height $h$ has
$2^{h}$ number of leaf nodes.

See 1.1

###### Proof

$T$ has total $h+1$ levels, since $T$ has height $h$. Suppose we set the fire
at the root of $T$ which is at the $1$st level. At the $t$-th step, the fire
completes the burning of the $t$-th level of $T$. Therefore, the burning of
the whole $T$ will be completed after $h+1$ steps, since $T$ has total $h+1$
levels. Therefore, $b(T)\leq h+1$.

Now we will show that $b(T)\geq h+1$. We prove this by contradiction. Suppose
there is a burning sequence $S=(x_{1},x_{2},\ldots,x_{\alpha})$, where
$\alpha<h+1$. After completing the burning of $T$ using this burning sequence,
the fire that was set on the vertex $x_{j}$ can spread to the vertices of the
ball $N_{\alpha-j}[x_{j}]$, for all $j$ where $1\leq j\leq\alpha$. Note that,
$N_{\alpha-j}[x_{j}]$ can contain at most $2^{\alpha-j}$ leaves of $T$.
Therefore, the total number of leaves that can be burned using the burning
sequence $S$ is at most $\sum_{j=1}^{\alpha}2^{\alpha-j}=2^{\alpha}-1$. But
the total number of leaves of $T$ is $2^{h}$. Now, $2^{h}\geq
2^{\alpha}>2^{\alpha}-1$. Therefore, all the leaves of $T$ can not be burned
by $S$, which is a contradiction. Therefore, $b(T)\geq h+1$. $\square$

A perfect binary tree $T$ of height $h$ is of order $n=2^{h+1}-1$, therefore,
we have $b(T)=h+1=\log_{2}(n+1)\leq\lceil\sqrt{n}\rceil$ for $n\geq 19$. This
validates the burning number conjecture for this graph class.

##  4 Complete Binary Tree

A complete binary tree is a binary tree in which every level, except the last,
is completely filled, and all nodes in the last level are filled from as left
as possible. The number of nodes (leaves) at the last level, ranges from $1$
to $2^{h}-1$, where $h$ is the height of the tree.

See 1.2

###### Proof

The fact that $b(T)\leq h+1$ can be determined by placing the source of fire
at the root of $T$ at the first step of burning.

We will now show that $T$ cannot be burnt in $h$ steps. On the contrary, let
$(x_{1},x_{2},\ldots,\\\ x_{h})$ be an arbitrary burning sequence of $T$,
i.e., $b(T)\leq h$. After completing the burning of $T$ using this burning
sequence, the fire that was set on the vertex $x_{i}$ can spread to the
vertices of the ball $N_{h-i}[x_{i}]$, for all $i$ where $1\leq i\leq h$. Now
we show that for $x_{i}$, the total number of leaves that can be burnt from
the fire spread from $x_{i}$, i.e., which are in $N_{h-i}[x_{i}]$ is at most
$2^{h-i}$ in number and maximality is attained only when $x_{i}$ is at $i+1$
th level. If $x_{i}$ is at $j$ th level where $1\leq j\leq i$, then any leaf
(say $l$) that is the descendant of $x_{i}$ remains unburnt from the fire
spread from $x_{i}$ since, $d(x_{i},l)=h+1-j\geq h+1-i>(h-i)$. Therefore, it
is necessary to place $x_{i}$ at $j(\geq i+1)$ th level to burn the leaves,
and furthermore, maximality can only be attained when $j=i+1$. Note that
$x_{h}$ cannot burn any more vertex except itself. Hence, the total number of
leaves and parent-leaves that can be burnt by all the $x_{i}$’s up to $h$ th
step of burning is at max
$\sum_{i=1}^{h-1}(2^{h-i}+2^{h-i-1})+1=2^{h}+2^{h-1}-2$. Again, since there is
only one leaf is missing at the $h+1$ th level, the total number of leaves and
parent leaves in $T$ is $(2^{h}-1)+2^{h-1}$. Therefore, at least $1$ vertex
(leaf/parent-leaf) is left unburnt after $h$ th step. Therefore $b(T)=h+1$.
$\square$

See 1.3

###### Proof

First, we show that $h$ steps are sufficient to burn $T$ in this case, i.e.,
$b(T)\leq h$. Let $c$ be the root of $T$ and $T_{1},T_{2}$ be two subtrees of
$T$ rooted at the two children $c_{1},c_{2}$ of $c$. Since $T$ is a complete
binary tree where at least two leaves are absent at its last level, at least
one among $T_{1},T_{2}$, let’s say $T_{1}$ is of height $h-1$, while $T_{2}$
is of height $h-2$ or $h-1$. Let $u_{1},u_{2},\ldots,u_{h-1}$ be the vertices
on a branch of $T_{2}$ that does not contain any leaf from $h+1$ th level (see
Figure 1) satisfying $d_{T}(c,u_{i})=i$ and $x_{i}$ be the sibling node of
$u_{i}$. Then $d(c,x_{i})=i$. We set $v_{1}=c_{1},v_{i}=x_{i},2\leq i\leq h-1$
and $v_{h}=u_{h-1}$. Now consider the sequence
$(v_{1},v_{2},\ldots,v_{h-1},v_{h})$. As every subtree rooted at $v_{i},1\leq
i\leq h-1$ is of height $h-i$ or $h-i-1$ and $v_{h}$ is a leaf node of
$T_{2}$, we get $\bigcup\limits_{i=1}^{h}N_{h-i}[v_{i}]=V(T)$. Therefore,
$(v_{1},v_{2},\ldots,v_{h})$ becomes the burning sequence of $T$. Thus, up to
$h$ steps $T$ must be burnt.

Now we will show that $T$ cannot be burnt in $h-1$ steps. Let $T^{\prime}$ be
the perfect binary subtree of $T$ having height $h-1$. If we assume on the
contrary that $T$ can be burnt in $h-1$ steps, then $T^{\prime}$ should also
be burnt in $h-1$ steps. But from Theorem 1.1 we know that $b(T^{\prime})=h$,
which contradicts our assumption. Hence $b(T)=h$. $\square$

Figure 1: Complete Binary Tree

A complete binary tree of height $h$ that does not contain exactly one leaf in
its last level is of order $2^{h+1}-2$. Hence
$b(T)=h+1=\log_{2}(n+2)\leq\lceil\sqrt{n}\rceil$ when $n\geq 20$. For the
other complete binary trees, $n\geq 2^{h}$, therefore,
$b(T)=h\leq\log_{2}n\leq\lceil\sqrt{n}\rceil$. Hence, the burning number
conjecture holds true for this subclass.

##  5 Full Binary Tree

A full binary tree is a binary tree in which all of the nodes have either $0$
or $2$ children. In other words, except for the leaf nodes, all other nodes
have two children, and it is not necessary for all leaf nodes to be at the
same level.

See 1.4

###### Proof

Let $c$ be the root and $x_{1},x_{2}$ be the two children of $c$ in $T$. By
induction hypothesis, we assume that the result is true for all such trees of
height less than $h$. Now consider the subtrees $T_{1},T_{2}$ of $T$ having
$x_{1},x_{2}$ as their roots. It is easy to note that $T_{1},T_{2}$ are two
disjoint trees. Also, they cannot be perfect binary trees of height $h-1$
simultaneously, as $T$ is not perfect. Without loss of generality, let $T_{1}$
be any full binary tree of height $h-1$ and $T_{2}$ be a full binary tree of
height $\leq h-1$ which is not perfect. Thus, using the algorithm stated in
the proof of Theorem 1.1, $T_{1}$ can be burnt in $h$ steps by only placing
fire at $x_{1}$ in the $1st$ step. Note that we do not need to set fire to any
other vertex of $T_{1}$ to burn it in $h$ steps. Now, by the induction
hypothesis, we know $b(T_{2})\leq h-1$. Also if $T_{2}$ is perfect and of
height $\leq h-2$ then it can be burned upto $h-1$ steps by the algorithm
stated in the proof of Theorem 1.1. Let the burning sequence to burn $T_{2}$
be $(y_{1},\ldots,y_{h-1})$. Thus, the burning sequence
$(x_{1},y_{1},\ldots,y_{h-1})$ is sufficient to burn $T$ upto $h$ steps.
Therefore, $b(T)\leq h$. $\square$

For convenience, we denote the class of full binary tree which is not perfect
by the notation FBTNP(Full Binary Tree Not Perfect).

###### Proposition 1

Given any positive integer $k$, there exists a maximal full binary tree
$T=(V,E)$ which is not perfect satisfying $|V|=3(2^{k}-1)-2k$, that can be
burnt in $k$ steps.

###### Proof

Figure 2: Maximal Burning

It is sufficient to create a burning sequence $(v_{1},v_{2},\ldots,v_{k})$ in
such a manner so that $N_{k-1}[v_{1}]\cup N_{k-2}[v_{2}]\cup\ldots\cup
N_{0}[v_{k}]=V$ for some FBTNP tree $T$ and $|V|=3(2^{k}-1)-2k$. Maximality
can be guaranteed whenever we are able to prevent all instances of double-
burning in $T$, i.e., if $T$ can be constructed in such a way that
$N_{k-i}[v_{i}]\cap N_{k-j}[v_{j}]=\emptyset$ for all $i\neq j$.

First, we construct a perfect binary tree $T(v_{1})$ (say) of height $k-1$,
rooted at the vertex $v_{1}$. Let $v_{1}^{\prime}$ be the neighbor of $v_{1}$
apart from the two children of $v_{1}$ in $T(v_{1})$. Clearly,
$v_{1}^{\prime}\notin V(T(v_{1}))$. Next, we create a perfect binary tree of
height $k-2$ rooted at $v_{1}^{\prime}$, say $T(v_{1}^{\prime})$ disjoint from
$T({v_{1}})$. It is important to note that, $T(v_{1})$ and $T(v_{1}^{\prime})$
are two separate perfect binary trees and are connected by the edge
$v_{1}v_{1}^{\prime}$. Let, $T_{1}=T(v_{1})\cup T(v_{1}^{\prime})$ be a
subtree of $T$. It is easy to verify that
$|N_{k-1}[v_{1}]|=|V(T_{1})|=|V(T(v_{1}))|+|V(T({v_{1}}^{\prime}))|=(2^{k}-1)+(2^{k-1}-1)=2^{k}+2^{k-1}-2$
(see Figure 2). We construct the subtrees $T_{2},T_{3},\ldots T_{k}$
sequentially in the aforementioned procedure where $T_{i}=N_{k-i}[v_{i}]$ and
$|T_{i}|=|N_{k-i}[v_{i}]|=2^{(k-i)+1}+2^{k-i}-2$ for $2\leq i\leq k$. We
create an edge between any two leaves of $T_{i},T_{j}$ for all $i\neq j$. Thus
we build $T=T_{1}\cup T_{2}\cup T_{3}\ldots\cup T_{k}$.

One can verify that $T$ is an FBTNP with the root as one of the leaves of
$T(v_{1}^{\prime})$. Furthermore, the total number of vertices of $T$ is
$(2^{k}+2^{k-1}-2)+\sum_{i=2}^{k}(2^{k-i+1}+2^{k-i}-2)=3(2^{k}-1)-2k$. Since
each of $T(v_{i})$ and $T(v_{i}^{\prime})$ are perfect binary trees of height
$k-i$ and $k-i-1$ respectively, and $v_{i}v_{i}^{\prime}\in E$, using Theorem
1.1 we can burn the FBTNP $T$ in $k$ steps. The maximality of $T$ is ensured
by the above construction. $\square$

###  5.1 Algorithm to burn an FBTNP

Figure 3: Cases in Full Binary Tree (case (a) at the top, case (b)(i) in the
middle, case (b)(ii) in the bottom)

In this subsection, we propose an algorithm to burn an FBTNP which is
recursive in nature. We construct a burning sequence $(v_{1},\ldots,v_{k})$ of
an FBTNP tree $T$ of height $h$ for some $k\in\mathbb{N}$. Our idea is to burn
a portion of the tree $T$ at each step by using one or two sources of fire.
When $k<h$, we cut the portion from the main tree in such a way that the
remaining graph becomes an FBTNP 111except some trivial situations where after
generating the sequence $(v_{1},\ldots,v_{k-2})$, the modified tree may not be
an FBTNP. In these cases, it can be $P_{2}$ or $K_{1,3}$ and both can be
burned by placing $v_{k-1}$ and $v_{k}$ itself with a smaller size. Otherwise,
only a single source of fire spreading upto $k$ steps is sufficient to burn
the whole tree. In the Theorem 1.5, we prove that for an FBTNP of order $n$,
the value of $k=\lceil\sqrt{n}\rceil$.

Algorithm:  Let $T=(V,E)$ be an FBTNP having
$P_{d+1}=(u_{0},u_{1},\ldots,u_{d})$ as the diametral path, where $d$ is the
diameter and $h$ be the height of $T$. Below we will construct a burning
sequence $(v_{1},v_{2},\dots v_{k})$ of $T$ for some $k\in\mathbb{N}$. For
$0\leq i\leq d$, we define $T(u_{i})$ to be the subtree rooted at $u_{i}$,
formed by the branches of $T$ attached to the vertices
$u_{0},u_{1},\ldots,u_{i}$ excluding the branch $(u_{i+1},\ldots,u_{d})$. Let
$u_{c}$ be the root of $T$ and $p_{i}$ be the neighbour of $u_{i}\neq u_{c}$,
where $p_{i}\neq u_{i-1}$ or $u_{i+1}$. Similarly, another subtree
$T^{\prime}(u_{i})$ rooted at $u_{i}$ can be formed by the branches attached
to the vertices $u_{i},u_{i+1},\ldots,u_{d}$, excluding the branch
$(u_{0},\ldots,u_{i-1})$ at $u_{i}$ in $T$.

In order to burn the tree $T$ in $k$ steps, we consider the two circumstances.

$1$) Let $k\geq h$. If the root $u_{c}$ lies on the diametral path
$(u_{0},\ldots,u_{c},\ldots,u_{k},\ldots,u_{d})$. Then either $u_{c}=u_{k-1}$
or it occurs left to $u_{k-1}$ along the path $P_{d+1}$. We place $v_{1}$ at
$u_{c}$ to burn $T(u_{c})\cup T^{\prime}(u_{c})=T$ up to $k$ steps.

In the other situation, i.e., when the root $u_{c}$ is not on the diametral
path $P_{d+1}$, then it must be on a branch attached to some $u_{l}$, where
$0<l<k$ or $d-k<l<d$. Without loss of generality, we assume $0<l<k$ and
$p_{m}$ be the maximum distance vertex on that branch measured from $u_{l}$.
We place $v_{1}$ at $u_{l}$ to burn $T(u_{l})\cup T^{\prime}(u_{l})=T$ up to
$k$ steps.

Choices of $v_{2},\ldots,v_{k}$ in this case, can be arbitrary.

$2$) Let $k<h$. We will apply the following technique to form the burning
sequence $(v_{1},v_{2},\ldots,v_{k})$ of $T$. We start the algorithm from the
maximum end of $P_{d+1}$, calculated from the root of $T$. If both of the
endpoints of $P_{d+1}$ are of the same distance from the root, then we can
start from any end. Without loss of generality, assume that $u_{0}$ is at
maximum distance from the root (Refer to Figure 3).

Step I:

a) Let the number of vertices of the subtree $T(u_{k-2})$ be greater than
equal $2k-1$. Then the order of $T(u_{k-2})\cup\\{p_{k-1}\\}$ becomes $\geq
2k$. One can observe that for this to happen there must exist at least one
branch from a vertex $u_{i}$, $1\leq i\leq k-2$ having its height $\geq 2$
which is different from $P_{d+1}$. Now we place $v_{1}$ at $u_{k-1}$ in order
to burn the vertices of $T(u_{k-2})\cup\\{p_{k-1}\\}$ upto $k$ steps.

Next, we update the diametral path $P_{d+1}$ to
$P_{d-k+2}=(u_{k-1},u_{k},\ldots,u_{d})$. It is important to note that we
include $u_{k-1}$ in the updated diametral path so that the modified tree
$T^{\prime}(u_{k})\cup\\{u_{k-1}\\}$ preserves all the features of the initial
tree $T$.

b) Next, we consider the case when the order of the subtree $T(u_{k-2})$ is
less than $2k-1$. Since $k<h$, no vertex $u_{i}$, $0\leq i\leq k$ can be the
root of $T$. Therefore $|V(T(u_{k-2})|\geq 2k-3$ and hence
$T(u_{k-1})\cup\\{p_{k}\\}$ is of order $\geq(2k-3)+3=2k$ as $T$ is an FBTNP.

The following situations may further occur.

i) The branch attached to $u_{k}$ different from $P_{d+1}$ is of maximum
height $k-2$. Then we place $v_{1}$ at $u_{k-1}$ to burn the vertices of
$T(u_{k-1})\cup\\{p_{k}\\}$ upto $k$ steps.

ii) The branch attached to $u_{k}$ different from $P_{d+1}$ is of height $k-1$
or $k$. Let $p_{m}$ be the last vertex in the attached branch. Then $m=k$ or
$k-1$. Apart from $p_{k}$, there must be at least $2k-2$ vertices in this
branch. We place $v_{1}$ at $p_{k}$ and $v_{2}$ at $u_{k-2}$ so that up to $k$
th step the total number of vertices burnt due to the fire spread from the
vertices $v_{1},v_{2}$ become $\geq 4k-4$.

After this, the diametral path $P_{d+1}$ of $T$ is updated, resulting in the
new diametral path $P_{d-k+1}=(u_{k},\ldots,u_{d})$. In order to ensure that
the modified tree $T^{\prime}(u_{k+1})\cup\\{u_{k}\\}$ retains all the
properties of the original tree $T$, we include the vertex $u_{k}$ in the
updated diameter 222in both of these cases, we have placed $v_{1}$ or
$\\{v_{1},v_{2}\\}$ on the branches of $T$ in a suitable manner so that the
modified tree remains a connected FBTNP and the remaining graph completely
burns upto $k$ steps.

Step II: Repeat Step I.

See 1.5

###### Proof

Let $P_{d}=(u_{0},u_{1},\ldots,u_{d})$ be the diametral path of $T$. We follow
the Algorithm 5.1 to burn $T$ in $k$ steps. We will use induction on $|V(T)|$
to prove the theorem.

Induction Hypothesis : Suppose the result is true for all FBTNP trees having
order less than equal $t^{2}$, i.e., if $|V(T)|\leq t^{2}$ then we get
$b(T)\leq t$.

Inductive Step: Consider an FBTNP tree $T$ of $m$ verices such that
$t^{2}<m\leq(t+1)^{2}$. In order to prove the theorem, it is sufficient to
show that $T$ can be burnt in $t+1$ steps. Assume $k=t+1$.

First, we consider the situation when $k\geq h$. If $u_{c}$ is on $P_{d+1}$
then $h=d(u_{0},u_{c})<d(u_{c},u_{k})=k$. In the other situation,
$d(u_{0},u_{c})=h<k=d(u_{0},u_{k})$ imply $d(u_{0},u_{l})<k$. Again,
$d(u_{l},u_{d})<d(u_{c},u_{d})<h\leq k$. Furthermore, $d(u_{l},u_{m})<k$
follows from the definition of diametral path $P_{d+1}$. More specifically,
$N_{k-1}[v_{1}]=V(T)$ as $v_{1}=u_{l}$. Therefore all the vertices of $T$ will
get burnt up to $k=t+1$ th step due to the fire spread from $v_{1}$.

Next, we consider the case when $k<h$. For Case (a) and Case (b) (i), the
total number of vertices burnt due to the fire spread from $v_{1}$ upto $t+1$
th step is $\geq 2(t+1)\geq 2t+2$. Moreover, since $P_{d+1}$ is the diametral
path, any branch attached to $u_{k-1}$ is of maximum height $k-1$ and the
branch attached to $u_{k}$ is of maximum height $k-2$ in case (b) (i).
Therefore, after placing $v_{1}$ at $u_{k-1}$, the subtree $T(u_{k-1})$ in
case (a) and the subtree $T(u_{k})$ in case (b)(i) will be completely burnt up
to $k$ steps.

One can observe that the order of the modified tree becomes less than equal to
$m-2t-2$ after updating the diameter for both of the above cases. Since
$m\leq(t+1)^{2}$, the number of vertices of the modified tree is
$\leq(t+1)^{2}-2t-2=t^{2}-1<t^{2}$. Thus, the modified tree can be burnt in
$t$ steps by the induction hypothesis.

For Case (b) (ii), the total number of vertices burnt as a result of the fire
spreading from $v_{1},v_{2}$ up to $t+1$ th step is $\geq 4(t+1)-4\geq 4t$.
Also, it is important to note that any branch attached to $u_{k}$ can be of
maximum height $k$, as a result, the placement of $v_{1},v_{2}$ as described
in the algorithm ensures the complete burnability of the subtree $T(u_{k})$ up
to $k$ th step. Due to this burning, the order of the modified tree becomes
less than equal $m-4t\leq(t+1)^{2}-4t\leq(t-1)^{2}$. Therefore, according to
the induction hypothesis the modified tree can be burnt in $t-1$ steps.

Conclusion: Thus, by induction the FBTNP $T$, having $|V(T)|\leq(t+1)^{2}$ can
be burnt in $(t+1)$ steps. Hence we get $b(T)\leq\lceil\sqrt{m}\hskip
3.00003pt\rceil$. $\square$

###  5.2 Improved Bound Algorithm to burn an FBTNP

Algorithm : Let $P_{d+1}=(u_{0},u_{1},\ldots,u_{d})$ be the diametral path
where $d$ is the diameter and $h$ be the height of an FBTNP $T=(V,E)$. We
consider the following cases, depending on which we develop a method to burn
the tree $T$ in $k$ steps. The burning sequence of $T$ will be built as
$(v_{1},v_{2},\ldots v_{k})$. If $k\geq h$, then we follow the method to burn
$T$ as described in Algorithm 5.1. Now we will consider the situation when
$k<h$. Let $L_{i}=(p_{i,1},p_{i,2},\ldots,p_{i,h^{\prime}})$ be the branch
attached to $u_{i}$ different from $P_{d+1}$ where $1\leq i\leq d-1$ and
$h^{\prime}=d(u_{i},p_{i,h^{\prime}})$ be the height of $L_{i}$ computed from
$u_{i}$. To keep the notations simple, we denote the subtree rooted at
$p_{i,l}$, $1\leq l\leq h^{\prime}$ by considering all the branches which are
attached to the path $(p_{i,l},\ldots,p_{i,h^{\prime}})$. Other notations will
remain the same as in Algorithm 5.1.

Step I:

Case 1: First, we consider the case where $T(u_{k-1})$ has order $\geq 2k+1$.
Here are three situations that may happen. For this to happen, there must be a
branch from some $u_{i}$, $1\leq i\leq k-1$ of height $\geq 2$ that is
different from $P_{d+1}$.

a) If the branch $L_{k-1}$ attached to $u_{k-1}$ is of height $\geq 2$, then
order of $T(u_{k-1})\setminus\\{u_{k-1}\\}\geq 2k+2$. In this situation, we
place $v_{1}$ at $u_{k-1}$ to burn $\geq 2k+2$ vertices up to $k$ steps. Next,
we update the diametral path $P_{d+1}$ to $P_{d-k+2}=(u_{k-1},\ldots,u_{d})$.
It is important to note that we include the vertex $u_{k-1}$ in the updated
diametrical path so that the modified tree
$T^{\prime}(u_{k})\cup\\{u_{k-1}\\}$ retains all properties of the original
tree $T$.(Refer Figure 4(a))

(a)

(b)

(c)

(d)

Figure 4: Case 1

b) Next, we consider the situation when $L_{k-1}$ is of height $1$, i.e., a
single pendant is attached to $u_{k-1}$. We observe that
$T(u_{k-1})\cup\\{p_{k,1}\\}$ have order $\geq 2k+2$.

If the branch $L_{k}$ attached to $u_{k}$ is of height at most $k-2$, then we
place $v_{1}$ at $u_{k-1}$ to burn $T(u_{k-1})\cup\\{p_{k,1}\\}$.(see Figure
4(b)).
Again, if $L_{k}$ is of height $k$, then we place $v_{1}$ at $p_{k,1}$ and
$v_{2}$ at $u_{k-2}$ to burn $\geq 4k$ vertices. In both of these situations,
we update the diametral path $P_{d+1}$ to $P_{d-k+1}=(u_{k},\ldots,u_{d})$ and
the modified FBTNP becomes $T^{\prime}(u_{k+1})\cup\\{u_{k}\\}$. (Refer Figure
4(d))

When $L_{k}$ is of height $k-1$ and furthermore there is a branch of height
$\geq 2$ at $p_{k,1}$ different from $L_{k}$, then by placing $v_{1}$ at
$p_{k,1}$ and $v_{2}$ at $u_{k-2}$ we burn $T(u_{k})\setminus\\{u_{k}\\}$ upto
$k$ steps, i.e. total of $\geq 4k$ vertices, otherwise, we place $v_{1}$ at
$u_{k-1}$ to burn $\geq 4k-5$ many vertices to burn $T(u_{k})\setminus
T(p_{k,k-2})$ up to $k$ steps. Next, we place $v_{k-1}$ at $p_{k,k-2}$ to burn
$T(p_{k,k-2})$. Therefore, total $\geq 4k-2$ vertices get burnt by burning
$T(u_{k})\setminus\\{u_{k}\\}$ up to $k$ steps. Also, to burn the modified
tree $T^{\prime}(u_{k+1})\cup\\{u_{k}\\}$ we use Algorithm 5.1. (Refer Figure
4(c))

Case 2: Next, we consider the case when $T(u_{k-1})$ have order less than
$2k+1$. Since $k<h$, no vertex $u_{i}$, $0\leq i\leq k$ can be the root of
$T$. Therefore, number of vertices of $T(u_{k-1})$ is $\geq 2k-1$. In fact,
$|V(T(u_{k-1})|=2k-1$ as $T$ is an FBTNP. Hence the total number of vertices
of $T(u_{k})\geq(2k-1)+2=2k+1$. The following situations may arise:

a) First, we consider the situation when the branch $L_{k}$ attached to
$u_{k}$ is of height $\geq 2$.

(a)

(b)

(c)

Figure 5: Case 2a

If the branch $L_{k}$ attached to $u_{k}$ is of maximum height $k-2$, then
order of $T(u_{k})\setminus\\{u_{k}\\}$ is $\geq(2k-1)+3=2k+2$. We place
$v_{1}$ at $u_{k-1}$ to burn $\geq 2k+2$ vertices to burn
$T(u_{k})\setminus\\{u_{k}\\}$ up to $k$ steps. Next, we update the diametral
path $P_{d+1}$ to $P_{d-k+1}=(u_{k},\ldots,u_{d})$ so that the modified FBTNP
becomes $T^{\prime}(u_{k+1})\cup\\{u_{k}\\}$. (Refer Figure 5(a))

Now, consider the situation when $L_{k}$ is of height $k$. If there is a
branch of height $\geq 2$ from any $p_{k,i}$ where $1\leq i\leq k-2$, then
$|V(T(p_{k,1})|\geq 2k+1$. We can modify the diametral path $P_{d+1}$ to
$(p_{k,k},\ldots,p_{k,1},u_{k},\ldots,u_{d})$ and hence we can apply Case $1$
by taking $|V(T(p_{k,1})|\geq 2k+1$. In another situation, order of
$T(u_{k})\setminus\\{u_{k}\\}$ is $(2k-1)+(2k-1)=4k-2$. Therefore, we place
$v_{1}$ at $u_{k-1}$ and $v_{k-1}$ at $p_{k,k-1}$ and $v_{k}$ at the pendant
attached to $p_{k,k-2}$ to burn $4k-2$ vertices up to $k$ steps. (Refer Figure
5(c))

Again, if $L_{k}$ is of height $k-1$, we place $v_{1}$ at $u_{k}$ and
$v_{k-1}$ at $u_{1}$ to burn $4k-4$ vertices of the subtree
$T(u_{k})\setminus\\{u_{k}\\}$. In both of these circumstances, we update the
diametral path to $P_{d-k+1}$ and to burn the modified FBTNP
$T^{\prime}(u_{k+1})\cup\\{u_{k}\\}$ we apply Algorithm 5.1. (Refer Figure
5(b))

b) If there is only one pendant attached to $u_{k}$, i.e.,
$|V(T(u_{k})|=2k+1$. Let $u_{k+1}$ be the root of $T$. Then we place $v_{1}$
at $u_{k-1}$ to burn to burn $2k+2$ vertices of the subtree $T(u_{k+1})$ in
$k$ steps. We update the diametral path $P_{d+1}$ to
$L_{k+2}\cup(u_{k+2},\ldots,u_{d})$ and hence the modified FBTNP becomes
$T^{\prime}(u_{k+2})$.

(a)

(b)

(c)

(d)

(e)

Figure 6: Case 2b

Now, consider the situation when $u_{k+1}$ is not the root of $T$. Let
$T(u_{k})\cup\\{p_{k+1,1}\\}$ has order $\geq 2k+2$. Since $k<h$, no vertex of
the path $L_{k+1}$ can be the root of $T$.

If the branch $L_{k+1}$ attached to $u_{k+1}$ is of height $\leq k-3$, then we
place $v_{1}$ at $u_{k-1}$ to burn $T(u_{k+1})$ up to $k$ steps. Next, we
update the diametral path $P_{d+1}$ to $P_{d-k}=(u_{k+1},\ldots,u_{d})$ so
that the modified FBTNP becomes $T^{\prime}(u_{k+2})\cup\\{u_{k+1}\\}$. (Refer
Figure 6(a))

If $L_{k+1}$ is of height $k+1$. Let the subtree $T(u_{k})\cup T(p_{k+1,1})$
have order exactly equals $4k+2$. Then every branch from the internal nodes of
$L_{k+1}$ is of height exactly equals $1$. We place $v_{1}$ at $p_{k+1,2}$ and
$v_{2}$ at $u_{k-2}$ to burn $T(u_{k+1})\setminus\\{u_{k}\\}$ up to $k$ steps.
Hence the modified FBTNP is $T^{\prime}(u_{k+2})\cup\\{u_{k+1}\\}$. (Refer
Figure 6(e))

Again, if the subtree $T(u_{k})\cup T(p_{k+1,1})$ has its order $>4k+2$, then
there must be some branch from the vertices of $L_{k+1}$ of height $\geq 2$,
different from $L_{k+1}$ as $|V(T(u_{k})|=2k+1$. Now, if the order of the
subtree $T(p_{k+1,2})\geq 2k+1$, then we update the diametral path $P_{d+1}$
to $L_{k+1}\cup(u_{k+1},\ldots,u_{d})$ and apply Case $1$, otherwise, i.e.,
when the order of the subtree $T(p_{{k+1},1})\geq 2k+3$ and
$|V(T(p_{k+1,2}))|=2k-1$, then also we update the the diametral path $P_{d+1}$
to $L_{k+1}\cup(u_{k+1},\ldots,u_{d})$ and apply Case $2$(a).

If the branch $L_{k+1}$ is of height $k$, then the order of the subtree
$T(u_{k})\cup T(p_{k+1,1})$ has order $\geq 4k$. We place $v_{1}$ at
$p_{k+1,1}$ and $v_{2}$ at $u_{k-2}$ to burn
$T(u_{k+1})\setminus\\{u_{k+1}\\}$ up to $k$ steps. After this, we update the
diametral path $P_{d+1}$ to $P_{d-k}$ so that the modified tree
$T^{\prime}(u_{k+2})\cup\\{u_{k+1}\\}$ preserves all properties of the initial
tree $T$. (Refer Figure 6(d))

When the branch $L_{k+1}$ is of height $k-1$, then if the order of the subtree
$T(u_{k})\cup T(p_{k+1,1})$ has order $4k-2(\geq 2k+2)$, then we place $v_{1}$
at $u_{k+1}$ and $v_{k-1}$ at $u_{1}$ and $v_{k}$ at the leaf of $u_{2}$ to
burn $T(u_{k+1})\setminus\\{u_{k}\\}$ up to $k$ steps (Refer Figure 6(c)).
After this placement, we update the diametral path to $P_{d-k}$ and the
modified FBTNP becomes $T^{\prime}(u_{k+2})\cup\\{u_{k+1}\\}$.

If the branch $L_{k+1}$ is of height $k-2$, then $T(u_{k})\cup T(p_{k+1,1})$
has order $\geq 4k-4$. We place $v_{1}$ at $u_{k}$ and $v_{k-1}$ at $u_{1}$ to
burn $T(u_{k})\cup T(p_{k+1,1})$ up to $k$ steps (Refer Figure 6(b)). Next, we
update the diametral path to $P_{d-k}$ so that the modified FBTNP becomes
$T^{\prime}(u_{k+2})\cup\\{u_{k+1}\\}$.

Step II: Repeat Step I.

See 1.6

###### Proof

Let $P_{d+1}=(u_{0},u_{1},\ldots,u_{d})$ be the diametral path of $T$. We
follow the Algorithm 5.2 to burn $T$ in $k$ steps. We will use induction on
$|V(T)|$ to prove the theorem.

Induction Hypothesis : Suppose, all FBTNP trees having order less than equal
$(t+1)^{2}-9$, i.e. $|V(T)|\leq(t+1)^{2}-9$ can be burnt in $t$ steps.

Inductive Step: Consider a tree $T$ with $m$ vertices such that
$(t+1)^{2}-9<m\leq(t+2)^{2}-9$. In order to prove the theorem, it is
sufficient to show that $T$ can be burnt in $t+1$ steps. We set $k=t+1$. For
$k\geq h$, the verification is similar to what we did in Theorem 1.5.

Consider the case when $k<h$. In the first step of Algorithm 5.2, different
vertices have been chosen as sources of fire as per requirement. The choices
are made among the following sources $\\{v_{1},v_{2},v_{k-1},v_{k}\\}$ before
updating the diametral path of $T$ for the first time. We have burnt a certain
number of vertices in each of the cases in such a manner so that the modified
FBTNP remains connected and the remaining graph gets burnt completely up to
$k$ steps. In each of the cases, we prove $k=\lceil\sqrt{n+9}\rceil-1$.

We select $v_{1}$ as a source of fire to burn $\geq 2k+2$ vertices for some
cases. Therefore, the number of vertices burnt due to the fire spread from
$v_{1}$ up to $t+1$ th step is $\geq 2t+4$. Therefore, the order of the
modified tree becomes less than equal $m-(2t+4)$. Since $m\leq(t+2)^{2}-9$,
the number of vertices of the modified tree is
$\leq(t+2)^{2}-9-(2t+4)=(t+1)^{2}-10<(t+1)^{2}-9$. Hence, it can be burnt in
$t$ steps by induction hypothesis.

We select $v_{1}$ and $v_{2}$ at suitable places over the branches of $T$ to
burn $\geq 4k$ vertices. Therefore, the number of vertices burnt up to $t+1$
th step from the fire spread from $v_{1},v_{2}$ is $\geq 4t+4$. Hence the
order of the modified tree is $\leq m-(4t+4)\leq(t+2)^{2}-9-4t-4=t^{2}-9$.
Therefore, the modified tree can be burnt in $t-1$ steps by induction
hypothesis.

The remaining cases have been proved with the help of Theorem 1.5.

We select $v_{1}$ and $v_{k-1}$ at appropriate locations over the branches of
$T$ to burn $\geq 4k-4$ vertices. Therefore, the number of vertices burnt up
to $t+1$ th step from the fire spread from $v_{1},v_{t}$ is $\geq 4t$. Hence
the order of the modified tree is $\leq m-4t\leq(t+2)^{2}-9-4t=t^{2}-5<t^{2}$.

Again, in some situations, to burn $4k-2$ vertices, we choose
$v_{1},v_{k-1},v_{k}$ suitably at proper places on the branches of $T$. Hence,
the number of vertices burnt up to $t+1$ th step from the fire spread from
$v_{1},v_{t},v_{t+1}$ is $\geq 4t+2$. Therefore, the order of the modified
tree is $m-(4t+2)\leq(t+2)^{2}-9-4t=t^{2}-7<t^{2}$. = (

We see in both of the above cases the modified tree has order $\leq t^{2}-5$.
Now, we claim that $(v_{2},\ldots,v_{t-2})$ is sufficient to burn the modified
tree. From the proof of Theorem 1.5, we know, we can burn a tree of order
$t^{2}$ in $t$ steps (i.e., $(v_{1}^{\prime},\ldots,v_{t}^{\prime})$. Note
that, the sources $v_{t-1}^{\prime}$ and $v_{t}^{\prime}$ burn a maximum of
$5$ vertices in an FBTNP. Thus, using
$(v_{1}^{\prime},\ldots,v_{t-2}^{\prime})$ is enough to burn a tree using a
tree of order $t^{2}-5$. It is easy to observe that the burning sequence
$(v_{2},v_{3},\ldots v_{t+1})$ is equivalent to
$(v_{1}^{\prime},v_{2}^{\prime},\ldots,v_{t}^{\prime})$.

Conclusion: Thus, by induction we are able to prove that an FBTNP $T$ having
$|V(T)|\leq(t+2)^{2}-9$ can be burnt in $t+1$ steps. Hence we get
$b(T)\leq\lceil\sqrt{n+9}\rceil-1$. $\square$

##  6 General Tree

We now extend our results to the more general tree. The $k$-ary tree is a
rooted tree, where each node can hold at most $k$ number of children. We
define a special type of $k$-ary tree, where each internal node can hold at
least $2$ children and at most $k$ children, we name this tree as $(3,k)$-ary
tree. Note that, Algorithm 5.2 works for this special kind of $k$-ary.

In 2018, Bessy et al. proved [3] that
$b(T)\leq\lceil\sqrt{n+n_{2}+1/4}+1/2\rceil$ for a tree $T$ where $n_{2}$ is
the number of degree $2$ vertices in $T$. Using Theorem 1.6, we improve this
bound for the trees having the number of vertices at least $50$. See 1.7

###### Proof

Let a tree $T$ of order $n$ has $n_{2}$ nodes of degree $2$. We add a pendent
vertex to each of $n_{2}-1$ nodes leaving out $1$ node as the root, thus
transforming $T$ to a $(3,k)$-ary $T^{\prime}$ of order $n+n_{2}-1$. We know
that Algorithm 5.2 works for $(3,k)$-ary tree. By Theorem 1.7 we can burn
$T^{\prime}$ in
$\lceil\sqrt{(n+n_{2}-1)+9}\rceil-1=\lceil\sqrt{n+n_{2}+8}\rceil-1$ steps.
$\square$

The burning number of a connected graph G equals the burning number of a
spanning tree of G; see [5]. Hence, we derive the following results for a
connected graph. As, $n_{2}\leq n-2$, thus a tree of order $n$ can be burnt in
$\lceil\sqrt{2n+6}\rceil-1$ steps which is an improvement over [3]. Also, when
$n_{2}\leq n/3$, then $b(T)\leq\lceil\sqrt{4n/3+8}\rceil-1$ which is an
improvement over [6] under the given condition.

##  7 Conclusion

To sum up, the burning number conjecture has been proved for the perfect
binary tree, complete binary tree, and FBTNP. For an FBTNP, an improved
algorithm has been given which in turn has improved the bound from the
original conjecture.

The burning number conjecture could also be studied for the other interesting
subclasses of trees.

## References

  * [1] Banerjee, S., Gopalan, A., Das, A.K., Shakkottai, S.: Epidemic spreading with external agents. IEEE Transactions on Information Theory 60(7), 4125–4138 (2014)
  * [2] Bessy, S., Bonato, A., Janssen, J., Rautenbach, D., Roshanbin, E.: Burning a graph is hard. Discrete Applied Mathematics 232, 73–87 (2017)
  * [3] Bessy, S., Bonato, A., Janssen, J., Rautenbach, D., Roshanbin, E.: Bounds on the burning number. Discrete Applied Mathematics 235, 16–22 (2018)
  * [4] Bonato, A., Janssen, J., Roshanbin, E.: Burning a graph as a model of social contagion. In: Algorithms and Models for the Web Graph: 11th International Workshop, WAW 2014, Beijing, China, December 17-18, 2014, Proceedings 11. pp. 13–22. Springer (2014)
  * [5] Bonato, A., Janssen, J., Roshanbin, E.: How to burn a graph. Internet Mathematics 12(1-2), 85–100 (2016)
  * [6] Bonato, A., Kamali, S.: An improved bound on the burning number of graphs. arXiv preprint arXiv:2110.01087 (2021)
  * [7] Bonato, A., Lidbetter, T.: Bounds on the burning numbers of spiders and path-forests. Theoretical Computer Science 794, 12–19 (2019)
  * [8] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction To Algorithms. Mit Electrical Engineering and Computer Science, MIT Press (2001)
  * [9] Das, S., Dev, S.R., Sadhukhan, A., Sahoo, U.K., Sen, S.: Burning spiders. In: Algorithms and Discrete Applied Mathematics: 4th International Conference, CALDAM 2018, Guwahati, India, February 15-17, 2018, Proceedings. pp. 155–163. Springer (2018)
  * [10] Domingos, P., Richardson, M.: Mining the network value of customers. In: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 57–66 (2001)
  * [11] Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 137–146 (2003)
  * [12] Kempe, D., Kleinberg, J., Tardos, É.: Influential nodes in a diffusion model for social networks. In: Automata, Languages and Programming: 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005. Proceedings 32. pp. 1127–1138. Springer (2005)
  * [13] Kramer, A.D., Guillory, J.E., Hancock, J.T.: Experimental evidence of massive-scale emotional contagion through social networks. Proceedings of the National academy of Sciences of the United States of America 111(24), 8788 (2014)
  * [14] Liu, H., Hu, X., Hu, X.: Burning number of caterpillars. Discrete Applied Mathematics 284, 332–340 (2020)
  * [15] Mossel, E., Roch, S.: On the submodularity of influence in social networks. In: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. pp. 128–134 (2007)
  * [16] Richardson, M., Domingos, P.: Mining knowledge-sharing sites for viral marketing. In: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 61–70 (2002)
  * [17] Tan, T.S., Teh, W.C.: Burnability of double spiders and path forests. Applied Mathematics and Computation 438, 127574 (2023)
  * [18] West, D.: Introduction to graph theory. 2nd edn. Pearson Education, London (2002)