Extremal inverse eigenvalue problem for irreducible acyclic matrices

ABSTRACT

In this paper, we study the inverse eigenvalue problem of constructing symmetric matrices whose graph is a tree, i.e. of constructing irreducible acyclic matrices from given eigendata consisting of the smallest and largest eigenvalues of their leading principal submatrices. We solve the problem completely for the case when the given eigenvalues are distinct and the subgraph of the tree induced by $\{1,2,\dots ,j\}$ remains connected for $1\le j\le n$. The result generalizes the results known for matrices described by some specific trees. The proofs of the main results are constructive and so provide an algorithm for computing the actual entries of the required matrix. Numerical solutions of the problem are then obtained with SCILAB by feeding the eigendata and plugging in the adjacency matrix as inputs. We also make an attempt to find the number of solutions for several special families of unlabelled trees.

KEYWORDS:

• Inverse eigenvalue problems
• trees
• acyclic matrices
• leading principal submatrices

MATHEMATICS SUBJECT CLASSIFICATIONS:

• 05C05
• 05C50
• 65F18

1. Introduction

An inverse eigenvalue problem (IEP) is the problem of reconstructing matrices of a pre-assigned structure which also satisfy the given constraints on eigenvalues and eigenvectors of the matrices or their submatrices. IEPs that require the construction of matrices having a pre-assigned pattern of zero entries are quite interesting. The pattern of zero entries of an $n\times n$ symmetric matrix determines the structure of the underlying graph on n vertices. It has been seen that the structure of the underlying graph has a considerable influence on the spectrum of the corresponding matrix. For example, the smallest and the largest eigenvalues of a symmetric matrix whose graph is a tree are always of algebraic multiplicity one [1]. Any modification like the deletion of a vertex or the deletion of a path applied to a graph creates a change in the eigen structure of the resulting matrix. Such relations between the structure of a graph and the eigen-structure of the corresponding matrix motivates the study of IEPs of constructing matrices described by graphs.

Peng et al. [2] and Pickman et al. [3,4] studied IEPs involving the construction of arrow matrices and doubly arrow matrices from given eigendata consisting of the smallest and the largest eigenvalues of each of the leading principal submatrices of the required matrix. Thereafter, several authors studied the problem for constructing matrices whose graphs are certain types of trees. Sharma and Sen [5] studied the IEP for constructing matrices described by brooms. The IEP with the same eigen data was also studied for special banded matrices by Xu and Chen [6] and for matrices of dense centipedes by Sharma and Sen [7]. This IEP was further studied by Heydari et al. [8]) for matrices of generalized stars. Several other authors have also come up for this extremal IEP in recent times with Zarch et al. [9] taking up the problem for banana trees, Zarch and Fazeli [10] for double-starlike trees or double comets and Sharma and Sen [11] for generalized star of depth 2. However, there has not been any general approach to the problem for constructing matrices described by any given tree. Inverse eigenvalue problems find applications in control theory, mass-spring vibrations, structural analysis, pole assignment problems and graph theory. A few references of such applications can be found in the works [12–15].

In this paper, we study the extremal inverse eigenvalue problem for a general tree, that is, the question of existence and construction of real matrices whose graph is a given tree, and whose leading principal submatrices have specified minimum and maximum eigenvalues. The problem was proposed by Sharma and Sen [11].

2. Preliminaries

Throughout this paper, the term graph will mean an undirected graph on the vertex set $V=\{1,\dots ,n\}$ without loops or multiple edges. Let $G_1$ and $G_2$ be two graphs on V. A permutation π of V is an isomorphism of $G_1$ onto $G_2$, if $\{i,j\}$ is an edge in $G_1$ if and only if $\left\{\pi \right(i),\pi (j\left)\right\}$ is an edge in $G_2$. If such a π exists, $G_1$ and $G_2$ are said to be isomorphic. If $G_1=G_2=G$, then the isomorphism π is called an automorphism of G. The set of automorphisms of G form a finite group, denoted by $\mathcal{A}ut\left(G\right)$.

If $G_1$ and $G_2$ are isomorphic graphs on the vertex set V, we say that $G_2$ is obtained from $G_1$ by relabelling the vertices. An unlabelled graph $\mathcal{G}$ is an equivalence class of isomorphic graphs, that is, the collection of all graphs obtained from any of its members by relabelling the vertices. A labelling of an unlabelled graph $\mathcal{G}$ means choosing a member of $\mathcal{G}$. An unlabelled tree is an unlabelled graph whose members are trees.

The adjacency matrix of a graph G is defined to be the $n\times n$ matrix $A\left(G\right)=\left(a_{ij}\right),$ with $a_{ij}=1$ if $\{i,j\}$ is an edge in G, and 0 otherwise. The matrix $A\left(G\right)$ completely determines the graph G. Two graphs $G_1$ and $G_2$ on the vertex set V are isomorphic if and only if their adjacency matrices are permutation similar. The automorphisms of a graph G are the permutations of the vertices for which the resulting relabellings of G also have the same adjacency matrix.

Given an $n\times n$ symmetric matrix A, the graph of A, denoted by $G\left(A\right)$, has vertex set V and edge set $E=\left\{\right\{i,j\}:i\ne j,a_{ij}\ne 0\}$. For a graph G with n vertices, $\mathcal{S}\left(G\right)$ denotes the set of all $n\times n$ symmetric matrices which have G as their graph. A symmetric matrix is said to be acyclic, if its graph does not have a cycle [16]. Thus, the graph of an irreducible acyclic matrix is a tree. For an $n\times n$ matrix A, we denote by $A_j$ the leading principal submatrix of A indexed by $\{1,2,\dots ,j\}$,  $1\le j\le n$. Clearly, if A is acyclic, then so is $A_j$ for each j.

For an $n\times n$ matrix $A=\left(a_{ij}\right)$, the determinant of A is defined as $detA=\sum _{\sigma }\left(\mathrm{s}\mathrm{g}\mathrm{n}\sigma \right)a_{1\sigma \left(1\right)}{a}_{2\sigma \left(2\right)}\cdots a_{n\sigma \left(n\right)},$ where the sum varies over all permutations σ of $\{1,\dots ,n\}$ and the sign of σ is + or − according as σ is even or odd [17]. It is well-known that every permutation is a product of disjoint cycles. Suppose A is symmetric and σ is a permutation of $\{1,\dots ,n\}$ such that $a_{1\sigma \left(1\right)}{a}_{2\sigma \left(2\right)}\cdots a_{n\sigma \left(n\right)}\ne 0$. If a cycle $(i_1,i_2,\dots ,i_r)$ of length r>2 appears as a factor in the product of disjoint cycles for σ, then $a_{i_k\sigma \left(i_k\right)}\ne 0$ for each k, and therefore the vertices $i_1,i_2,\dots ,i_r$ give rise to a cycle in $G\left(A\right)$. In other words, if A is acyclic, then the product $a_{1\sigma \left(1\right)}{a}_{2\sigma \left(2\right)}\cdots a_{n\sigma \left(n\right)}$ in the expression for $detA$ is nonzero only if σ is a product of disjoint two cycles.

