1. Introduction
Let \(G=(V,E)\) be a simple, connected graph with \(n=|V|\) vertices.
The spectrum of \(G\) consists of the eigenvalues of its \((0,1)\)-adjacency matrix \(A\),
ordered as \(\lambda_1>\lambda_2\geq\dots\geq\lambda_n\).
Let \(x_1,\dots,x_n\) be an orthonormal basis of eigenvectors of \(A\),
such that \(x_i\) is an eigenvector of \(\lambda_i\) for \(i=1,\dots,n\).
The adjacency matrix \(A\) then has a spectral decomposition \(A=Q\Lambda Q^\top\),
where \(\Lambda=\mathrm{diag}(\lambda_1,\dots,\lambda_n)\) and
\(Q=[x_1\ x_2\ \dots\ x_n]\) is the matrix with eigenvectors listed in columns.
As in Nikiforov [1], let \(w_k\) denote the number of walks with \(k\) vertices, hence of length \(k-1\), in a graph \(G\).
Since \(w_k\) is the sum of entries of \(A^{k-1}\),
the spectral decomposition yields \(A^{k-1}=Q\Lambda^{k-1}Q^\top\),
so
\begin{equation}
w_k=\sum_{i=1}^n \lambda_i^{k-1}\left(\sum_{j=1}^n x_{i,j}\right)^{\!2}.
\end{equation}
(1)
Apparently, only those eigenvalues \(\lambda_i\) for which \(\sum_{j=1}^n x_{i,j}\) is not zero
affect the value of \(w_k\). Such eigenvalues are called the main eigenvalues.
The spectral radius \(\lambda_1\) of a connected graph is always a main eigenvalue,
due to its strictly positive eigenvector \(x_1\) [2].
Regular graphs, for which \(x_1\) is proportional to the all-one vector \(\mathbf{j}\),
have exactly one main eigenvalue, as all their other eigenvectors are orthogonal to \(\mathbf{j}\).
It follows from (1) that \(\lambda_1=\lim_{k\to\infty} \sqrt[2k]{w_{2k+1}}\),
as \(\lambda_1\) has the largest absolute value among the eigenvalues of \(A\)
by the Perron-Frobenius theorem [2].
Nikiforov proved in [1] that the inequality \(\lambda_1^r\geq w_{s+r}/w_s\) holds for all odd \(s>0\) and all \(r>0\).
He further showed that \(\lambda_1^r\) can be smaller than \(w_{s+r}/w_s\) for even \(s\) and odd \(r\)
on the example of complete bipartite graphs,
and then posed the following problem.
Problem 1.[1]
Let \(G\) be a connected bipartite graph. Is it true that
$$
\lambda_1^r\geq\frac{w_{s+r}}{w_s}
$$
for every even \(s\geq 2\) and even \(r\geq 2\)?
Several counterexamples have been found since the problem was posed.
Nikiforov himself offered the complete tripartite graph \(K_{2t,2t,t}\) as a counterexample for \(s=r=2\).
Elphick and Réti [3] produced an infinite family of unicyclic graphs as counterexamples for \(s=r=2\) and
further showed that the path \(P_4\) is a counterexample for even \(s\geq 2\) and arbitrary \(r\).
One of the reviewers of [4] provided the following more general result.
Theorem 1.[4]
Let \(G\) be a connected graph with two main eigenvalues \(\lambda_1\) and \(\lambda_i\),
such that \(0>\lambda_i>-\lambda_1\).
If \(s\geq 2\) and \(r\geq 2\) are even, then
$$
\lambda_1^r < \frac{w_{s+r}}{w_s}.
$$
While Cvetković [5] posed
the problem of characterizing graphs with a given number of main eigenvalues already in 1978,
the first results on graphs with two main eigenvalues started to appear
only after a seminal paper by Hagos [6] was published in 2002.
Hagos showed that a graph has exactly \(k\) main eigenvalues
if and only if \(k\) is the maximum number such that
\(\mathbf{j}\), \(A\mathbf{j}\), \dots, \(A^{k-1}\mathbf{j}\) are linearly independent.
For \(k=2\) this means that there exist \(\alpha\) and \(\beta\) such that
\begin{equation}
\label{eq-2-walk-linear}
A^2\mathbf{j}=\alpha A\mathbf{j}+\beta\mathbf{j},
\end{equation}
(2)
and that \(G\) is not regular.
Graph \(G\) satisfying (2) is also called a
2-walk \((\alpha,\beta)\)-linear graph
and its main eigenvalues are [
6, Corollary 2.5]
\begin{equation}
\label{eq-main-eigenvalues}
\mu_1,\mu_2=\frac{\alpha\pm\sqrt{\alpha^2+4\beta}}2.
\end{equation}
(3)
Various constructions of graphs with two main eigenvalues have been described
in a number of papers [7, 8, 9, 10, 11, 12, 13, 14],
and graphs satisfying the requirements of Theorem 1 can be found in most of these papers.
Our purpose here is to generalize a set of counterexamples presented in [4],
which enables one to show that the ratio \(\frac{w_{s+r}}{\lambda_1^r w_s}\) can be significantly larger than 1.
Since this cannot be shown by using main eigenvalues and their eigenvectors only,
we will resort to combinatorial counting of walks in such graphs.
Let us recall the definition of equitable partition of vertices.
Let \(\pi=\{\pi_1,\dots,\pi_k\}\) be a partition of the vertex set of a graph \(G\),
and for each \(v\in\pi_i\) denote by \(d^{(j)}_v\) the number of neighbors of \(v\) in \(\pi_j\).
The partition \(\pi\) is called {\em equitable}
if for all \(i\) and \(j\), the value \(d^{(j)}_v\) has the same value, denote it by \(d^{i\to j}\), for all \(v\in\pi_i\).
The {\em quotient matrix} of such partition \(\pi\) is the matrix \(Q_{\pi}=\left(d^{i\to j}\right)\).
Definition 1.
For positive integers \(p,q\) and \(r\), let \(\mathcal{G}_{p,q,r}\) be
the set of graphs which have an equitable vertex partition with the quotient matrix
\(\left[\begin{smallmatrix} p & q \\ r & 0 \end{smallmatrix}\right]\).
We can now state the main results of the paper.
Theorem 2.
Let \(G\in\mathcal{G}_{p,q,r}\) and
let \(A\cup B\) be an equitable partition of \(G\) with the quotient matrix
\(\left[\begin{smallmatrix} p & q \\ r & 0 \end{smallmatrix}\right]\).
Then for any \(k\in\mathbb{N}\),
\begin{align}
\label{eq-walks-gpqr}
w_k = |A|&\left(\sum_{l=0}^{\left\lfloor\frac{k-1}2\right\rfloor} {k-l-1\choose l} p^{k-2l-1}q^lr^l +\sum_{l=1}^{\left\lfloor\frac{k}2\right\rfloor} {k-l-1\choose l-1}2p^{k-2l} q^lr^{l-1} +\sum_{l=2}^{\left\lfloor\frac{k+1}2\right\rfloor} {k-l-1\choose l-2} p^{k-2l+1}q^lr^{l-2}\right).
\end{align}
(4)
Let \((F_n)_{n\geq 0}\) be the sequence of Fibonacci numbers
and \(\varphi=(1+\sqrt5)/2\) be the golden ratio.
Theorem 3.
In each of the following cases, there exists a separate sequence of connected bipartite graphs \((G_p)_{p\in\mathbb{N}}\)
such that:
a)
\(
\displaystyle\lim_{p\to\infty}
\displaystyle\frac{w_{s+r}(G_p)}{\lambda_1^r(G_p) w_s(G_p)}
=\displaystyle\frac{s+r-2}{s-2},
\)
for even \(s\geq 4\) and even \(r\geq 2\);
b)
\(
\displaystyle\lim_{p\to\infty}
\displaystyle\frac{w_{s+r}(G_p)}{\lambda_1^r(G_p) w_s(G_p)}
=\displaystyle\frac{s+r}{s},
\)
for even \(s\geq 2\) and even \(r\geq 2\);
c)
\(
\displaystyle\lim_{p\to\infty}
\displaystyle\frac{w_{s+r}(G_p)}{\lambda_1^r(G_p) w_s(G_p)}
=\displaystyle\frac{s+r+2}{s+2},
\)
for even \(s\geq 2\) and even \(r\geq 2\);
d)
\(
\displaystyle\lim_{p\to\infty}
\displaystyle\frac{w_{s+r}(G_p)}{\lambda_1^r(G_p) w_s(G_p)}
=\displaystyle\frac{F_{s+r}}{\varphi^r F_s},
\)
for even \(s\geq 2\) and even \(r\geq 2\);
e)
\(
\displaystyle\lim_{p\to\infty}
\displaystyle\frac{w_{s+r}(G_p)}{\lambda_1^r(G_p) w_s(G_p)}
=\displaystyle\frac{F_{s+r-2}}{\varphi^r F_{s-2}},
\)
for even \(s\geq 4\) and even \(r\geq 2\).
Theorem 2 is proved in Section 2,
while the various parts of Theorem 3 are proved in Section 3.
2. Numbers of walks in graphs from \(\mathcal{G}_{p,q,r}\)
Proof. [Proof of Theorem 2]
Let \(A\cup B\) be an equitable partition of \(G\) with the quotient matrix
\(Q=\left[\begin{smallmatrix} p & q \\ r & 0 \end{smallmatrix}\right]\).
Due to \(Q_{2,2}=0\), from each vertex in \(B\)
a walk can continue only to one of its \(r\) neighbors in \(A\),
while from each vertex in \(A\)
a walk can continue to either one of its \(p\) neighbors in \(A\) or one of its \(q\) neighbors in \(B\).
We can now classify the \(k\)-walks in \(G\)
according to the \(k\)-sequence of letters \(A\), \(B\)
indicating to which set the vertices along a walk belong.
For a given \(k\)-sequence of letters \(A\) and \(B\),
the number of the corresponding \(k\)-walks can be determined
by choosing the first vertex of a walk and then
by considering pairs of successive letters:
- each pair \(AA\) yields \(p\) choices for the second \(A\)
after the vertex corresponding to the first \(A\) is chosen;
- each pair \(AB\) yields \(q\) choices for \(B\) after the vertex for \(A\) is chosen;
- each pair \(BA\) yields \(r\) choices for \(A\) after the vertex for \(B\) is chosen.
For example, the sequence \(BAABA\) encodes \(|B|\cdot r\cdot p\cdot q\cdot r=pqr^2|B|\) walks with five vertices,
while \(AABAABA\) encodes \(|A|\cdot p\cdot q\cdot r\cdot p\cdot q\cdot r=p^2q^2r^2|A|\) walks with seven vertices.
The fact that a feasible type sequence does not contain the pair \(BB\)
means that each letter \(B\) may occupy either a single position between any two consecutive letters \(A\),
or a single position prior to the first \(A\) or after the last \(A\).
Since the number of walks with \(k\) vertices with a given letter sequence is
influenced by the first and the last letter of the sequence,
we will count them separately, working out in detail the first possibility only.
Hence suppose that a given letter sequence starts and ends with the letter \(A\)
and that it contains \(l\) letters \(B\) (and consequently \(k-l\) letters \(A\)).
There are \(k-l-1\) feasible positions for letters \(B\) between consecutive letters \(A\),
so the number of such letter sequences is \({k-l-1\choose l}\).
The initial letter \(A\) yields \(|A|\) choices for the initial vertex of a \(k\)-walk.
Each letter \(B\) appearing in the type sequence produces one pair \(AB\) and one pair \(BA\),
which together yield \(qr\) choices for two corresponding vertices along a \(k\)-walk.
This leaves a total of \(k-1-2l\) pairs \(AA\) remaining in the type sequence,
each of which yields \(p\) choices for the corresponding vertex in a \(k\)-walk.
Hence each letter sequence starting and ending with \(A\)
corresponds to a total of \(p^{k-2l-1}(qr)^l|A|\) walks with \(k\) vertices,
and the number of \(k\)-walks corresponding to all such letter sequences is equal to
$$
\sum_{l\geq 0} {k-l-1\choose l} p^{k-2l-1}q^lr^l|A|.
$$
Following the similar argument, we get that:
-
the number of \(k\)-walks corresponding to letter sequences starting with \(A\) and ending with \(B\)
is equal to
$$
\sum_{l\geq 1} {k-l-1\choose l-1} p^{k-2l}q^lr^{l-1}|A|;
$$
-
the number of \(k\)-walks corresponding to letter sequences starting with \(B\) and ending with \(A\)
is equal to
$$
\sum_{l\geq 1} {k-l-1\choose l-1} p^{k-2l}q^{l-1}r^l|B|;
$$
-
the number of \(k\)-walks corresponding to letter sequences starting and ending with \(B\)
is equal to
$$
\sum_{l\geq 2} {k-l-1\choose l-2}p^{k-2l+1}q^{l-1}r^{l-1}|B|.
$$
Summing up these four cases we see that the total number of \(k\)-walks in \(G\) is:
\begin{eqnarray}
\label{eq-walks-almost}
w_k &=& \sum_{l\geq 0} {k-l-1\choose l} p^{k-2l-1}q^lr^l|A| + \sum_{l\geq 1} {k-l-1\choose l-1} p^{k-2l}q^{l-1}r^{l-1}(q|A|+r|B|)\nonumber\\&&+ \sum_{l\geq 2} {k-l-1\choose l-2}p^{k-2l+1}q^{l-1}r^{l-1}|B|.
\end{eqnarray}
(5)
Note that the number of edges with one vertex in \(A\) and another in \(B\)
can be counted as both \(q|A|\) and \(r|B|\), which yields \(q|A|=r|B|\),
so (5) becomes:
\begin{eqnarray}
\label{eq-walks-almost2}
w_k &=& |A|\left(\sum_{l\geq 0} {k-l-1\choose l} p^{k-2l-1}q^lr^l+ \sum_{l\geq 1} {k-l-1\choose l-1} 2p^{k-2l}q^lr^{l-1} +\sum_{l\geq 2} {k-l-1\choose l-2} p^{k-2l+1}q^lr^{l-2}\right).
\end{eqnarray}
(6)
Upper limits for the three sums in (6)
can be determined from the corresponding binomial coefficients:
- nonzero summands in the first sum are obtained for \(k-l-1\geq l\),
i.e., for \(l\leq \left\lfloor\frac{k-1}2\right\rfloor\);
- nonzero summands in the second sum are obtained for \(k-l-1\geq l-1\),
i.e., for \(l\leq \left\lfloor\frac{k}2\right\rfloor\);
- nonzero summands in the third sum are obtained for \(k-l-1\geq l-2\),
i.e., for \(l\leq \left\lfloor\frac{k+1}2\right\rfloor\).
Putting these upper limits in (6) yields (4).
3. Nikiforov’s ratio when \(q\) and \(r\) are powers of \(p\)
The key to proving various parts of Theorem 3 is
to turn the expression for the number of walks \(w_k\) into a polynomial of a single variable
by letting \(q\) and \(r\) to be the powers of \(p\):
\(q=p^c\) and \(r=p^d\) for some nonnegative integers \(c\) and \(d\).
In such case we have
\begin{align}
\label{eq-special-case}
w_k = |A|& \left(\sum_{l=0}^{\left\lfloor\frac{k-1}2\right\rfloor} {k-l-1\choose l} p^{k+(c+d-2)l-1} \right.+ \sum_{l=1}^{\left\lfloor\frac{k}2\right\rfloor} {k-l-1\choose l-1}2p^{k+(c+d-2)l-d}\nonumber \\
&+\left.\sum_{l=2}^{\left\lfloor\frac{k+1}2\right\rfloor} {k-l-1\choose l-2} p^{k+(c+d-2)l+1-2d}\right).
\end{align}
(7)
In addition,
the quotient matrix \(Q=\left[\begin{smallmatrix} p & q \\ r & 0 \end{smallmatrix}\right]\)
determines a divisor of any graph \(G\in\mathcal{G}_{p,q,r}\).
As graphs in \(\mathcal{G}_{p,q,r}\) are not regular when \(p+q\neq r\),
by [
15, Theorem 3.9.9]
any of them has two main eigenvalues that are equal to the eigenvalues of \(Q\):
\begin{equation}
\label{eq-spectral-radius}
\lambda_1,\lambda_i = \frac{p\pm\sqrt{p^2+4qr}}2 = \frac{p\pm\sqrt{p^2+4p^{c+d}}}2.
\end{equation}
(8)
Now we can determine the limit of the Nikiforov’s ratio \(\frac{w_{s+r}}{\lambda_1^r w_s}\)
by discussing possible cases.
Since the Nikiforov’s problem assumes both \(s\) and \(r\) to be even,
we will assume that \(k\) in (7) is even, i.e., $$k=2k’,$$
in order to simplify discussion.
Case 1: \(c+d-2>0\).
In this case
$$
\lim_{p\to\infty} \frac{\lambda_1}{p^{(c+d)/2}}=1.
$$
The highest exponents appearing in the three sums of (7) are
$$
2k’+(c+d-2)(k’-1)-1,
2k’+(c+d-2)k’-d,
2k’+(c+d-2)k’+1-2d,
$$
respectively.
We can now distinguish the following subcases.
Subcase 1(a): \(c=0\), hence \(d>2\).
In this case, the highest exponent in (7) is \(2k’+(c+d-2)(k’-1)-1\),
appearing in the first sum for \(l=k’-1\),
and the corresponding coefficient is equal to
$$
{2k’-(k’-1)-1\choose k’-1}=k’=\frac{k}2.
$$
Hence in this subcase
\begin{align*}
\lim_{p\to\infty} \frac{w_{s+r}}{\lambda_1^r w_s}
=\lim_{p\to\infty} \frac{w_{s+r}}{p^{(s+r)+(c+d-2)(\frac{s+r}2-1)-1}}
\frac{p^{r(c+d)/2}}{\lambda_1^r}
\frac{p^{s+(c+d-2)(\frac{s}2-1)-1}}{w_s}
=\frac{s+r}2\cdot1\cdot\frac2{s}
=\frac{s+r}s.
\end{align*}
There remains to construct a sequence \((G_p)_{p\geq 1}\) of connected bipartite graphs
with equitable partition \(A_p\cup B_p\) that corresponds to this case.
The simplest choice is to let, for each \(p\geq 1\),
the vertex set \(A_p\) to consist of vertices \(\{a_0,\dots,a_{p^d-1}\}\cup\{a’_0,\dots,a’_{p^d-1}\}\)
and the vertex set \(B_p\) to consist of vertices \(b\) and \(b’\) only.
The subgraph induced by \(A_p\) should be \(p\)-regular,
say by making the vertex \(a_i\) adjacent to vertices \(a’_i,\dots,a’_{i+p-1}\) for \(i=0,\dots,p^d-1\),
where addition is done modulo \(p\),
while the vertex \(b\) is adjacent to vertices in \(\{a_0,\dots,a_{p^d-1}\}\)
and the vertex \(b’\) is adjacent to vertices in \(\{b_0,\dots,b_{p^d-1}\}\).
\(A_p\cup B_p\) is then an equitable vertex partition with the quotient matrix
\(\left[\begin{smallmatrix} p & 1 \\ p^d & 0 \end{smallmatrix}\right]\), as requested,
thus proving part b) of Theorem 3.
Subcase 1(b): \(c=1\), hence \(d>1\).
In this case, the highest exponent in (7) is \(2k’+(c+d-2)(k’-1)-1=2k’+(c+d-2)k’-d\),
appearing in the first sum for \(l=k’-1\) and in the second sum for \(l=k’\).
Hence the corresponding coefficient is equal to
$$
{2k’-(k’-1)-1\choose k’-1} + {2k’-k’-1\choose k’-1} = k’+1 = \frac{k+2}2.
$$
Then in this subcase
\begin{align*}
\lim_{p\to\infty} \frac{w_{s+r}}{\lambda_1^r w_s} =\lim_{p\to\infty} \frac{w_{s+r}}{p^{(s+r)+(c+d-2)(\frac{s+r}2-1)-1}}
\frac{p^{r(c+d)/2}}{\lambda_1^r}
\frac{p^{s+(c+d-2)(\frac{s}2-1)-1}}{w_s}
=\frac{s+r+2}2\cdot1\cdot\frac2{s+2}
=\frac{s+r+2}{s+2}.
\end{align*}
There remains to construct a sequence \((G_p)_{p\geq 1}\) of connected bipartite graphs
with equitable partition \(A_p\cup B_p\) that corresponds to this case.
The simplest choice is to let, for each \(p\geq 1\),
the vertex set \(A_p\) to consist of vertices \(\{a_1,\dots,a_{p^d}\}\cup\{a’_1,\dots,a’_{p^d}\}\)
and the vertex set \(B_p\) to consist of vertices \(\{b_1,\dots,b_p\}\cup\{b’_1,\dots,b’_{p}\}\).
The subgraph induced by \(A_p\) should be \(p\)-regular,
which can be done in the same way as in Subcase 1.a.
The subgraph induced by the vertices in \(\{a_1,\dots,a_{p^d}\}\cup\{b_1,\dots,b_p\}\)
should be isomorphic to the complete bipartite graph \(K_{p^d,p}\),
as well as the subgraph induced by the vertices in \(\{a’_1,\dots,a’_{p^d}\}\cup\{b’_1,\dots,b’_p\}\).
\(A_p\cup B_p\) is then an equitable vertex partition with the quotient matrix
\(\left[\begin{smallmatrix} p & p \\ p^d & 0 \end{smallmatrix}\right]\), as requested,
thus proving part c) of Theorem 3.
Subcase 1(c): \(d=0\), hence \(c>2\).
In this subcase, the highest exponent in (7) is \(2k’+(c+d-2)k’+1-2d\),
appearing in the third sum for \(l=k’\).
The corresponding coefficient is equal to
$$
{2k’-k’-1\choose k’-2}=k’-1=\frac{k-2}2.
$$
Hence
\begin{align*}
\lim_{p\to\infty} \frac{w_{s+r}}{\lambda_1^r w_s} =\lim_{p\to\infty} \frac{w_{s+r}}{p^{(s+r)+(c+d-2)\frac{s+r}2+1-2d}}
\frac{p^{r(c+d)/2}}{\lambda_1^r}
\frac{p^{s+(c+d-2)\frac{s}2+1-2d}}{w_s}
=\frac{s+r-2}2\cdot1\cdot\frac2{s-2}
=\frac{s+r-2}{s-2}.
\end{align*}
There remains to construct a sequence \((G_p)_{p\geq 1}\) of connected bipartite graphs
with equitable partition \(A_p\cup B_p\) that corresponds to this case.
The simplest choice is to let, for each \(p\geq 1\),
\(A_p\) to be the vertex set of a complete bipartite graph \(K_{p,p}\),
and then to attach \(q=p^c\) pendant vertices to each vertex of \(K_{p,p}\),
with these \(p^c|A|\) pendant vertices forming the vertex set \(B_p\).
\(A_p\cup B_p\) is then an equitable vertex partition with the quotient matrix
\(\left[\begin{smallmatrix} p & p^c \\ 1 & 0 \end{smallmatrix}\right]\), as requested,
thus proving part a) of Theorem 3.
Subcase 1(d): \(d=1\), hence \(c>1\).
In this subcase, the highest exponent in (7) is \(2k’+(c+d-2)k’-d=2k’+(c+d-2)k’+1-2d\),
appearing in the second sum for \(l=k’\) and in the third sum also for \(l=k’\).
The corresponding coefficient is thus equal to
$$
{2k’-k’-1\choose k’-1} + {2k’-k’-1\choose k’-2} = k’ = \frac k2.
$$
Hence
\begin{align*}
\lim_{p\to\infty} \frac{w_{s+r}}{\lambda_1^r w_s} =\lim_{p\to\infty} \frac{w_{s+r}}{p^{(s+r)+(c+d-2)\frac{s+r}2+1-2d}}
\frac{p^{r(c+d)/2}}{\lambda_1^r}
\frac{p^{s+(c+d-2)\frac{s}2+1-2d}}{w_s} =\frac{s+r}2\cdot1\cdot\frac2{s}
=\frac{s+r}{s}.
\end{align*}
Constructing a sequence of connected, bipartite graphs corresponding to this subcase
would yield another proof of part b) of Theorem 3.
Subcase 1(e): \(c,d\geq 2\).
In this subcase, the highest exponent in (7) is \(2k’+(c+d-2)k’-d\),
appearing in the second sum for \(l=k’\).
The corresponding coefficient is equal to
$$
{2k’-k’-1\choose k’-1} = 1,
$$
so
$$
\lim_{p\to\infty} \frac{w_{s+r}}{\lambda_1^r w_s}
=\lim_{p\to\infty} \frac{w_{s+r}}{p^{(s+r)+(c+d-2)\frac{s+r}2-d}}
\frac{p^{r(c+d)/2}}{\lambda_1^r}
\frac{p^{s+(c+d-2)\frac{s}2-d}}{w_s}
=1\cdot1\cdot1=1,
$$
which is not helpful for the Nikiforov’s problem.
Case 2: \(c+d-2=0\), i.e., \((c,d)\in\{(0,2),(1,1),(2,0)\}\).
In this case
$$
\lim_{p\to\infty} \frac{\lambda_1}{p} = \frac{1+\sqrt5}2.
$$
The highest exponents appearing in the three sums of (7) are
$$
2k’-1,
2k’-d,
2k’+1-2d,
$$
respectively.
To calculate the corresponding coefficients in this case
we will rely on the following summation formula \cite[Formula 1.61]{Gould}:
$$
\sum_{l=0}^{\left\lfloor\frac k2\right\rfloor} {k-l\choose l}2^k\left(\frac z4\right)^l
=\frac{x^{k+1}-y^{k+1}}{x-y},
$$
where \(x=1+\sqrt{z+1}\) and \(y=1-\sqrt{z+1}\).
In particular, for \(z=4\) we have \(x=1+\sqrt5\) and \(y=1-\sqrt5\),
so
$$
\sum_{l=0}^{\left\lfloor\frac k2\right\rfloor} {k-l\choose l}
=\frac{(1+\sqrt5)^{k+1}-(1-\sqrt5)^{k+1}}{2^{k+1}\sqrt5}
=\frac{\varphi^{k+1}-\psi^{k+1}}{\sqrt5}
=F_{k+1},
$$
where \(\varphi=x/2=(1+\sqrt5)/2\), \(\psi=y/2=(1-\sqrt5)/2\)
and \((F_n)_{n\geq 0}\) is the usual Fibonacci sequence.
Subcase 2(a): \((c,d)=(0,2)\).
The highest exponent is \(2k’-1\),
appearing in the first sum for all values of \(l=0,\dots,k’-1\).
Hence the corresponding coefficient is equal to
$$
\sum_{l=0}^{k’-1} {2k’-1-l\choose l}= F_{k},
$$
so
$$
\lim_{p\to\infty} \frac{w_{s+r}}{\lambda_1^r w_s}
= \lim_{p\to\infty} \frac{w_{s+r}}{p^{s+r-1}}
\frac{p^r}{\lambda_1^r}
\frac{p^{s-1}}{w_s}
= \frac{F_{s+r}}{\varphi^r F_s}.
$$
Since \(s\) and \(r\) are even and \(-\varphi< \psi\frac{\varphi^r(\varphi^s-\psi^s)}{\sqrt5}=\varphi^r F_s,
$$
so the limit above is larger than 1,
although it tends to 1 when \(s\) tends to infinity.
There remains to construct a sequence \((G_p)_{p\geq 1}\) of connected bipartite graphs
with equitable partition \(A_p\cup B_p\) that corresponds to this case.
We can use the same construction as in Subcase 1(a),
setting for each \(p\geq 1\)
the vertex set \(A_p\) to consist of vertices \(\{a_0,\dots,a_{p^2-1}\}\cup\{a’_0,\dots,a’_{p^2-1}\}\)
and the vertex set \(B_p\) to consist of vertices \(b\) and \(b’\) only.
The subgraph induced by \(A_p\) should be \(p\)-regular,
while the vertex \(b\) is adjacent to vertices in \(\{a_0,\dots,a_{p^2-1}\}\)
and the vertex \(b’\) is adjacent to vertices in \(\{b_0,\dots,b_{p^2-1}\}\).
\(A_p\cup B_p\) is then an equitable vertex partition with the quotient matrix
\(\left[\begin{smallmatrix} p & 1 \\ p^2 & 0 \end{smallmatrix}\right]\), as requested,
thus proving part d) of Theorem 3.
Subcase 2(b): \((c,d)=(1,1)\).
The highest exponent is \(2k’-1\),
appearing in all three sums for all values of \(l\).
Hence the corresponding coefficient is equal to
\begin{align*}
& \sum_{l=0}^{k’-1} {2k’-1-l\choose l}
+ \sum_{l=1}^{k’} {2k’-1-l\choose l-1}
+ \sum_{l=2}^{k’} {2k’-1-l\choose l-2} \\
=&
\sum_{l=0}^{k’-1} {2k’-1-l\choose l}
+\sum_{l=0}^{k’-1} {2k’-2-l\choose l} % l=1+l’
+\sum_{l’=0}^{k’-2} {2k’-3-l\choose l} \\ % l=2+l’
=& F_{2k’} + F_{2k’-1} + F_{2k’-2} = 2F_{k},
\end{align*}
due to \(F_{2k’-1}+F_{2k’-2}=F_{2k’}\).
Thus
$$
\lim_{p\to\infty} \frac{w_{s+r}}{\lambda_1^r w_s}
= \lim_{p\to\infty} \frac{w_{s+r}}{p^{s+r-1}}
\frac{p^r}{\lambda_1^r}
\frac{p^{s-1}}{w_s}
= \frac{F_{s+r}}{\varphi^r F_s}.
$$
Constructing a sequence of connected bipartite graphs corresponding to this subcase
would yield another proof of part d) of Theorem 3.
Subcase 2(c): \((c,d)=(2,0)\).
The highest exponent is \(2k’+1\),
appearing in the third sum for all values of \(l=2,\dots,k’\),
with the corresponding coefficient equal to
$$
\sum_{l=2}^{k’} {2k’-1-l\choose l-2}
=\sum_{l’=0}^{k’-2} {2k’-3-l\choose l}=F_{k-2}. % l=2+l’
$$
Hence
$$
\lim_{p\to\infty} \frac{w_{s+r}}{\lambda_1^r w_s}
= \lim_{p\to\infty} \frac{w_{s+r}}{p^{s+r+1}}
\frac{p^r}{\lambda_1^r}
\frac{p^{s+1}}{w_s}
= \frac{F_{s+r-2}}{\varphi^r F_{s-2}}.
$$
There remains to construct a sequence \((G_p)_{p\geq 1}\) of connected bipartite graphs
with equitable partition \(A_p\cup B_p\) that corresponds to this case.
We can use the same construction as in Subcase 1.c,
setting for each \(p\geq 1\),
\(A_p\) to be the vertex set of a complete bipartite graph \(K_{p,p}\),
and then to attach \(q=p^2\) pendant vertices to each vertex of \(K_{p,p}\),
with these \(p^2|A|\) pendant vertices forming the vertex set \(B_p\).
\(A_p\cup B_p\) is then an equitable vertex partition with the quotient matrix
\(\left[\begin{smallmatrix} p & p^2 \\ 1 & 0 \end{smallmatrix}\right]\), as requested,
thus proving part ) of Theorem 3.
Case 3: \(c+d-2< 0\), i.e., \((c,d)\in\{(0,0),(0,1),(1,0)\}\).
In this case
$$
\lim_{p\to\infty} \frac{\lambda_1}{p} = 1.
$$
The highest exponents appearing in the three sums of (7) are
$$
k-1,
k+c-2,
k+2c-3,
$$
respectively, obtained for the least feasible values of \(l\).
We can now distinguish the following subcases.
Subcase 3(a): \(c=0\).
The highest exponent is \(k-1\), appearing in the first sum for \(l=0\).
The corresponding coefficient is \({k-1\choose 0}=1\),
so
$$
\lim_{p\to\infty} \frac{w_{s+r}}{\lambda_1^r w_s}
= \lim_{p\to\infty} \frac{w_{s+r}}{p^{s+r-1}}
\frac{p^r}{\lambda_1^r}
\frac{p^{s-1}}{w_s}
= 1\cdot1\cdot1=1,
$$
which is not helpful for the Nikiforov’s problem.
Subcase 3(b): \(c=1\), hence \(d=0\).
The highest exponent is \(k-1\), appearing in the first sum for \(l=0\),
the second sum for \(l=1\) and the third sum for \(l=2\),
so the corresponding coefficient is
\({k-1\choose 0}+{k-2\choose 0}+{k-3\choose 0}=3\).
Hence
$$
\lim_{p\to\infty} \frac{w_{s+r}}{\lambda_1^r w_s}
= \lim_{p\to\infty} \frac{w_{s+r}}{p^{s+r-1}}
\frac{p^r}{\lambda_1^r}
\frac{p^{s-1}}{w_s}
= 3\cdot1\cdot\frac13=1,
$$
which again does not help with the Nikiforov’s problem.
This closes the discussion of cases when \(q\) and \(r\) are various powers of \(p\).
As a result, we see that it yields five different limit values that are larger than 1
for the Nikiforov’s ratio \(\frac{w_{s+r}}{\lambda_1^r w_s}\) for even \(s\) and even \(r\).
For each of these limit values,
one of many possible sequences of connected bipartite graphs that achieves the limit
has been constructed.
Acknowledgments
LF was supported by NSFC (No. 11671402, 11871479), Hunan Provincial Natural Science Foundation (2016JJ2138, 2018JJ2479) and
Mathematics and Interdisciplinary Sciences Project of CSU. DS was partly supported by Grant ON174033 of the Serbian Ministry of Education, Science and Technological Development.
Author Contributions
All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.
Conflicts of Interest:
The authors declare no conflict of interest.