3. IEP for a tree (IEPT)

We consider the following extremal inverse eigenvalue problem.

3.1. IEPT

Given a tree T on n vertices and 2n−1 real numbers ${\alpha }_j,{\text{β}}_j,1\le j\le n$, with ${\alpha }_1={\text{β}}_1$, find a matrix $A\in \mathcal{S}\left(T\right)$ such that ${\alpha }_j$ and ${\text{β}}_j$ are respectively the smallest and the largest eigenvalues of $A_j$.

The problem has been studied for some special matrices and trees by several authors [2–5,7–11]. We will discuss the problem for any given tree.

4. Solution of IEPT

We begin this section with the following result:

Lemma 4.1

[17,18] Cauchy's interlacing theorem

Let ${\lambda }_1\le {\lambda }_2\le \dots \le {\lambda }_n$ be the eigenvalues of an $n\times n$ real symmetric matrix A, and ${\mu }_1\le {\mu }_2\le \dots \le {\mu }_{n-1}$ be the eigenvalues of an $(n-1)\times (n-1)$ principal submatrix B of A, then ${\lambda }_1\le {\mu }_1\le {\lambda }_2\le {\mu }_2\le \cdots \le {\lambda }_{n-1}\le {\mu }_{n-1}\le {\lambda }_n.$

The theorem says in particular that the eigenvalues of an $n\times n$ irreducible acyclic matrix and those of any of its $(n-1)\times (n-1)$ principal submatrices interlace each other.

Lemma 4.2

A necessary condition for the IEPT to have a solution is ${\alpha }_n\le {\alpha }_{n-1}\le \cdots \le {\alpha }_2\le {\alpha }_1={\text{β}}_1\le {\text{β}}_2\le \cdots \le {\text{β}}_{n-1}\le {\text{β}}_n.$

Proof.

It follows from a repeated application of Lemma 4.1.

Lemma 4.3

If ${\alpha }_i\ne {\alpha }_j$ and ${\text{β}}_i\ne {\text{β}}_j$ for all $i\ne j$ in $\{1,\dots ,n\}$, then the IEPT has a solution only if the vertices of T are labelled such that for each $j\in \{1,\dots ,n\}$, the subgraph $T_j$ of T induced by the vertices $\{1,\dots ,j\}$ is connected.

Proof.

Let T be labelled such that for some $j\in \{1,\dots ,n\}$ the induced subgraph $T_j$ is disconnected. So, there exists $i\in \{1,\dots ,j-1\}$ such that $T_i$ is connected but $T_{i+1}$ is disconnected. Clearly, the vertex i + 1 in the induced subgraph $T_{i+1}$ is an isolated vertex. Let $A\in \mathcal{S}\left(T\right)$. Then, the eigenvalues of $A_{i+1}$ are same as those of $A_i$ together with another eigenvalue $a_{i+1,i+1}$ that is precisely the diagonal entry corresponding to the vertex i + 1. So, $A_{i+1}$ has at most one eigenvalue different from those of $A_i$. However, the smallest and the largest eigenvalues of $A_i$ are ${\alpha }_i$ and ${\text{β}}_i$ and those of $A_{i+1}$ are ${\alpha }_{i+1}$ and ${\text{β}}_{i+1}$. Since it is given that ${\alpha }_i\ne {\alpha }_{i+1}$ and ${\text{β}}_i\ne {\text{β}}_{i+1}$, so we get that $A_{i+1}$ has two eigenvalues different from those of $A_i$, and we have a contradiction. Hence, no matrix in $\mathcal{S}\left(T\right)$ can be a solution of IEPT.

It is easy to see that the vertices of a tree can be labelled satisfying the condition in Lemma 4.3. Let $\mathcal{T}$ be an unlabelled tree and $T_0$ be any tree in $\mathcal{T}$. We can relabel the vertices to obtain T in $\mathcal{T}$ such that for every $j\in \{1\dots ,n\}$, the subgraph $T_j$ of T induced by the vertices $\{1,2,\dots ,j\}$ is also a tree. We start with any vertex $v_1$ of $T_0$ and relabel it as 1. Since the induced subgraph of T corresponding to the vertex set $\{1,2\}$ has to be a tree, so the vertex 2 in T should be adjacent to 1. Thus, we select a vertex $v_2$ in $T_0$ adjacent to $v_1$ and relabel it as 2. In each subsequent step, we relabel a vertex $v_j$ that is adjacent to one of the vertices that have already been relabelled as j, maintaining the serial number of the new labels in the natural order. We continue this process till all the vertices of T are labelled from 1 to n. Clearly, the tree T thus obtained has the property that the subgraph of T induced by $\{1,2,\dots ,j\}$ for $1\le j\le n$ is connected. In this paper, we refer to such labelling of a tree as a successively connected labelling. The following figure depicts a successively connected labelling of a tree Figure 1.

Figure 1. A successively connected labelling of a tree.

In Lemma 4.3, we have seen that if the given eigenvalues are distinct, then the IEPT has a solution only if the given tree has successively connected labelling. We shall also show (Lemma 4.6) that if the given tree has successively connected labelling, then the IEPT has a solution only if the given eigenvalues are distinct. We need a few more results before that.

Lemma 4.4

Let $P\left(x\right)$ be a monic polynomial of degree n with all real zeros and ${\lambda }_{min}$ and ${\lambda }_{max}$ be the smallest and largest zeros of P, respectively.

(i)	If $\mu <{\lambda }_{min}$, then $(-1{)}^{n}P(\mu )>0$.
(ii)	If $\mu >{\lambda }_{max}$, then $P\left(\mu \right)>0$.
(iii)	If $P\left(\mu \right)<0$, then $\mu <{\lambda }_{max}$.

Proof.

Follows by expressing $P\left(x\right)$ as the product of its linear factors.

We provide a simple proof of the following strict interlacing of the extreme eigenvalues of matrices in $\mathcal{S}\left(T\right)$ and their principal submatrices, using Lemma 4.4.

Lemma 4.5

Let A be an $n\times n$ real symmetric matrix such that $G\left(A\right)$ is a tree, and B be a $k\times k$ principal submatrix of A, k<n. Let α and β be the largest eigenvalues of A and B, and γ and δ be the smallest eigenvalues of A and B, respectively. Then $\gamma <\delta \le \text{β}<\alpha .$

Proof.

We prove by induction on n that $\text{β}<\alpha$. Then, it will follow that $\gamma <\delta$ by comparing the largest eigenvalues of $-A$ and $-B$, since $G(-A)=T$.

If n = 2, then $G\left(A\right)$ is a path on two vertices. So, $A=\left(\begin{array}{cc}{a}_1& b_{12}\\ b_{12}& a_2\end{array}\right)$ with $b_{12}\ne 0$. The only $1\times 1$ principal submatrices of A are $\left(a_1\right)$ and $\left(a_2\right)$. By Lemma 4.1, $\alpha \ge max\{a_1,a_2\}\ge \text{β}$. The characteristic polynomial of A is $P\left(x\right)=(x-a_1)(x-a_2)-b_{12}^2$. Since $P\left(a_1\right)<0,P\left(a_2\right)<0$, by (iii) of Lemma 4.4, $\alpha >max\{a_1,a_2\}\ge \text{β}$.

Assume that $n\ge 3$ and that the result holds for all symmetric matrices of order less than n whose graphs are trees. Let A be an $n\times n$ real symmetric matrix such that $G\left(A\right)=T$ and B be the principal submatrix of A.

Putting $\tilde{A}=xI-A=\left({\tilde{a}}_{ij}\right)$, the characteristic polynomial of A can be written as $P_A\left(x\right)=det\tilde{A}=\sum _{\sigma }\left(\mathrm{s}\mathrm{g}\mathrm{n}\sigma \right){\tilde{a}}_{1\sigma \left(1\right)}\cdots {\tilde{a}}_{n\sigma \left(n\right)},$ where the sum varies over all permutations σ of $\{1,\dots ,n\}$. Since A is acyclic, the product ${\tilde{a}}_{1\sigma \left(1\right)}\cdots {\tilde{a}}_{n\sigma \left(n\right)}$ is non-zero only if σ is a product of disjoint two-cycles. For $i,j\in V=\{1,\dots ,n\}$ let $A_i$ and $A_{ij}$ denote the principal submatrices of A indexed by $V\setminus \left\{i\right\}$ and $V\setminus \{i,j\}$, respectively. Then, we have $P_A\left(x\right)=\sum _{\sigma \left(i\right)=i}\left(\mathrm{s}\mathrm{g}\mathrm{n}\sigma \right){\tilde{a}}_{1\sigma \left(1\right)}\cdots {\tilde{a}}_{n\sigma \left(n\right)}+\sum _{\sigma \left(i\right)\ne i}\left(\mathrm{s}\mathrm{g}\mathrm{n}\sigma \right){\tilde{a}}_{1\sigma \left(1\right)}\cdots {\tilde{a}}_{n\sigma \left(n\right)}$

For permutations σ with $\sigma \left(i\right)=i$, the sign of σ restricted to $V\setminus \left\{i\right\}$ is same as that of σ. Also for $\sigma \left(i\right)\ne i$, $a_{i\sigma \left(i\right)}\ne 0$ iff $\sigma \left(i\right)\sim i$, that is the vertex $\sigma \left(i\right)$ is adjacent to i. The sign of σ restricted to $V\setminus \{i,j\}$, where $j\sim i$, is opposite to that of σ as only the two cycle $(i,j)$ gets removed from the product of disjoint two cycles. Thus, we have (1) $\begin{array}{rl}{P}_A\left(x\right)& ={\tilde{a}}_{ii}{P}_{A_i}\left(x\right)-\sum _{j\sim i}{\tilde{a}}_{ij}{\tilde{a}}_{ji}{P}_{A_{ij}}\left(x\right)\\ & =(x-a_{ii})P_{A_i}\left(x\right)-\sum _{j\sim i}{a}_{ij}^2{P}_{A_{ij}}\left(x\right),\end{array}$(1)

Now, let η be the largest eigenvalue of $A_i$. Since each connected component of $G\left(A_{ij}\right)$ is a subtree of $G\left(A_i\right)$, by induction hypothesis and in view of Lemma 4.4(ii), we get $P_{A_{ij}}\left(\eta \right)>0$ for each $j\sim i$. Consequently, (1(1) $\begin{array}{rl}{P}_A\left(x\right)& ={\tilde{a}}_{ii}{P}_{A_i}\left(x\right)-\sum _{j\sim i}{\tilde{a}}_{ij}{\tilde{a}}_{ji}{P}_{A_{ij}}\left(x\right)\\ & =(x-a_{ii})P_{A_i}\left(x\right)-\sum _{j\sim i}{a}_{ij}^2{P}_{A_{ij}}\left(x\right),\end{array}$(1) ) yields $P_A\left(\eta \right)<0$. Therefore, by Lemma 4.4(iii), we get $\eta <\alpha$. Thus, we have proved the result for the case when $B=A_i$. For any other B the argument can be repeated. This completes the proof.

We are now ready to give a necessary condition for existence of solution for the IEPT in the case of trees with successively connected labelling.

Lemma 4.6

Let T be a tree with successively connected labelling. If the IEPT has a solution, then ${\alpha }_n<{\alpha }_{n-1}<\cdots <{\alpha }_2<{\alpha }_1={\text{β}}_1<{\text{β}}_2<\cdots <{\text{β}}_{n-1}<{\text{β}}_n.$

Proof.

Suppose $A\in \mathcal{S}\left(T\right)$ be such that ${\alpha }_j$ and ${\text{β}}_j$ are the smallest and the largest eigenvalues of $A_j$ for $j=1,\dots ,n$. Since $A_{j-1}$ is a principal submatrix of the matrix $A_j$ whose graph is a tree, so by Lemma 4.5, we have ${\alpha }_j<{\alpha }_{j-1}\mathrm{a}\mathrm{n}\mathrm{d}{\text{β}}_{j-1}<{\text{β}}_j\mathrm{f}\mathrm{o}\mathrm{r}j=2,\dots ,n.$

It follows that ${\alpha }_n<{\alpha }_{n-1}<\cdots <{\alpha }_2<{\alpha }_1={\text{β}}_1<{\text{β}}_2<\cdots <{\text{β}}_{n-1}<{\text{β}}_n.$

Lemma 4.7

Let A be a real symmetric matrix and ${\alpha }_n<{\alpha }_{n-1}<\cdots <{\alpha }_2<{\alpha }_1={\text{β}}_1<{\text{β}}_2<\cdots <{\text{β}}_{n-1}<{\text{β}}_n$ such that ${\alpha }_j$ and ${\text{β}}_j$ are eigenvalues of $A_j$ for each j. Then, ${\alpha }_j$ is the smallest eigenvalue and ${\text{β}}_j$ is the largest eigenvalue of $A_j$, $j=1,2,\dots ,n$.

Proof.

Follows from Cauchy's interlacing theorem.

For the rest of this section, T will denote a tree on the vertex set $\{1,\dots ,n\}$ with successively connected labelling. We shall show that the necessary condition in Lemma 4.3 is also a sufficient condition for a solution of the IEPT for trees with successively connected labelling.

We now adopt some notations for the entries of a matrix $A\in \mathcal{S}\left(T\right)$. For a successively connected labelling, it is easy to see that for $1\le j\le n$, the vertex j is pendent in the subtree $T_j$ of T induced by $\{1,\dots ,j\}$. Let $j\ge 2$. Since $T_j$ is connected, degree of j is non-zero. Suppose $p,q\in \{1,\dots ,j-1\}$ are adjacent to j. If $p\ne q$, then the unique p-q path in $T_{j-1}$ along with the edges $\{j,p\}$ and $\{q,j\}$ produces a cycle in $T_j$, contradicting that $T_j$ is a tree. Thus, j is of degree 1 in $T_j$. This allows us to define a function $v:\{2,\dots ,n\}\to \{1,\dots ,n-1\}$ given by $v\left(j\right)=$ the unique vertex among $1,\dots ,j-1$ that is adjacent to j. Thus, for each $j=1,\dots ,n$, the only non-zero off-diagonal entry in the jth column of $j\times j$ leading principal submatrix $A_j$ of any matrix $A\in \mathcal{S}\left(T\right)$ is in the $v\left(j\right)$th row and the only non-zero off-diagonal entry in the jth row of $A_j$ is in the $v\left(j\right)$th column.

The diagonal entries of A are taken to be $a_j$ and the off-diagonal entries $b_{ij},i,j\in \{1,\dots ,n\}$. Since A is symmetric, $b_{ij}=b_{ji}$ for all i and j. Moreover, it follows from the above discussion that in each leading principal submatrix $A_j$, $b_{ij}\ne 0$ if and only if $i=v\left(j\right)$. Let $P_j\left(x\right)$ denote the characteristic polynomial of $A_j$, $j=1,\dots ,n$. Further, for $j\ge 3$, let $Q_j\left(x\right)$ denote the characteristic polynomial of the principal submatrix of $A_j$ obtained by deleting the rows and the columns indexed by j and $v\left(j\right)$. We put $Q_2\left(x\right)=1$. Then, we have the following result.

Lemma 4.8

The characteristic polynomials $P_j\left(x\right)$ of $A_j$ satisfy the following recurrence relation:

(i)	$P_1\left(x\right)=x-a_1$;
(ii)	$P_j\left(x\right)=(x-a_j)P_{j-1}\left(x\right)-b_{jv\left(j\right)}^2{Q}_j\left(x\right)$, $j=2,\dots ,n$.

Proof.

Clearly, (i) holds. Moreover, $P_2\left(x\right)=(x-a_1)(x-a_2)-b_{12}^2=(x-a_2)P_1\left(x\right)-b_{2v\left(2\right)}^2{Q}_2\left(x\right).$

Now, let $j\ge 3$. In view of (1(1) $\begin{array}{rl}{P}_A\left(x\right)& ={\tilde{a}}_{ii}{P}_{A_i}\left(x\right)-\sum _{j\sim i}{\tilde{a}}_{ij}{\tilde{a}}_{ji}{P}_{A_{ij}}\left(x\right)\\ & =(x-a_{ii})P_{A_i}\left(x\right)-\sum _{j\sim i}{a}_{ij}^2{P}_{A_{ij}}\left(x\right),\end{array}$(1) ) we have (2) $P_j\left(x\right)=(x-a_j)P_{j-1}\left(x\right)-\sum _{\begin{array}{c}j\sim i\\ 1\le i\le j-1\end{array}}{b}_{ij}^2{P}_{A_{ij}}\left(x\right),$(2) where $A_{ij}$ is the principal submatrix of A induced by $\{1,\dots ,j\}\setminus \{i,j\}$. Now, by our choice of the labelling of the vertices, the only i in $\{1,\dots ,j\}$ that is adjacent to j is $v\left(j\right)$. Moreover, $P_{A_{jv\left(j\right)}}\left(x\right)=Q_j\left(x\right)$. Hence, (2(2) $P_j\left(x\right)=(x-a_j)P_{j-1}\left(x\right)-\sum _{\begin{array}{c}j\sim i\\ 1\le i\le j-1\end{array}}{b}_{ij}^2{P}_{A_{ij}}\left(x\right),$(2) ) reduces to $P_j\left(x\right)=(x-a_j)P_{j-1}\left(x\right)-b_{jv\left(j\right)}^2{Q}_j\left(x\right).$

We therefore have the recurrence relation.

Now, for any $A\in \mathcal{S}\left(T\right)$ and for $j=1,2,\dots ,n$ let ${\alpha }_j$ and ${\text{β}}_j$ be the smallest and the largest eigenvalues of $A_j$, respectively. Then, $P_j\left({\alpha }_j\right)=0\mathrm{a}\mathrm{n}\mathrm{d}{P}_j\left({\text{β}}_j\right)=0.$

From Lemma 4.8 we get $a_1={\alpha }_1$, and for $j\ge 2$ (3) $\begin{array}{l}{a}_j{P}_{j-1}\left({\alpha }_j\right)+b_{jv\left(j\right)}^2{Q}_j\left({\alpha }_j\right)-{\alpha }_j{P}_{j-1}\left({\alpha }_j\right)=0\\ a_j{P}_{j-1}\left({\text{β}}_j\right)+b_{jv\left(j\right)}^2{Q}_j\left({\text{β}}_j\right)-{\text{β}}_j{P}_{j-1}\left({\text{β}}_j\right)=0.\end{array}\}$(3)

Thus, studying the IEPT for solutions is equivalent to seeking for appropriate solutions for the system of linear Equations (3(3) $\begin{array}{l}{a}_j{P}_{j-1}\left({\alpha }_j\right)+b_{jv\left(j\right)}^2{Q}_j\left({\alpha }_j\right)-{\alpha }_j{P}_{j-1}\left({\alpha }_j\right)=0\\ a_j{P}_{j-1}\left({\text{β}}_j\right)+b_{jv\left(j\right)}^2{Q}_j\left({\text{β}}_j\right)-{\text{β}}_j{P}_{j-1}\left({\text{β}}_j\right)=0.\end{array}\}$(3) ) for $a_j$ and positive $b_{jv\left(j\right)}^2$. Let $D_j$ be the determinant of the coefficient matrix of the system (3(3) $\begin{array}{l}{a}_j{P}_{j-1}\left({\alpha }_j\right)+b_{jv\left(j\right)}^2{Q}_j\left({\alpha }_j\right)-{\alpha }_j{P}_{j-1}\left({\alpha }_j\right)=0\\ a_j{P}_{j-1}\left({\text{β}}_j\right)+b_{jv\left(j\right)}^2{Q}_j\left({\text{β}}_j\right)-{\text{β}}_j{P}_{j-1}\left({\text{β}}_j\right)=0.\end{array}\}$(3) ), i.e. (4) $D_j=P_{j-1}\left({\alpha }_j\right)Q_j\left({\text{β}}_j\right)-P_{j-1}\left({\text{β}}_j\right)Q_j\left({\alpha }_j\right).$(4)

Lemma 4.9

Given a tree T with successively connected labelling and 2n−1 real numbers satisfying ${\alpha }_n<{\alpha }_{n-1}<\cdots <{\alpha }_2<{\alpha }_1={\text{β}}_1<{\text{β}}_2<\cdots <{\text{β}}_{n-1}<{\text{β}}_n$ there is a unique solution $A\in \mathcal{S}\left(T\right)$ of the IEPT with positive off-diagonal entries.

Proof.

We show that the systems of Equations (3(3) $\begin{array}{l}{a}_j{P}_{j-1}\left({\alpha }_j\right)+b_{jv\left(j\right)}^2{Q}_j\left({\alpha }_j\right)-{\alpha }_j{P}_{j-1}\left({\alpha }_j\right)=0\\ a_j{P}_{j-1}\left({\text{β}}_j\right)+b_{jv\left(j\right)}^2{Q}_j\left({\text{β}}_j\right)-{\text{β}}_j{P}_{j-1}\left({\text{β}}_j\right)=0.\end{array}\}$(3) ) can recursively be solved uniquely for real $a_j$ and positive $b_{jv\left(j\right)}^2$. We put $a_1={\alpha }_1$, yielding $P_1\left(x\right)=x-{\alpha }_1$. Since $Q_2\left(x\right)=1$, for j = 2 the system becomes $\begin{array}{rl}& a_2({\alpha }_2-{\alpha }_1)+b_{12}^2-{\alpha }_2({\alpha }_2-{\alpha }_1)=0\\ & a_2({\text{β}}_2-{\alpha }_1)+b_{12}^2-{\text{β}}_2({\text{β}}_2-{\alpha }_1)=0,\end{array}$ which has unique solution $a_2={\alpha }_2+{\text{β}}_2-{\alpha }_1$,  $b_{12}^2=({\alpha }_1-{\alpha }_2)({\text{β}}_2-{\alpha }_1)>0$.

Now let $j\ge 3$ and assume that we have obtained $a_k$ and $b_{kv\left(k\right)}^2>0$ for $1\le k\le j-1$ so that the matrix $A_{j-1}$ and the polynomials $P_{j-1}\left(x\right)$ and $Q_j\left(x\right)$ are determined. Since ${\alpha }_{j-1}$ and ${\text{β}}_{j-1}$ are the smallest and the largest eigenvalues of the polynomial $P_{j-1}\left(x\right)$ of degree j−1, and because ${\alpha }_j<{\alpha }_{j-1}$ and ${\text{β}}_{j-1}<{\text{β}}_j$, in view of Lemma 4.4 we have (5) $(-1{)}^{j-1}{P}_{j-1}({\alpha }_j)>0\text{and}{P}_{j-1}({\text{β}}_j)>0.$(5)

Let ${\gamma }_j$ and ${\delta }_j$ be the smallest and the largest zeros of the polynomial $Q_j\left(x\right)$ which is of degree j−2. Then, by Lemma 4.1, ${\alpha }_j<{\alpha }_{j-1}\le {\gamma }_j$ and ${\delta }_j\le {\text{β}}_{j-1}<{\text{β}}_j$. Therefore, Lemma 4.4 gives (6) $(-1{)}^{j-2}{Q}_j({\alpha }_j)>0\text{and}{Q}_j({\text{β}}_j)>0.$(6)

Consequently, from Equation (4(4) $D_j=P_{j-1}\left({\alpha }_j\right)Q_j\left({\text{β}}_j\right)-P_{j-1}\left({\text{β}}_j\right)Q_j\left({\alpha }_j\right).$(4) ), we have (7) $(-1{)}^{j-1}{D}_j=((-1{)}^{j-1}{P}_{j-1}\left({\alpha }_j\right))Q_j\left({\text{β}}_j\right)+P_{j-1}\left({\text{β}}_j\right)((-1{)}^{j-2}{Q}_j({\alpha }_j))>0.$(7)

In particular, $D_j\ne 0$ and therefore the system (3(3) $\begin{array}{l}{a}_j{P}_{j-1}\left({\alpha }_j\right)+b_{jv\left(j\right)}^2{Q}_j\left({\alpha }_j\right)-{\alpha }_j{P}_{j-1}\left({\alpha }_j\right)=0\\ a_j{P}_{j-1}\left({\text{β}}_j\right)+b_{jv\left(j\right)}^2{Q}_j\left({\text{β}}_j\right)-{\text{β}}_j{P}_{j-1}\left({\text{β}}_j\right)=0.\end{array}\}$(3) ) has a unique solution for $a_j$ and $b_{jv\left(j\right)}^2$ given by (8) $\begin{array}{rl}{a}_j& ={\displaystyle \frac{{\alpha }_j{P}_{j-1}\left({\alpha }_j\right)Q_j\left({\text{β}}_j\right)-{\text{β}}_j{P}_{j-1}\left({\text{β}}_j\right)Q_j\left({\alpha }_j\right)}{D_j}}\\ b_{jv\left(j\right)}^2& ={\displaystyle \frac{({\text{β}}_j-{\alpha }_j)P_{j-1}\left({\alpha }_j\right)P_{j-1}\left({\text{β}}_j\right)}{D_j}}.\end{array}$(8)

Further, from (5(5) $(-1{)}^{j-1}{P}_{j-1}({\alpha }_j)>0\text{and}{P}_{j-1}({\text{β}}_j)>0.$(5) ), (6(6) $(-1{)}^{j-2}{Q}_j({\alpha }_j)>0\text{and}{Q}_j({\text{β}}_j)>0.$(6) ) and (7(7) $(-1{)}^{j-1}{D}_j=((-1{)}^{j-1}{P}_{j-1}\left({\alpha }_j\right))Q_j\left({\text{β}}_j\right)+P_{j-1}\left({\text{β}}_j\right)((-1{)}^{j-2}{Q}_j({\alpha }_j))>0.$(7) ), we get $b_{jv\left(j\right)}^2={\displaystyle \frac{({\text{β}}_j-{\alpha }_j)((-1{)}^{j-1}{P}_{j-1}({\alpha }_j\left))P_{j-1}\right({\text{β}}_j)}{(-1{)}^{j-1}{D}_j}}>0,$ since ${\alpha }_j<{\text{β}}_j$. Taking $b_{jv\left(j\right)}$ as the positive square root of values obtained for $b_{jv\left(j\right)}^2$ we get the unique solution we are seeking for.

Combining Lemmas 4.6 and 4.9 we get a complete answer for the IEPT for trees with successively connected labelling.

Theorem 4.10

Let T be a tree with successively connected labelling. Then, the IEPT has a solution if and only if (9) ${\alpha }_n<{\alpha }_{n-1}<\cdots <{\alpha }_2<{\alpha }_1={\text{β}}_1<{\text{β}}_2<\cdots <{\text{β}}_{n-1}<{\text{β}}_n.$(9)

Further, in that case, there is a unique solution $A\in \mathcal{S}\left(T\right)$ with positive off-diagonal entries. Any other solution differs from A only by signs of some off-diagonal entries.

Remark 4.1

We refer the solution A to the IEPT that has positive off-diagonal entries as the dominant solution. Since T has n−1 edges, a matrix in $\mathcal{S}\left(T\right)$ has n−1 pairs of equal off-diagonal entries. Thus, the IEPT has $2^{n-1}$ distinct solutions in $\mathcal{S}\left(T\right)$, obtained by choosing different signs for the off-diagonal entries.

Provided the inequality (9(9) ${\alpha }_n<{\alpha }_{n-1}<\cdots <{\alpha }_2<{\alpha }_1={\text{β}}_1<{\text{β}}_2<\cdots <{\text{β}}_{n-1}<{\text{β}}_n.$(9) ) holds, the procedures in the proof of Theorem 4.9 can be coded as a computer program which takes the eigendata and adjacency matrix (or the function $j\mapsto v\left(j\right)$) as inputs and gives the required matrix A as output. We have coded this in SCILAB 5.5.2.

5. Numerical examples

In this section, we take up some specific examples which appeared in the papers [5,7–10]. We solve them using our program and find the dominant solution in each case. The values of the entries are given correct to 5 places of decimal.

Example 5.1

Consider the unlabelled tree $B_{4,3}$ (a broom on seven vertices) obtained by attaching three pendent vertices to one of the endpoints of a path with four vertices. Consider 13 real numbers $-6,-4.4,-3.8,-2,-1.4,0.5,1,2,3,4.7,5,6,7.$

The tree $T_1$ of $B_{4,3}$ labelled as in Figure 2 was considered in [5]. It is a successively connected labelling and the function v has the values $v\left(2\right)=1,v\left(3\right)=2,v\left(4\right)=3,v\left(5\right)=4,v\left(6\right)=4,v\left(7\right)=4$. As obtained in [5], we find the dominant solution as $A=\left(\begin{array}{ccccccc}1.00000& 0.70711& 0& 0& 0& 0& 0\\ 0.70711& 1.50000& 1.93799& 0& 0& 0& 0\\ 0& 1.93799& -0.00465& 2.15801& 0& 0& 0\\ 0& 0& 2.15801& 3.36148& 1.89908& 3.18842& 3.72473\\ 0& 0& 0& 1.89908& -3.16120& 0& 0\\ 0& 0& 0& 3.18842& 0& -1.58226& 0\\ 0& 0& 0& 3.72473& 0& 0& -3.19246\end{array}\right).$

Figure 2. Two labellings of the broom.

On the other hand, for the labelling $T_2$ of $B_{4,3}$ (see Figure 2), the function v takes values $v\left(2\right)=1,v\left(3\right)=1,v\left(4\right)=2,v\left(5\right)=v\left(6\right)=v\left(7\right)=3$. With this new v as input, the dominant solution obtained is $A^{\prime }=\left(\begin{array}{ccccccc}1.00000& 0.70711& 2.04812& 0& 0& 0& 0\\ 0.70711& 1.50000& 0& 3.20484& 0& 0& 0\\ 2.04812& 0& 0.48312& 0& 3.81892& 2.72839& 3.86854\\ 0& 3.20484& 0& 1.29356& 0& 0& 0\\ 0& 0& 3.81892& 0& 0.51410& 0& 0\\ 0& 0& 2.72839& 0& 0& 2.24341& 0\\ 0& 0& 3.86854& 0& 0& 0& -0.52783\end{array}\right).$

Note that, although the adjacency matrices of $T_1$ and $T_2$ are permutation similar, the solutions A and $A^{\prime }$ to the two IEPT with same set of eigendata are not permutation similar.

Example 5.2

Consider the tree $T=C(3,5,4)$ with 12 vertices in Figure 3, known as a centipede. The IEPT with the 23 real numbers $\begin{array}{rl}& -11.2,-10.5,-9.1,-8,-7.2,-6.3,-5.2,-4,-3,-2.8,-1.2,\\ & 0,1,2.5,3,4.7,5.8,6.4,7,8,9,11,14\end{array}$ was considered in [7]. The function v takes values $v\left(2\right)=v\left(3\right)=v\left(4\right)=1,v\left(5\right)=v\left(6\right)=v\left(7\right)=v\left(8\right)=v\left(9\right)=4,v\left(10\right)=v\left(11\right)=v\left(12\right)=9$. With these values as inputs, we get the resulting dominant solution as $\begin{array}{rl}& (\begin{array}{cccccc}0& 1.09545& 2.40789& 1.29251& 0& 0\\ 1.09545& -0.20000& 0& 0& 0& 0\\ 2.40789& 0& -0.32062& 0& 0& 0\\ 1.29251& 0& 0& 1.09937& 3.95804& 3.42502\\ 0& 0& 0& 3.95804& -0.36267& 0\\ 0& 0& 0& 3.42502& 0& -0.71897\\ 0& 0& 0& 3.00673& 0& 0\\ 0& 0& 0& 3.10344& 0& 0\\ 0& 0& 0& 3.73695& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\\ & \begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 3.00673& 3.10344& 3.73695& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ -2.42578& 0& 0& 0& 0& 0\\ 0& -2.46585& 0& 0& 0& 0\\ 0& 0& -0.40720& 6.80131& 6.58352& 5.47470\\ 0& 0& 6.80131& -0.20582& 0& 0\\ 0& 0& 6.58352& 0& 2.22715& 0\\ 0& 0& 5.47470& 0& 0& 9.03577\end{array})\end{array}$ which is the same as obtained in [7].

Figure 3. A Labelling of the centipede C(3,5,4).

Example 5.3

Consider the generalized star T with 9 vertices shown in Figure 4. The tree with the eigendata $-60,-13,-8.83,-7.43,-2.7,0.23,2,3.6,4,5.3,10,11.43,12,14.5,15.64,21,45$ was considered in [8]. The labelling is successively connected and the function v takes values $v\left(2\right)=v\left(5\right)=v\left(7\right)=1,v\left(3\right)=2,v\left(4\right)=3,v\left(6\right)=5,v\left(8\right)=7,v\left(9\right)=8$. By our program we obtain the solution as $\begin{array}{rl}A& =(\begin{array}{ccccc}4.00000& 0.72111& 0& 0& 7.24597\\ 0.72111& 4.90000& 3.71950& 0& 0\\ 0& 3.71950& 7.24042& 3.88790& 0\\ 0& 0& 3.88790& 4.04923& 0\\ 7.24597& 0& 0& 0& 5.24265\\ 0& 0& 0& 0& 7.79528\\ 7.24283& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}\\ & \begin{array}{cccc}0& 7.24283& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 7.79528& 0& 0& 0\\ 0.10873& 0& 0& 0\\ 0& 0.58485& 14.33160& 0\\ 0& 14.33160& 8.43147& 47.35109\\ 0& 0& 47.35109& -25.50266\end{array})\end{array}$ which is the same as in [8].

Figure 4. A labelling of GS(3,2,3).

Example 5.4

Consider the tree T (called the banana tree $B(2,4)$) with 9 vertices shown in Figure 5. The tree with the eigendata $-7,-6.1,-5,-3.6,-2.5,-1,-0.5,1.5,2,2.5,3,4,5.3,6,7,8,9.2$ was considered in [9]. The labelling is successively connected and the function v takes the values $v\left(2\right)=v\left(6\right)=1,v\left(3\right)=2,v\left(4\right)=v\left(5\right)=3,v\left(7\right)=6,v\left(8\right)=v\left(9\right)=7$. Plugging v and the eigendata into our program we get the dominant solution as $\begin{array}{rl}A& =(\begin{array}{ccccc}2.00000& 0.50000& 0& 0& 0\\ 0.50000& 2.00000& 1.41421& 0& 0\\ 0& 1.41421& 0.33333& 1.61009& 3.05871\\ 0& 0& 1.61009& 3.00293& 0\\ 0& 0& 3.05871& 0& 2.39252\\ 4.69518& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}\\ & \begin{array}{cccc}4.69518& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0.37522& 3.62258& 0& 0\\ 3.62258& 0.94213& 5.05338& 4.43126\\ 0& 5.05338& 1.12229& 0\\ 0& 4.43126& 0& 2.22016\end{array})\end{array}$ which is same as that obtained in [9].

Figure 5. A labelling of B(2,4).

Example 5.5

Consider the tree $T=G(3,4,2)$ with 9 vertices shown in Figure 6. The tree with the eigendata $-14,-11,-9.2,-7,-5,-2,-1,1,2,6,7,8.1,10,12,14,15.3,17$ was considered in [10]. The function v takes values $v\left(2\right)=v\left(3\right)=v\left(4\right)=v\left(5\right)=1$, $v\left(6\right)=5,v\left(7\right)=6,v\left(8\right)=v\left(9\right)=7$. Plugging v and the eigendata into our program, we get the dominant solution as $\begin{array}{rl}A& =(\begin{array}{ccccc}2.00000& 2.00000& 3.24037& 3.09581& 5.54970\\ 2.00000& 5.00000& 0& 0& 0\\ 3.24037& 0& 3.50000& 0& 0\\ 3.09581& 0& 0& 4.30745& 0\\ 5.54970& 0& 0& 0& 2.10480\\ 0& 0& 0& 0& 6.88313\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}\\ & \begin{array}{cccc}0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 6.88313& 0& 0& 0\\ 3.32599& 8.22571& 0& 0\\ 8.22571& 1.02082& 8.21818& 8.96849\\ 0& 8.21818& 2.25175& 0\\ 0& 8.96849& 0& -0.62174\end{array})\end{array}$ which is same as that obtained in [10].

Figure 6. Labelling of the vertices of $G(3,4,2)$.

6. Number of dominant solutions for an unlabelled tree

Let $\mathcal{T}$ be an unlabelled tree with n vertices. For each successively connected labelling of $\mathcal{T}$, we have a dominant solution of the corresponding IEPT. In this section, we discuss the number of dominant solutions that can be obtained from different successively connected labellings of $\mathcal{T}$.

For $T\in \mathcal{T}$ let us denote by $\ell \left(T\right)$ the number of successively connected relabellings of T. We note that the dominant solution A obtained in Section 4 for a successively connected relabelling $T_0$ of T is completely determined by the adjacency matrix of $T_0$. For any two successively connected relabellings of T, the dominant solutions coincide if and only if the corresponding adjacency matrices are identical. Therefore, the number of successively connected relabellings of T giving rise to the same dominant solution A is $|\mathcal{A}ut\left(T\right)|$, the number of automorphisms of T. Consequently, the number of dominant solutions obtained from different labellings of $\mathcal{T}$ is $\frac{\ell \left(T\right)}{|\mathcal{A}ut\left(T\right)|}$.

Remark 6.1

As mentioned in Example 5.1, in all cases we have examined (including all trees with at most five vertices), we found that the dominant solutions for two labellings of an unlabelled tree whose adjacency matrices are different are not permutation similar. However, we are not sure whether this is the case in general.

Now, we need to determine the number of ways of relabelling the vertices $\{1,\dots ,n\}$ of T such that for each $j=1,2,\dots ,n$, the subgraph induced by $\{1,2,\dots ,j\}$ is a tree. Suppose $T^{\prime }$ is the resulting tree through such a relabelling. Note that n is pendent in the tree $T^{\prime }$, n−1 is pendent in the tree $T^{\prime }-n$, and in general, j is pendent in the tree $T^{\prime }-\{j+1,\dots ,n\}$. This observation facilitates a way for counting the number of successively connected relabellings by reducing the problem to counting the same for trees with lesser number of vertices.

Let $P^{\left(T\right)}$ be the set of pendent vertices of T. For $v\in P^{\left(T\right)}$ the number of successively connected relabellings of T with v as the nth vertex is $\ell (T-v)$. We obtain the following recurrence relation for $\ell \left(T\right)$. (10) $\ell \left(T\right)=\sum _{v\in P^{\left(T\right)}}\ell (T-v).$(10)

Using the recurrence relation (10(10) $\ell \left(T\right)=\sum _{v\in P^{\left(T\right)}}\ell (T-v).$(10) ), we compute the number of distinct successively connected labellings of some special trees.

6.1. The path $P_n$

Consider the path $P_n$ on n vertices Figure 7. Clearly, $\ell \left(P_1\right)=1$. For $n\ge 2$, $P_n$ has two pendent vertices, and deletion of each of them from $P_n$ results $P_{n-1}$. Thus, by repeated application of (10(10) $\ell \left(T\right)=\sum _{v\in P^{\left(T\right)}}\ell (T-v).$(10) ) gives $\ell \left(P_n\right)=2\ell \left(P_{n-1}\right)=\cdots =2^{n-1}\ell \left(P_1\right)=2^{n-1}.$

Figure 7. The path $P_n$.

Since $|\mathcal{A}ut\left(P_n\right)|=2$, the number of dominant solutions obtained from the successively connected relabellings of $P_n$ is $2^{n-2}$.

6.2. The star $S_n$

Let $S_n$ denote the star on n vertices Figure 8, $n\ge 2$. We have $\ell \left(S_2\right)=\ell \left(P_2\right)=2$. There are n−1 pendent vertices in $S_n$ and deletion of each gives a star with n−1 vertices. So, by repeated application of (10(10) $\ell \left(T\right)=\sum _{v\in P^{\left(T\right)}}\ell (T-v).$(10) ), we get $\ell \left(S_n\right)=(n-1)\ell \left(S_{n-1}\right)=\cdots =(n-1)(n-2)\cdots 3\cdot 2\cdot \ell \left(S_2\right)=2\cdot (n-1)!.$

Figure 8. The star $S_n$.

Now, the permutations of the pendent vertices produce all automorphisms of $S_n$. So, $|\mathcal{A}ut\left(S_n\right)|=(n-1)!$. Consequently, the number of dominant solutions obtained from the successively connected relabellings of $S_n$ is 2.

6.3. The broom (or comet) $B_{n,m}$

The broom $B_{n,m}$ (see Figure 9) has n + m vertices of which m + 1 vertices, namely, $1,n+1,n+2,\dots ,n+m$, are pendent vertices. Since $B_{n,1}$ is the path $P_{n+1}$ and $B_{1,m}$ is the star $S_{m+1}$, we have $\ell \left(B_{n,1}\right)=2^n$ and $\ell \left(B_{1,m}\right)=2\cdot m!$.

Figure 9. The broom $B_{n,m}$.

For $n,m\ge 2$, the deletion of the pendent vertex 1 from $B_{n,m}$ produces $B_{n-1,m}$, and the deletion of each of the pendent vertices $n+1,\dots ,n+m$ produces $B_{n,m-1}$. Applying (10(10) $\ell \left(T\right)=\sum _{v\in P^{\left(T\right)}}\ell (T-v).$(10) ), we get the recurrence relation (11) $\ell \left(B_{n,m}\right)=\ell \left(B_{n-1,m}\right)+m\cdot \ell \left(B_{n,m-1}\right).$(11)

Using (11(11) $\ell \left(B_{n,m}\right)=\ell \left(B_{n-1,m}\right)+m\cdot \ell \left(B_{n,m-1}\right).$(11) ), for $n\ge 2$ we get $\begin{array}{rl}\ell \left(B_{n,2}\right)& =\ell \left(B_{n-1,2}\right)+2\cdot \ell \left(B_{n,1}\right)\\ & =(\ell \left(B_{n-2,2}\right)+2\cdot \ell \left(B_{n-1,1}\right))+2\cdot \ell \left(B_{n,1}\right)\\ & =\ell \left(B_{1,2}\right)+2(\ell \left(B_{2,1}\right)+\ell \left(B_{3,1}\right)+\cdots +\ell \left(B_{n,1}\right))\\ & =2\cdot 2!+2(2^2+2^3+\cdots +2^n)\\ & =2!\sum _{i=1}^n{2}^i.\end{array}$

Similarly, $\begin{array}{rl}\ell \left(B_{n,3}\right)& =\ell \left(B_{n-1,3}\right)+3\cdot \ell \left(B_{n,2}\right)\\ & =(\ell \left(B_{n-2,3}\right)+3\cdot \ell \left(B_{n-1,2}\right))+3\cdot \ell \left(B_{n,2}\right)\\ & =\ell \left(B_{1,3}\right)+3(\ell \left(B_{2,2}\right)+\ell \left(B_{3,2}\right)+\cdots +\ell \left(B_{n,2}\right))\\ & =2\cdot 3!+3\cdot 2!(\sum _{i=1}^1{2}^i+\sum _{i=1}^2{2}^i+\cdots +\sum _{i=1}^n{2}^i)\\ & =3!\sum _{j=1}^n\sum _{i=1}^j{2}^i.\end{array}$

Using induction on m we show that for $m\ge 2$ (12) $\ell \left(B_{n,m}\right)=m!\sum _{i_{m-1}=1}^n\sum _{i_{m-2}=1}^{i_{m-1}}\cdots \sum _{i_1=1}^{i_2}{2}^{i_1},n\ge 2.$(12)

Assuming our claim true for $B_{n,m-1}$ and using the recurrence relation (11(11) $\ell \left(B_{n,m}\right)=\ell \left(B_{n-1,m}\right)+m\cdot \ell \left(B_{n,m-1}\right).$(11) ) we get $\begin{array}{rl}\ell \left(B_{n,m}\right)& =\ell \left(B_{n-1,m}\right)+m\cdot \ell \left(B_{n,m-1}\right)\\ & =(\ell \left(B_{n-2,m}\right)+m\cdot \ell \left(B_{n-1,m-1}\right))+m\cdot \ell \left(B_{n,m-1}\right)\\ & =\ell \left(B_{1,m}\right)+m(\ell \left(B_{2,m-1}\right)+\ell \left(B_{3,m-1}\right)+\cdots +\ell \left(B_{n,m-1}\right))\\ & =\ell \left(B_{1,m}\right)+m\sum _{i_{m-1}=2}^n\ell \left(B_{i_{m-1},m-1}\right)\\ & =2\cdot m!+m\sum _{i_{m-1}=2}^n\left(\right(m-1)!\sum _{i_{m-2}=1}^{i_{m-1}}\sum _{i_{m-3}=1}^{i_{m-2}}\cdots \sum _{i_1=1}^{i_2}{2}^{i_1})\\ & =m!(2+\sum _{i_{m-1}=2}^n\sum _{i_{m-2}=1}^{i_{m-1}}\sum _{i_{m-3}=1}^{i_{m-2}}\cdots \sum _{i_1=1}^{i_2}{2}^{i_1})\\ & =m!\sum _{i_{m-1}=1}^n\sum _{i_{m-2}=1}^{i_{m-1}}\cdots \sum _{i_1=1}^{i_2}{2}^{i_1}.\end{array}$

Thus, for $n,m\ge 2$ we have $\ell \left(B_{n,m}\right)=m!\sum _{i_{m-1}=1}^n\sum _{i_{m-2}=1}^{i_{m-1}}\cdots \sum _{i_1=1}^{i_2}{2}^{i_1}.$

Now, the permutations of the pendent vertices $n+1,\dots ,n+m$ produce all automorphisms of $B_{n,m}$. So, $|\mathcal{A}ut\left(B_{n,m}\right)|=m!$. Consequently, the number of dominant solutions obtained from the successively connected relabellings of $B_{n,m}$ is given by $\sum _{i_{m-1}=1}^n\sum _{i_{m-2}=1}^{i_{m-1}}\dots \sum _{i_1=1}^{i_2}{2}^{i_1}.$

7. Conclusion

We have solved the IEPT completely for all trees with successively connected labellings and for the case where the given eigenvalues are distinct. The solution is primarily based on Cauchy's interlacing theorem and the recurrence relations obtained in Lemma 4.8. Trees are useful structures in graph theory as well as in computer science and methods of constructing matrices of trees having a desired eigen structure can be quite useful. The problem studied in this paper gives one such method which may also find its applications. The case for other type of labellings and for non-distinct eigenvalues can be studied further. The combinatorial problem of determining the number of distinct successively connected labellings of an arbitrary tree can also be studied further.

Acknowledgments

The authors thank the anonymous referees for their valuable comment that has enhanced the presentation of the article.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The authors also thank the Science and Engineering Research Board (SERB), Government of India for supporting this work under the Teachers Associateship for Research Excellence (TARE) project [file number TAR/2018/000245].