The Normalized Laplacians on Both Two Iterated Constructions Associated with Graph and Their Applications

Chang Liu, Yingui Pan, Jianping Li, Li Dai

College of Liberal Arts and Sciences, National University of Defense Technology, Changsha, China.

DOI: 10.4236/jamp.2020.85066                

Abstract

Given a simple connected graph G, we consider two iterated constructions associated with G: F^k (G) and R^k (G) . In this paper, we completely obtain the normalized Laplacian spectrum of F^k (G) and R^k (G) , with k ≥2, respectively. As applications, we derive the closed-formula of the multiplicative degree-Kirchhoff index, the Kemeny’s constant, and the number of spanning trees of F^k (G)  , R^k (G) , r-iterative graph ,F_r^k (G)  and r-iterative graph , where k ≥2 and r ≥1 . Our results extend those main results proposed by Pan et al. (2018), and we provide a method to characterize the normalized Laplacian spectrum of iteratively constructed complex graphs.

Keywords

Normalized Laplacian, Multiplicative Degree-Kirchhoff Index, Kemeny’s Con-stant, Spanning Tree

1. Introduction

Graph matrices, such as adjacency, incident, Laplacian and normalized Laplacian matrices, can well describe the structure and complex dynamic informations of complex networks. The eigenvalues and eigenvectors of these matrices represent some significant physical or chemical properties of networks. Recently, the normalized Laplacian has been a research hotpot, due to the consistency of eigenvalues in spectral geometry and random processes. Moreover, iteratively constructed graphs are very common in complex networks. Therefore, how to characterize the normalized Laplacian spectrum of such graphs is still a question worthy of study.

Let $G=(V(G),E(G))$ be a simple connected graph. $V(G)$ and $E(G)$ are called the order and the size of G, respectively. The adjacency matrix of G, denoted by $A(G)$, is an $n\times n$ matrix with the $(i,j)$ -entry equals to 1 if vertices $v_i$ and $v_j$ are adjacent ( $v_i\sim v_j$ ) and 0 otherwise. Let $D(G)=diag(d_1,d_2,\cdots d_n)$ be the diagonal matrix of vertex degrees, where $d_{v_i}$ is the degree of $v_i\in V(G)$ for $1\le i\le n$. The matrix $L(G)=D(G)-A(G)$ is called the (combinational) Laplacian matrix of G. Recent research on Laplace spectrum one can refer to [1] [2].

In 2007, Chen and Zhang [3] introduced a new resistance distance-based parameter, named the multiplicative degree-Kirchhoff index, defined as $Kf(G)={\displaystyle \underset{i<j}{\sum }{d}_{v_i}{d}_{v_j}{r}_{ij}}$. The multiplicative degree-Kirchhoff index is closely related to the normalized Laplacian matrix $\mathcal{L}(G)$, which is defined as

$\mathcal{L}(G)=D{(G)}^{-\frac{1}{2}}L(G)D{(G)}^{\frac{1}{2}}$ (If the degree of $v_i$ in graph G is equal to 0, then ${(d_{v_i})}^{-\frac{1}{2}}=0$ [4]. It’s easy to know that

$\mathcal{L}(G)=\{\begin{array}{cc}1,& \text{if}i=j\\ -\frac{1}{\sqrt{d_{v_i}{d}_{v_j}}},& \text{if}i\ne j\text{and}{v}_i\sim v_j\\ 0,& \text{otherwise}\end{array}.$ (1.1)

Let $S(G)=\{{\lambda }_1,{\lambda }_2,\cdots {\lambda }_n\}$ be the spectrum of $\mathcal{L}(G)$ with ${\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$. Let $p_{\mathcal{L}(G)}({\lambda }_i)$ be the multiplicity of eigenvalue ${\lambda }_i$ of $\mathcal{L}(G)$. If G is a connected graph, it is easy to conclude that ${\lambda }_1=0$ and ${\lambda }_i>0$ for $2\le i\le n$, and the explicit formula of multiplicative degree-Kirchhoff index of G can be written by [3]

$K{f}^{*}(G)=2|E(G)|{\displaystyle \underset{i=2}{\overset{n}{\sum }}\frac{1}{{\lambda }_i}}$ (1.2)

Hunter (2014) [5] studied the Kemeny’s constant of G, which is denoted by $Ke(G)$. The Kemmeny’s constant provides an interesting quantity for finite ergodic Markov chains and can be given by

$K{f}^{*}(G)=2|E(G)|Ke(G)$ (1.3)

In recent years, more and more researchers have been devoted to studying the normalized Laplacian spectra. Relevant research results on normalized Laplacian and multiplicative degree-Kirchhoff index one may refer to [6]-[11].

Now we consider two iterated constructions associated with G: $F^k(G)$ append k 3-cycles $T_i^l=u_{i_1}^l{u}_{i_2}^l{u}_{i_3}^l{u}_{i_1}^l$ ( $l=1,2,\cdots ,k$ ) parallel with each edge $e_i=u_{e_i}{v}_{e_i}$ of G, and then adding in edges $u_{e_i}{u}_{i_1}^l$ an $v_{e_i}{u}_{i_4}^l$, while $R^k(G)$ appends k 4-cycles $Q_i^l=u_{i_1}^l{u}_{i_2}^l{u}_{i_3}^l{u}_{i_4}^l{u}_{i_1}^l$ ( $l=1,2,\cdots ,k$ ) parallel with each edge $e_i=u_{e_i}{v}_{e_i}$, and then adding in edges $u_{e_i}{u}_{i_1}^l$ and $v_{e_i}{u}_{i_4}^l$. Two iterative graphs are shown in Figure 1.

Motivated by [7] [10], in this paper, we completely obtain the normalized Laplacian spectrum of $F^k(G)$ and $R^k(G)$, respectively, where $k\ge 2$. As applications, we derive the closed-formula of the multiplicative degree-Kirchhoff index, the Kemeny’s constant, and the number of spanning trees of $F^k(G)$, $R^k(G)$, r-iterative graph $F_r^k(G)$, and r-iterative graph $R_r^k(G)$, where $k\ge 2$ and $r\ge 1$.

2. Main Results

In this section, we will give the main conclusions of this paper.

Theorem 2.1. Let G be a simple connected graph with n vertices and m edges. Then the normalized Laplacian eigenvalues of $F^k(G)$ ( $k\ge 2$ ) can be obtained as following:

(i) If $\lambda$ is an eigenvalue of $\mathcal{L}(G)$ such that $\lambda \ne 0,2$, then ${\sigma }_1,{\sigma }_2,{\sigma }_3$ and ${\sigma }_4$ are the eigenvalues of $\mathcal{L}(F^k(G))$ with $p_{\mathcal{L}(F^k(G))}({\sigma }_1)=p_{\mathcal{L}(F^k(G))}({\sigma }_2)=p_{\mathcal{L}(F^k(G))}({\sigma }_3)=p_{\mathcal{L}(F^k(G))}({\sigma }_4)=p_{\mathcal{L}(G)}(\lambda )$, where ${\sigma }_1$, ${\sigma }_2$, ${\sigma }_3$ and ${\sigma }_4$ are roots of

$\begin{array}{l}18(k+1){\sigma }^4-(72k+18\lambda +54){\sigma }^3+(94k+54\lambda +46){\sigma }^2\\ -(40k+46\lambda +2k\lambda +8)\sigma +(3k+8)\lambda =0.\end{array}$

(ii) 0, $\frac{8k+\sqrt{4k^2+8k+13}+5}{6(k+1)}$ and $\frac{8k-\sqrt{4k^2+8k+13}+5}{6(k+1)}$ are the eigenvalues of $\mathcal{L}(F^k(G))$ with multiplicity 1.

(iii) $\frac{7k+\sqrt{13k^2+8k+4}+10}{6(k+1)}$ and $\frac{7k-\sqrt{13k^2+8k+4}+10}{6(k+1)}$ are the eigenvalues of $\mathcal{L}(F^k(G))$ with multiplicity 1 if G is bipartite and 0 otherwise.

(iv) If G is non-bipartite, then $\mathcal{L}(F^k(G))$ has eigenvalues $\frac{5+\sqrt{13}}{6}$ with multiplicity $km-n$, $\frac{5-\sqrt{13}}{6}$ with multiplicity $km-n$ and $\frac{4}{3}$ with multiplicity $km-n+1$.

(v) If G is bipartite, then $\mathcal{L}(F^k(G))$ has eigenvalues $\frac{5+\sqrt{13}}{6}$ with multiplicity

Figure 1. Graph $F^k(P_3)$ and $R^k(P_3)$.

$km-n+1$, $\frac{5-\sqrt{13}}{6}$ with multiplicity $km-n+1$ and $\frac{4}{3}$ with multiplicity $km-n+1$.

Theorem 2.2. Let G be a simple connected graph with n vertices and m edges. Then the normalized Laplacian eigenvalues of $R^k(G)$ ( $k\ge 2$ ) can be obtained as following:

(i) If $\lambda$ is an eigenvalue of $\mathcal{L}(G)$ such that $\lambda \ne 0,2$, then ${\mu }_1$, ${\mu }_2$, ${\mu }_3$ and ${\mu }_4$ are the eigenvalues of $\mathcal{L}(R^k(G))$ with $p_{\mathcal{L}(R^k(G))}({\mu }_1)=p_{\mathcal{L}(R^k(G))}({\mu }_2)=p_{\mathcal{L}(R^k(G))}({\mu }_3)=p_{\mathcal{L}(R^k(G))}({\mu }_4)=p_{\mathcal{L}(G)}(\lambda )$, where ${\mu }_1$, ${\mu }_2$, ${\mu }_3$ and ${\mu }_4$ are roots of

$\begin{array}{l}9(k+1){\mu }^4-(36k+9\lambda +27){\mu }^3+(45k+27\lambda +21){\mu }^2\\ -(18k+21\lambda +3)\mu +(k+3)\lambda =0\end{array}$.

(ii) 0, $\frac{9k+\sqrt{3}\sqrt{3k^2+8k+8}+6}{6(k+1)}$ and $\frac{9k-\sqrt{3}\sqrt{3k^2+8k+8}+6}{6(k+1)}$ are the eigenvalues of $\mathcal{L}(R^k(G))$ with multiplicity 1.

(iii) $\frac{6k+\sqrt{3}\sqrt{4k^2+4k+3}+9}{6(k+1)}$ and $\frac{6k-\sqrt{3}\sqrt{4k^2+4k+3}+9}{6(k+1)}$ are the eigenvalues of $\mathcal{L}(R^k(G))$ with multiplicity 1 if G is bipartite and 0 otherwise.

(iv) If G is non-bipartite, then $\mathcal{L}(R^k(G))$ has eigenvalues $\frac{3+\sqrt{6}}{3}$ with multiplicity $km-n$, $\frac{3-\sqrt{6}}{3}$ with multiplicity $km-n$ and 1 with multiplicity $2km-n+1$.

(v) If G is bipartite, then $\mathcal{L}(R^k(G))$ has eigenvalues $\frac{3+\sqrt{6}}{3}$ with multiplicity $km-n+1$, $\frac{3-\sqrt{6}}{3}$ with multiplicity $km-n+1$ and 1 with multiplicity $2km-n+1$.

3. Preliminaries

Before you begin to format your paper, first write and save the content as a separate text file. Let G be a connected graph with n vertices and m edges, the order of $F^k(G)$ is $n+3km$ and its size is $(5k+1)m$. Similarly, the order of $R^k(G)$ is $n+4km$ and its size is $(6k+1)m$. Let

$\begin{array}{l}0={\lambda }_1<{\lambda }_2\le \cdots \le {\lambda }_n,\\ 0={\sigma }_1<{\sigma }_2\le \cdots \le {\sigma }_{n+3km},\\ 0={\mu }_1<{\mu }_2\le \cdots \le {\mu }_{n+4km}.\end{array}$

be all the normalized Laplacian eigenvalues of G, $F^k(G)$ and $R^k(G)$, respectively.

The incident matrix $I(G)$ of G is an $n\times m$ matrix $(b_{ij})$ with the $(i,j)$ -entry equals to 1 if the vertex $v_i$ and the edge $e_j$ are incident in G and 0 otherwise, The rank of incident matrix $I(G)$ is written by $r(I(G))$. Then we have the following lemma.

Lemma 3.1. [12] Let G be a simple connected graph with n vertices, then

$r(I(G))=\{\begin{array}{cc}n-1,& \text{if}G\text{is}\text{bipartite,}\\ n,& \text{otherwise}\text{.}\end{array}$

If G is a connected oriented graph, the directed incident matrix of G, called $\stackrel{\to }{I}(G)$, is an $n\times m$ matrix. The rank of the directed incident matrix $\stackrel{\to }{I}(G)$ satisfies the following lemma.

Lemma 3.2. [13] Let G be a simple connected graph with n vertices. Then

$r(\stackrel{\to }{I}(G))=n-1.$

The following lemmas provide the calculation formula of the multiplicative degree-Kirhhoff index, the Kemeny’s constant and the number of spanning trees of graph G, based on the normalized Laplacian spectrum.

Lemma 3.3. [4] Let G be a graph with n vertices and m edges.

(i) $\frac{n}{n-1}\le {\lambda }_n\le 2$ with ${\lambda }_n=2$ if and only if G is bipartite.

(ii) G is bipartite if and only if the eigenvalues of $\mathcal{L}(G)$ are symmetric with respect to 1.

(iii) ${\displaystyle {\prod }_{i=1}^n{d}_i}{\displaystyle {\prod }_{k=2}^n{\lambda }_k}=2m\tau (G)$, where $\tau (G)$ is the number of spanning trees of G.

Lemma 3.4. [3] If G is a n-vertices graph of size m. Then

$K{f}^{*}(G)=2m{\displaystyle {\sum }_{i=2}^n\frac{1}{{\lambda }_i}}$.

Lemma 3.5. [14] Let G be a simple connected graph with n vertices and m edges, then we have

$Ke(G)={\displaystyle {\sum }_{i=2}(1/{\lambda }_i)},K{f}^{*}(G)=2mKe(G).$

Lemma 3.6. Let $\sigma$ be an eigenvalue of $\mathcal{L}(F^k(G))$ such that $\sigma \ne \frac{4}{3},\frac{5\pm \sqrt{13}}{6}$. Then

$\frac{\sigma [18(k+1){\sigma }^3-(72k+54){\sigma }^2+(94k+46)\sigma -(40k+8)]}{18{\sigma }^3-54{\sigma }^2+(46+2k)\sigma -(3k+8)}$ (3.1)

is an eigenvalue of $\mathcal{L}(G)$ with the same multiplicity as that of $\sigma$.

Proof. Let $E(G)=\{e_1,e_2,\cdots ,e_m\}$ and $V(F^k(G))=V\cup F$, where V is a set of common vertices of G and $F^k(G)$ (i.e. $V=V(G)\cap V(F^k(G))$ ), and F is the rest vertices of $V(F^k(G))$. For each edge $e_i=uv\in E(G)$, k 3-cycles are added between the vertices u, v. Denote these 3-cycles by $T_i^l=u_{i_1}^l{u}_{i_2}^l{u}_{i_3}^l{u}_{i_1}^l$. Let $F_j^l=\{u_{1_j}^l,u_{2_j}^l,\cdots ,u_{m_j}^l\}$ ( $j=1,2,3;l=1,2,\cdots ,k$ ). We have

$F={\displaystyle \underset{l=1}{\overset{k}{\cup }}{\displaystyle \underset{j=1}{\overset{3}{\cup }}{F}_j^l}}$

Denote the degree of vertex w in $F^k(G)$ by $d_w^{\text{'}}$, then

$d_w^{\text{'}}=\{\begin{array}{cc}(k+1)d_w,& w\in V\\ 3,& w\in F_1\cup F_3\\ 2,& w\in F_2\end{array}$ (3.2)

Let $x={(x_1,x_2,\cdots ,x_{n+3km})}^t$ be an eigenvector with respect to the eigenvalue $\sigma$ of $\mathcal{L}(F^k(G))$. According to the characteristic equation $\mathcal{L}(F^k(G))x=\sigma x$, we can obtain that

$(1-\sigma )x_w={\displaystyle \underset{v\sim w}{\sum }\frac{1}{\sqrt{d_v^{\text{'}}{d}_w^{\text{'}}}}}{x}_v$ (3.3)

for any vertex $w\in V(F^k(G))$.

For any vertex $u\in V$, let $N_G(u)$ be the set of the neighbour of vertex u inherited from G. According to the construction of $F^k(G)$ from G and (3.2) and (3.3), we can get

$\begin{array}{c}(1-\sigma )x_u={\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in F_1^l(u)}{\sum }\frac{1}{\sqrt{d_{u_{i_1}^l}^{\text{'}}{d}_u^{\text{'}}}}}}{x}_{u_{i_1}^l}+{\displaystyle \underset{v\in N_G(u)}{\sum }\frac{1}{\sqrt{d_u^{\text{'}}{d}_v^{\text{'}}}}}{x}_v\\ ={\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in F_1^l(u)}{\sum }\frac{1}{\sqrt{3(k+1)d_u}}}}{x}_{u_{i_1}^l}+{\displaystyle \underset{v\in N_G(u)}{\sum }\frac{1}{(k+1)\sqrt{d_u{d}_v}}}{x}_v.\end{array}$ (3.4)

Similarly, for any $u_{i_1}^l\in F_1^l$,

$\begin{array}{c}(1-\sigma )x_{u_{i_1}^l}=\frac{1}{\sqrt{d_{u_{i_1}^l}^{\text{'}}{d}_{u_{i_2}^l}^{\text{'}}}}{x}_{u_{i_2}^l}+\frac{1}{\sqrt{d_{u_{i_1}^l}^{\text{'}}{d}_{u_{i_3}^l}^{\text{'}}}}{x}_{u_{i_3}^l}+\frac{1}{\sqrt{d_{u_{i_1}^l}^{\text{'}}{d}_u^{\text{'}}}}{x}_u\\ =\frac{1}{\sqrt{6}}{x}_{u_{i_1}^l}+\frac{1}{3}{x}_{u_{i_3}^l}+\frac{1}{\sqrt{3(k+1)d_u}}{x}_u.\end{array}$ (3.5)

Analogously, for the vertex $u_{i_2}^l\in F_2^l$,

$(1-\sigma )x_{u_{i_2}^l}=\frac{1}{\sqrt{d_{u_{i_1}^l}^{\text{'}}{d}_{u_{i_2}^l}^{\text{'}}}}{x}_{u_{i_1}^l}+\frac{1}{\sqrt{d_{u_{i_2}^l}^{\text{'}}{d}_{u_{i_3}^l}^{\text{'}}}}{x}_{u_{i_3}^l}\text{=}\frac{1}{\sqrt{6}}{x}_{u_{i_1}^l}+\frac{1}{\sqrt{6}}{x}_{u_{i_3}^l}.$ (3.6)

For the vertex $u_{i_3}^l$ which is adjacent to $u_{i_1}^l$, $u_{i_3}^l\in V(T_i^l)$ and $v\in N_G(u)$,

$\begin{array}{c}(1-\sigma )x_{u_{i_3}^l}=\frac{1}{\sqrt{d_{u_{i_1}^l}^{\text{'}}{d}_{u_{i_3}^l}^{\text{'}}}}{x}_{u_{i_1}^l}+\frac{1}{\sqrt{d_{u_{i_2}^l}^{\text{'}}{d}_{u_{i_3}^l}^{\text{'}}}}{x}_{u_{i_2}^l}\text{+}\frac{1}{\sqrt{d_{u_{i_3}^l}^{\text{'}}{d}_v^{\text{'}}}}{x}_v\\ =\frac{1}{\sqrt{6}}{x}_{u_{i_2}^l}+\frac{1}{3}{x}_{u_{i_3}^l}+\frac{1}{\sqrt{3(k+1)d_v}}{x}_v.\end{array}$ (3.7)

Combining (3.5)-(3.7), we can have

$[{(1-\sigma )}^2-\frac{1}{6}]x_{u_{i_1}^l}=\frac{1-\sigma }{\sqrt{3(k+1)d_u}}{x}_u+\frac{3-2\sigma }{6}{x}_{u_{i_3}^l},$

$[{(1-\sigma )}^2-\frac{1}{6}]x_{u_{i_3}^l}=\frac{3-2\sigma }{\sqrt{3(k+1)d_u}}{x}_u+\frac{1-\sigma }{6}{x}_{u_{i_1}^l}.$

Then

$2(4-3\sigma )(3{\sigma }^2-5\sigma +1)x_{u_{i_1}^l}=\frac{3(6{\sigma }^2-12\sigma +5)}{\sqrt{3(k+1)d_u}}{x}_u+\frac{3(3-2\sigma )}{\sqrt{3(k+1)d_v}}{x}_v,$ (3.8)

Similarly,

$2(4-3\sigma )(3{\sigma }^2-5\sigma +1)x_{u_{i_3}^l}=\frac{3(3-2\sigma )}{\sqrt{3(k+1)d_u}}{x}_u+\frac{3(6{\sigma }^2-12\sigma +5)}{\sqrt{3(k+1)d_v}}{x}_v.$ (3.9)

According to (3.8), (3.9), we can get that

$x_{u_{i_1}^1}=x_{u_{i_1}^2}=\cdots =x_{u_{i_1}^k},x_{u_{i_3}^1}=x_{u_{i_3}^2}=\cdots =x_{u_{i_3}^k}.$

for any $\sigma \ne \frac{4}{3},\frac{5\pm \sqrt{13}}{6}$.

Substituting (3.8) into (3.5) yields

$\begin{array}{l}2(1-\sigma )(4-3\sigma )(3{\sigma }^2-5\sigma +1)x_u\\ =\frac{k(6{\sigma }^2-12\sigma +5)}{(k+1)}{x}_u+\frac{k(3-2\sigma )+2(4-3\sigma )(3{\sigma }^2-5\sigma +1)}{k+1}{\displaystyle \underset{v\in N_G(u)}{\sum }\frac{1}{\sqrt{d_u{d}_v}}}{x}_v.\end{array}$ (3.10)

If $k(3-2\sigma )+2(4-3\sigma )(3{\sigma }^2-5\sigma +1)=0$, then

$[2(k+1)(1-\sigma )(4-3\sigma )(3{\sigma }^2-5\sigma +1)-k(6{\sigma }^2-12\sigma +5)]x_u=0$.

The eigenvector $x$ can be completely decided by $x_0={(x_u)}_{u\in V}^t$, when $\sigma \ne \frac{4}{3},\frac{5\pm \sqrt{13}}{6}$ and

$[2(k+1)(1-\sigma )(4-3\sigma )(3{\sigma }^2-5\sigma +1)-k(6{\sigma }^2-12\sigma +5)]x_u\ne 0$.

Let $k(3-2\sigma )+2(4-3\sigma )(3{\sigma }^2-5\sigma +1)=0$ and

$[2(k+1)(1-\sigma )(4-3\sigma )(3{\sigma }^2-5\sigma +1)-k(6{\sigma }^2-12\sigma +5)]x_u=0$,

then we have

$k=-\frac{2(4-\sigma )(3{\sigma }^2-5\sigma +1)}{3-2\sigma }=-\frac{8{\sigma }^2-17\sigma +8}{(3-2\sigma )(1-\sigma )}.$ (3.11)

Then we have $\sigma (18{\sigma }^3-17{\sigma }^2+92\sigma -37)=0$. Since k is a integer ( $k\ge 2$ ), combining with (3.11), it is easy to conclude that the above equation does not hold. Thus,

$k(3-2\sigma )+2(4-3\sigma )(3{\sigma }^2-5\sigma +1)\ne 0.$

Then we can obtain that

$\begin{array}{l}\left\{\text{1}-\frac{\sigma [18(k+1){\sigma }^3-(72k+54){\sigma }^2+(94k+46)\sigma -(40k+8)]}{18{\sigma }^3-54{\sigma }^2+(46+2k)\sigma -(3k+8)}\right\}{x}_u\\ ={\displaystyle \underset{v\in N_G(u)}{\sum }\frac{1}{\sqrt{d_u{d}_v}}}{x}_v\end{array}$ (3.12)

for $\sigma \ne \frac{4}{3},\frac{5\pm \sqrt{13}}{6}$.

So, $\frac{\sigma [18(k+1){\sigma }^3-(72k+54){\sigma }^2+(94k+46)\sigma -(40k+8)]}{18{\sigma }^3-54{\sigma }^2+(46+2k)\sigma -(3k+8)}$ is an eigenvalue of $\mathcal{L}(G)$ and $x_0={(x_u)}_{u\in V}^t$ is one of the corresponding eigenvectors. Hence,

$p_{\mathcal{L}(G)}\left(\frac{\sigma [18(k+1){\sigma }^3-(72k+54){\sigma }^2+(94k+46)\sigma -(40k+8)]}{18{\sigma }^3-54{\sigma }^2+(46+2k)\sigma -(3k+8)}\right)\ge p_{\mathcal{L}(F^k(G))}(\sigma ).$

If

$p_{\mathcal{L}(G)}\left(\frac{\sigma [18(k+1){\sigma }^3-(72k+54){\sigma }^2+(94k+46)\sigma -(40k+8)]}{18{\sigma }^3-54{\sigma }^2+(46+2k)\sigma -(3k+8)}\right)>p_{\mathcal{L}(F^k(G))}(\sigma ),$

then there exists an eigenvector $x_0^{\text{'}}$ with respect to

$\frac{\sigma [18(k+1){\sigma }^3-(72k+54){\sigma }^2+(94k+46)\sigma -(40k+8)]}{18{\sigma }^3-54{\sigma }^2+(46+2k)\sigma -(3k+8)}$

without a corresponding eigenvector in $\mathcal{L}(F^k(G))$. Combining the (3.5) and (3.8), we can get

$p_{\mathcal{L}(G)}\left(\frac{\sigma [18(k+1){\sigma }^3-(72k+54){\sigma }^2+(94k+46)\sigma -(40k+8)]}{18{\sigma }^3-54{\sigma }^2+(46+2k)\sigma -(3k+8)}\right)=p_{\mathcal{L}(F^k(G))}(\sigma ).$

This completes the proofs.

Lemma 3.7. Let $\mu$ be an eigenvalue of $\mathcal{L}(R^k(G))$ such that $\mu \ne 1,\frac{3\pm \sqrt{6}}{3}$. Then

$\frac{3\mu [3(k+1){\mu }^3-(12k+9){\mu }^2+(15k+7)\mu -(6k+1)]}{9{\mu }^3-27{\mu }^2+21\mu -(k+3)}$ (3.13)

is an eigenvalue of $\mathcal{L}(G)$ with the same multiplicity as that of $\mu$.

Proof. Let $E(G)=\{e_1,e_2,\cdots ,e_m\}$ and $V(R^k(G))=O\cup R$, where O is a set of all the vertices of inherited from G, and R is the rest vertices of $V(R^k(G))$. For each edge $e_i=uv\in E(G)$, k 4-cycles are added between the vertices $u,v$. Denote these 4-cycles by $Q_i^l=u_{i_1}^l{u}_{i_2}^l{u}_{i_3}^l{u}_{i_4}^l{u}_{i_1}^l$.

Then we let $R_j^l=\{u_{1_j}^l,u_{2_j}^l,\cdots ,u_{m_j}^l\}$ ( $j=1,2,3,4;l=1,2,\cdots ,k$ ). Then we have

$R={\displaystyle \underset{l=1}{\overset{k}{\cup }}{\displaystyle \underset{j=1}{\overset{4}{\cup }}{R}_j^l}}.$

The degree of vertex u in $R^k(G)$ is denoted by $d_u^{\text{'}}$, then

$d_u^{\text{'}}=\{\begin{array}{cc}(k+1)d_u,& u\in O\\ 3,& u\in R_1\cup R_4\\ 2,& u\in R_2\end{array}.$ (3.14)

Suppose $x_0={(x_1,x_2,\cdots ,x_{n+4m})}^t$ is an eigenvector with respect to the eigenvalue $\mu$ of $\mathcal{L}(R^k(G))$. Based on the characteristic equation $\mathcal{L}(R^k(G))x=\mu x$, we can obtain

$(1-\mu )x_u={\displaystyle \underset{v\sim u}{\sum }\frac{1}{\sqrt{d_v^{\text{'}}{d}_u^{\text{'}}}}}{x}_v$ (3.15)

for any vertex $u\in V(R^k(G))$.

For any vertex $u\in O$, let $N_G(u)$ be the set of the neighbour of vertex u inherited from G. According to the structural of $R^k(G)$ from G, (3.14) and (3.15), we can get

$\begin{array}{l}(1-\mu )={\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in R_1^l}{\sum }\frac{1}{\sqrt{d_{u_{i_1}^l}^{\text{'}}{d}_u^{\text{'}}}}}}{x}_{u_{i_1}^l}+{\displaystyle \underset{v\in N_G(u)}{\sum }\frac{1}{\sqrt{d_u^{\text{'}}{d}_v^{\text{'}}}}}{x}_v\\ ={\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in R_1^l}{\sum }\frac{1}{\sqrt{3(k+1)d_u}}}}{x}_{u_{i_1}^l}+{\displaystyle \underset{v\in N_G(u)}{\sum }\frac{1}{(k+1)\sqrt{d_u{d}_v}}}{x}_v.\end{array}$ (3.16)

Similarly, for any $u_{i_1}^l\in R_1^l$, we have

$\begin{array}{l}(1-\mu )x_{u_{i_1}^l}=\frac{1}{\sqrt{d_{u_{i_1}^l}^{\text{'}}{d}_{u_{i_2}^l}^{\text{'}}}}{x}_{u_{i_2}^l}+\frac{1}{\sqrt{d_{u_{i_1}^l}^{\text{'}}{d}_{u_{i_3}^l}^{\text{'}}}}{x}_{u_{i_3}^l}+\frac{1}{\sqrt{d_{u_{i_1}^l}^{\text{'}}{d}_u^{\text{'}}}}{x}_u\\ =\frac{1}{\sqrt{6}}{x}_{u_{i_1}^l}+\frac{1}{\sqrt{6}}{x}_{u_{i_3}^l}+\frac{1}{\sqrt{3(k+1)d_u}}{x}_u.\end{array}$ (3.17)

Analogously, for the vertex $u_{i_2}^l\in R_2^l$ and $u_{i_3}^l\in R_3^l$,

$(1-\mu )x_{u_{i_2}^l}=\frac{1}{\sqrt{d_{u_{i_1}^l}^{\text{'}}{d}_{u_{i_2}^l}^{\text{'}}}}{x}_{u_{i_1}^l}+\frac{1}{\sqrt{d_{u_{i_4}^l}^{\text{'}}{d}_{u_{i_2}^l}^{\text{'}}}}{x}_{u_{i_4}^l}=\frac{1}{\sqrt{6}}{x}_{u_{i_1}^l}+\frac{1}{\sqrt{6}}{x}_{u_{i_4}^l},$ (3.18)

$(1-\mu )x_{u_{i_3}^l}=\frac{1}{\sqrt{d_{u_{i_1}^l}^{\text{'}}{d}_{u_{i_3}^l}^{\text{'}}}}{x}_{u_{i_1}^l}+\frac{1}{\sqrt{d_{u_{i_4}^l}^{\text{'}}{d}_{u_{i_3}^l}^{\text{'}}}}{x}_{u_{i_4}^l}=\frac{1}{\sqrt{6}}{x}_{u_{i_1}^l}+\frac{1}{\sqrt{6}}{x}_{u_{i_4}^l}.$ (3.19)

For the vertices $u_{i_4}^l\in R_4^l$ and $v\in N_G(u)$, it follows

$\begin{array}{l}(1-\mu )x_{u_{i_4}^l}=\frac{1}{\sqrt{d_{u_{i_4}^l}^{\text{'}}{d}_{u_{i_2}^l}^{\text{'}}}}{x}_{u_{i_2}^l}+\frac{1}{\sqrt{d_{u_{i_4}^l}^{\text{'}}{d}_{u_{i_3}^l}^{\text{'}}}}{x}_{u_{i_3}^l}+\frac{1}{\sqrt{d_{u_{i_4}^l}^{\text{'}}{d}_v^{\text{'}}}}{x}_v\\ =\frac{1}{\sqrt{6}}{x}_{u_{i_1}^l}+\frac{1}{\sqrt{6}}{x}_{u_{i_3}^l}+\frac{1}{\sqrt{3(k+1)d_v}}{x}_v.\end{array}$ (3.20)

In view of the formulas (3.18)-(3.19), one can see that $x_{u_{i_2}^l}=x_{u_{i_3}^l}$, with $i=1,2,\cdots ,m$ ; $l=1,2,\cdots ,k$.

Combining (3.17)-(3.20), we can get

$(1-\mu )(3{\mu }^2-6\mu +1)x_{u_{i_1}^l}=\frac{(3{\mu }^2-6\mu +2)}{\sqrt{3(k+1)d_u}}{x}_u+\frac{1}{\sqrt{3(k+1)d_v}}{x}_v,$ (3.21)

$(1-\mu )(3{\mu }^2-6\mu +1)x_{u_{i_4}^l}=\frac{1}{\sqrt{3(k+1)d_u}}{x}_u+\frac{(3{\mu }^2-6\mu +2)}{\sqrt{3(k+1)d_v}}{x}_v.$ (3.22)

According to (3.21) and (3.22), we have

$x_{u_{i_1}^1}=x_{u_{i_1}^2}=\cdots =x_{u_{i_1}^k},x_{u_{i_4}^1}=x_{u_{i_4}^2}=\cdots =x_{u_{i_4}^k}.$

for any $\mu \ne 1,\frac{3\pm \sqrt{6}}{3}$.

Substituting (3.21) into (3.16), then we have

$\begin{array}{l}[{(}^1(3{\mu }^2-6\mu +1)]x_u\\ =\frac{k(3{\mu }^2-6\mu +2)}{3(k+1)}{x}_u+\frac{k+3(1-\mu )(3{\mu }^2-6\mu +1)}{3(k+1)}{\displaystyle \underset{v\in N_G(u)}{\sum }\frac{1}{\sqrt{d_u{d}_v}}}{x}_v.\end{array}$ (3.23)

If $k+3(1-\mu )(3{\mu }^2-6\mu +1)=0$, then

$[3(k+1){(1-\mu )}^2(3{\mu }^2-6\mu +1)-k(3{\mu }^2-6\mu +2)]x_u=0$. The eigenvector $x$ can be completely decided by $x_0={(x_u)}_{u\in O}^t$, when $\mu \ne 1,\frac{3\pm \sqrt{6}}{3}$ and $3(k+1){(1-\mu )}^2(3{\mu }^2-6\mu +1)-k(3{\mu }^2-6\mu +2)\ne 0$.

Let $k+3(1-\mu )(3{\mu }^2-6\mu +1)=0$ and $3(k+1){(1-\mu )}^2(3{\mu }^2-6\mu +1)-k(3{\mu }^2-6\mu +2)=0$, which implies that

$k=\frac{3{\mu }^2-7\mu +3}{\mu -1}=3(\mu -1)(3{\mu }^2-6\mu +1).$ (3.24)

Then we have $\mu (9{\mu }^3-36{\mu }^2+45\mu -17)=0$. Since k is a integer ( $k\ge 2$ ), combining (3.24), we can know that the above equation does not hold. Hence $k+3(1-\mu )(3{\mu }^2-6\mu +1)\ne 0$.

Then

$\left\{1-\frac{3\mu [3(k+1){\mu }^3-(12k+9){\mu }^2+(15k+7)\mu -(6k+1)]}{9{\mu }^3-27{\mu }^2+21\mu -(k+3)}\right\}{x}_u={\displaystyle \underset{v\in N_G(u)}{\sum }\frac{1}{\sqrt{d_u{d}_v}}}{x}_v$. (3.25)

for $\mu \ne 1,\frac{3\pm \sqrt{6}}{3}$.

So, $\frac{3\mu [3(k+1){\mu }^3-(12k+9){\mu }^2+(15k+7)\mu -(6k+1)]}{9{\mu }^3-27{\mu }^2+21\mu -(k+3)}$ is an eigenvalue of $\mathcal{L}(G)$ and $x_0={(x_u)}_{u\in O}^t$ is one of the corresponding eigenvectors. Hence,

$p_{\mathcal{L}(G)}\left(\frac{3\mu [3(k+1){\mu }^3-(12k+9){\mu }^2+(15k+7)\mu -(6k+1)]}{9{\mu }^3-27{\mu }^2+21\mu -(k+3)}\right)\ge p_{\mathcal{L}(R^k(G))}(\mu ).$

If the inequality is strictly established, then there exists an eigenvector $x_0^{\text{'}}$ with respect to $\frac{3\mu [3(k+1){\mu }^3-(12k+9){\mu }^2+(15k+7)\mu -(6k+1)]}{9{\mu }^3-27{\mu }^2+21\mu -(k+3)}$ without a corresponding eigenvector in $\mathcal{L}(R^k(G))$. Combining (3.5)-(3.8), it is easy to know that

$p_{\mathcal{L}(G)}\left(\frac{3\mu [3(k+1){\mu }^3-(12k+9){\mu }^2+(15k+7)\mu -(6k+1)]}{9{\mu }^3-27{\mu }^2+21\mu -(k+3)}\right)=p_{\mathcal{L}(R^k(G))}(\mu ).$

This completes the proofs.

4. Proofs of Theorems 2.1 and 2.2

4.1. Proof of Theorem 2.1

Proof. (i)-(iii) Let $\sigma$ be an eigenvalue of $\mathcal{L}(F^k(G))$ with $\sigma \ne \frac{4}{3},\frac{5\pm \sqrt{13}}{6}$. According to Lemma 3.6, one can see that

$\lambda =\frac{\sigma [18(k+1){\sigma }^3-(72k+54){\sigma }^2+(94k+46)\sigma -(40k+8)]}{18{\sigma }^3-54{\sigma }^2+(46+2k)\sigma -(3k+8)}$ (4.1)

is an eigenvalue of $\mathcal{L}(G)$ with the same multiplicity as that of $\sigma$. Then we have

$\begin{array}{l}18(k+1){\sigma }^4-(72k+18\lambda +54){\sigma }^3+(94k+54\lambda +46){\sigma }^2\\ -(40k+46\lambda +2k\lambda +8)\sigma +(3k+8)\lambda =0.\end{array}$ (4.2)

Note that ${\lambda }_1=0$ is an eigenvalue of $\mathcal{L}(G)$, then we substitute $\lambda =0$ into (4.2) yields $\sigma =0,\frac{4}{3}$ and $\frac{8k\pm \sqrt{4k^2+8k+13}+5}{6(k+1)}$. If G is bipartite, substituting $\lambda =2$ into (4.2) yields $\sigma =\frac{5\pm \sqrt{13}}{6},\frac{7k+\sqrt{13k^2+8k+4}+10}{6(k+1)}.$

Combining Lemma 3.3, this completes proofs of (i) to (iii).

(iv) Substituting $\sigma =\frac{5-\sqrt{13}}{6}$ into (3.8) yields

$\frac{1}{\sqrt{d_u}}{x}_u=-\frac{1}{\sqrt{d_v}}{x}_v.$ (4.3)

Since the connected simple graph G is non-bipartite, G contains an odd cycle, written by $C_0$. By (4.3), we have $\frac{x_u}{\sqrt{d_u}}={(-1)}^{|V(C_0)|}\frac{x_u}{\sqrt{d_u}}=-\frac{x_u}{\sqrt{d_u}}$. Then we can obtain $x_u=x_v=0$ for $u\sim v$. It is clear that $x_u=0$ for all $u\in V(G)$. Combining (3.4)-(3.7), then we can get

$\{\begin{array}{l}{x}_{u_{i_1}^l}=x_{u_{i_3}^l},\forall u_{i_1}^l\in F_1^l,\forall u_{i_3}^l\in F_3^l\\ x_{u_{i_2}^l}=\frac{\sqrt{78}-\sqrt{6}}{6}{x}_{u_{i_1}^l},\forall u_{i_2}^l\in F_2^l\\ x_u=0,\forall u\in V\\ {\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in F_1^u}{\sum }\frac{1}{\sqrt{3(k+1)d_u}}{x}_{u_{i_1}^l}=0,\forall u\in V}}\end{array}$ (4.4)

Let $x_{u_{i_1}^l}=x_{u_{i_3}^l}=y_i^l$, with $i=1,2,\cdots ,m$ and $l=1,2,\cdots ,k$, then we have $x_{u_{i_2}^l}=\frac{\sqrt{78}-\sqrt{6}}{6}{y}_i^l$. Let

$y={(y_1^1,y_2^1,\cdots ,y_m^1,\cdots ,y_1^k,y_2^k,\cdots ,y_m^k)}_{km}^t$.

Note that ${\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in F_1^u}{\sum }\frac{1}{\sqrt{3(k+1)d_u}}{x}_{u_{i_1}^l}=0}}$, $\forall u\in V$. Let $W(G)={[I(G),I(G),\cdots ,I(G)]}_{n\times km}$, then we have

$W(G)y=0.$ (4.5)

According to Lemma 3.1, one can see that $r(W(G))=r(I(G))=n$. System (4.5) has exactly $km-n+1$ linearly independent solutions. It is easy to know that $p_{\mathcal{L}(F^k(G))}(\frac{5-\sqrt{13}}{6})=km-n$. Similarly, substituting $\sigma =\frac{5+\sqrt{13}}{6}$ into (3.8), we can get $p_{\mathcal{L}(F^k(G))}(\frac{5+\sqrt{13}}{6})=km-n$. Hence $p_{\mathcal{L}(F^k(G))}(\frac{4}{3})=km-n+1$ by counting the number of the eigenvalues of $F^k(G)$.

This completes the proofs of (iv).

(v) Substituting $\sigma =\frac{4}{3}$ into (3.8) yields that

$\frac{x_u}{\sqrt{d_u}}=\frac{x_v}{\sqrt{d_v}}.$ (4.6)

Assume $\frac{x_u}{\sqrt{d_u}}=\frac{x_v}{\sqrt{d_v}}=t$. Combining with (3.6), we have

$x_{u_{i_2}^l}=-\frac{\sqrt{6}}{2}(x_{u_{i_1}^l}+x_{u_{i_3}^l}).$ (4.7)

In view of (3.5) and (4.7), then

$x_{u_{i_1}^l}+x_{u_{i_3}^l}=\sqrt{\frac{12}{k+1}}\cdot t$ (4.8)

According to (3.4),

${\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in F_1^l}{\sum }{x}_{u_{i_1}^l}}}=-\frac{k+4}{\sqrt{3(k+1)}}{d}_{u}t.$ (4.9)

Combining (4.8) and (4.9), then

${\displaystyle \underset{u\in V}{\sum }{\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in F_1^l}{\sum }{x}_{u_{i_1}^l}}={\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{e_i\in E(G)}{\sum }(x_{u_{i_1}^l}+x_{u_{i_3}^l})}}}}={\displaystyle \underset{u\in V}{\sum }-\frac{k+4}{\sqrt{3(k+1)}}{d}_{u}t.}$ (4.10)

Combining (4.8) and (4.10), we have $k\sqrt{\frac{12}{k+1}}mt=-\frac{2(k+4)}{\sqrt{3(k+1)}}mt$. Since k is a integer, it is easy to obtain that $t=0$. Therefore, $x_u=0$ for all $u\in V$. By (3.5) to (3.7), one can see $x_{u_{i_1}^l}=-x_{u_{i_3}^l}$ and $x_{u_{i_2}^l}=0$. The eigenvector $x={(x_1,x_2,\cdots ,x_{n+3km})}^t$ associated with $\sigma =\frac{4}{3}$ can be completely determined by the following equation system:

$\{\begin{array}{l}{x}_{u_{i_1}^l}=-x_{u_{i_3}^l},\forall u_{i_1}^l\in F_1^l,\forall u_{i_3}^l\in F_3^l\\ x_{u_{i_2}^l}=0,\forall u_{i_2}^l\in F_2^l\\ x_u=0,\forall u\in V\\ {\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in F_1^u}{\sum }\frac{1}{\sqrt{3(k+1)d_u}}{x}_{u_{i_1}^l}=0,\forall u\in V}}\end{array}$ (4.11)

Let $x_{u_{i_1}^l}=-x_{u_{i_3}^l}=y_i^l$ with $i=1,2,\cdots ,m$ and $l=1,2,\cdots ,k$. Suppose

$y={(y_1^1,y_2^1,\cdots ,y_m^1,\cdots ,y_1^k,y_2^k,\cdots ,y_m^k)}_{km}^t$

Note that ${\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in F_1^u}{\sum }\frac{1}{\sqrt{3(k+1)d_u}}{x}_{u_{i_1}^l}=0}}$, $\forall u\in V$. Let $\stackrel{\to }{W}(G)={[\stackrel{\to }{I}(G),\stackrel{\to }{I}(G),\cdots ,\stackrel{\to }{I}(G)]}_{n\times km}$, then we have

$\stackrel{\to }{W}(G)y=0.$ (4.12)

By Lemma 3.1, we know that $r(\stackrel{\to }{W}(G))=r(\stackrel{\to }{I}(G))=n-1$, system (4.12) has exactly $km-n+1$ linearly independent solutions. Thus $p_{\mathcal{L}(F^k(G))}(\frac{4}{3})=km-n+1$. Suppose $p_{\mathcal{L}(F^k(G))}(\frac{5-\sqrt{13}}{6})=a$ and $p_{\mathcal{L}(F^k(G))}(\frac{5+\sqrt{13}}{6})=b$. In view of Lemma 3.3, we have

$\begin{array}{l}\tau (F^k(G))\\ =\frac{{\displaystyle {\prod }_{i=1}^{n+3km}{d}_i^{\text{'}}\cdot {\displaystyle {\prod }_{i=2}^{n-1}\left[\frac{3k+8}{18(k+1)}{\lambda }_i\right]\cdot \frac{3k+8}{3(k+1)}\cdot \frac{5k+1}{3(k+1)}\cdot {\left(\frac{4}{3}\right)}^{km-n+1}\cdot {\left(\frac{5-\sqrt{13}}{6}\right)}^a\cdot {\left(\frac{5+\sqrt{13}}{6}\right)}^b}}}{2|E(F^k(G))|}\\ =3^{km-n+1-a}\cdot 2^{3km-3n+3}\cdot {(}^3\cdot {\left(\frac{5+\sqrt{13}}{6}\right)}^{b-a}\cdot \tau (G).\end{array}$

Since $\tau (F^k(G))$ and $\tau (G)$ are positive integers, it is obvious that $a=b$. Then we have $p_{\mathcal{L}(F^k(G))}(\frac{5-\sqrt{13}}{6})=p_{\mathcal{L}(F^k(G))}(\frac{5+\sqrt{13}}{6})=km-n+1$ by counting the number of the eigenvalues of $F^k(G)$.

This completes the proofs of Theorem 2.1.

4.2. Proof of Theorem 2.2

Proof. (i)-(iii) Let $\mu$ be an eigenvalue of $\mathcal{L}(R^k(G))$ with $\mu \ne 1,\frac{3\pm \sqrt{6}}{3}$. By Lemma 3.7, we have

$\lambda =\frac{3\mu [3(k+1){\mu }^3-(12k+9){\mu }^2+(15k+7)\mu -(6k+1)]}{9{\mu }^3-27{\mu }^2+21\mu -(k+3)}$ (4.13)

is an eigenvalue of $\mathcal{L}(G)$ with the same multiplicity as that of $\mu$. Then we have

$\begin{array}{l}9(k+1){\mu }^4-(36k+9\lambda +27){\mu }^3+(45k+27\lambda +21){\mu }^2\\ -(18k+21+3)\mu +(3+k)\lambda =0.\end{array}$ (4.14)

Since 0 is an eigenvalue of $\mathcal{L}(G)$ with multiplicity 1, we substitute $\lambda =0$ into (4.14) yields $\mu =0,1$ and $\frac{9k\pm \sqrt{3}\sqrt{3k^2+8k+8}+6}{6(k+1)}$. By Lemma 3.3, ${\lambda }_n=2$ is an eigenvalue of $\mathcal{L}(G)$ with multiplicity 1 if G is bipartite. Substituting $\lambda =2$ into (4.14) yields $\mu =\frac{3\pm \sqrt{6}}{3}$, $\frac{6k\pm \sqrt{3}\sqrt{4k^2+4k+3}+9}{6(k+1)}$.

This completes the proofs of (i)-(iii).

(iv) Substituting $\mu =\frac{3-\sqrt{6}}{3}$ into (3.21) yields that

$\frac{1}{\sqrt{d_u}}{x}_u=-\frac{1}{\sqrt{d_v}}{x}_v.$ (4.15)

Since the connected simple graph G is non-bipartite, G contains an odd cycle, written as $C_1$. In view of (4.15), we have $\frac{x_u}{\sqrt{d_u}}={(-1)}^{|V(C_1)|}\frac{x_u}{\sqrt{d_u}}=-\frac{x_u}{\sqrt{d_u}}$. It is easy to conclude that $x_u=x_v=0$ for $u\sim v$. Note that G is connected, we have $x_u=0$ for all $u\in V(G)$. Combining with (3.16) to (3.20), we have $x_{u_{i_1}^l}=x_{u_{i_2}^l}=x_{u_{i_3}^l}=x_{u_{i_4}^l}$ and ${\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in R_1^l}{\sum }\frac{1}{\sqrt{3(k+1)d_u}}}}{x}_{u_{i_1}^l}=0$.

Therefore, the eigenvector $x={(x_1,x_2,\cdots ,x_{n+4km})}^t$ associated with $\mu =\frac{3-\sqrt{6}}{3}$ can be completely decided by the following equation system:

$\{\begin{array}{l}{x}_{u_{i_1}^l}=x_{u_{i_2}^l}=x_{u_{i_3}^l}=x_{u_{i_4}^l},\forall u_{i_1}^l\in R_1^l,u_{i_2}^l\in R_2^l,u_{i_3}^l\in R_3^l,u_{i_4}^l\in R_4^l\\ x_u=0,\forall u\in O\\ {\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in R_1^l}{\sum }\frac{1}{\sqrt{3(k+1)d_u}}}}{x}_{u_{i_1}^l}=0,\forall u\in O\end{array}$ (4.16)

Suppose $x_{u_{i_1}^l}=x_{u_{i_2}^l}=x_{u_{i_3}^l}=x_{u_{i_4}^l}=z_i^l$, with $i=1,2,\cdots ,m$ and $l=1,2,\cdots ,k$. Let

$z={(z_1^1,z_2^1,\cdots z_m^1,\cdots ,z_1^k,z_2^k,\cdots z_m^k)}_{km}^t.$

Note that ${\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in R_1^l}{\sum }\frac{1}{\sqrt{3(k+1)d_u}}}}{x}_{u_{i_1}^l}=0$, $\forall u\in O$. Let $W(G)={[I(G),I(G),\cdots ,I(G)]}_{n\times km}$. Then we have

$W(G)z=0.$ (4.17)

By Lemma 3.1, we know that $r(W(G))=r(I(G))=n$. System (4.17) has $km-n$ linearly independent solutions. Thus $p_{\mathcal{L}(R^k(G))}(\frac{3-\sqrt{6}}{3})=km-n$. Similarly, substitute $\mu =\frac{3+\sqrt{6}}{3}$ into (3.21), we can get $p_{\mathcal{L}(R^k(G))}(\frac{3+\sqrt{6}}{3})=km-n$. Hence $p_{\mathcal{L}(R^k(G))}(1)=2km-n+1$ by counting the number of the eigenvalues of $R^k(G)$.

This completes the proofs of (iv).

(v) Substituting $\mu =1$ into (3.20) yields that

$\frac{1}{\sqrt{d_u}}{x}_u=\frac{1}{\sqrt{d_v}}{x}_v.$ (4.18)

Suppose $\frac{1}{\sqrt{d_u}}{x}_u=\frac{1}{\sqrt{d_v}}{x}_v=t$. By (3.17) and (3.20), we have

$x_{u_{i_2}^l}+x_{u_{i_3}^l}=-\sqrt{\frac{2}{k+1}}\cdot t.$ (4.19)

In view of (3.18), we have that

$x_{u_{i_1}^l}+x_{u_{i_4}^l}=0.$ (4.20)

By (3.16), it is obvious that

${\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in R_1^l}{\sum }{x}_{u_{i_1}^l}}}=-\sqrt{\frac{3}{k+1}}{d}_{u}t.$ (4.21)

According to (4.20) and (4.21), we know that

${\displaystyle \underset{u\in O}{\sum }{\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in R_1^l}{\sum }{x}_{u_{i_1}^l}}}}={\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{e_i\in E(G)}{\sum }(x_{u_{i_1}^l}+x_{u_{i_4}^l})}}={\displaystyle \underset{u\in O}{\sum }-\sqrt{\frac{3}{k+1}}{d}_{u}t}.$ (4.22)

Combining (4.20) and (4.22), we have $-2m\sqrt{\frac{3}{k+1}}t=0$. Since k is a integer, it is easy to know that $t=0$, thus, $x_u=0$ for all $u\in O$. By (3.17) to (3.20), we have $x_{u_{i_1}^l}=-x_{u_{i_4}^l}$ and $x_{u_{i_2}^l}+x_{u_{i_3}^l}=0$. The eigenvector $x={(x_1,x_2,\cdots ,x_{n+4km})}^t$ associated with $\mu =1$ can be completely determined by the following equation system

$\{\begin{array}{l}{x}_{u_{i_1}^l}=-x_{u_{i_4}^l},\forall u_{i_1}^l\in R_1^l,u_{i_4}^l\in R_4^l\\ x_{u_{i_2}^l}=-x_{u_{i_3}^l},\forall u_{i_2}^l\in R_2^l,u_{i_3}^l\in R_3^l\\ x_u=0,\forall u\in O\\ {\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in R_1^l}{\sum }\frac{1}{\sqrt{3(k+1)d_u}}}}{x}_{u_{i_1}^l}=0,\forall u\in O\end{array}$ (4.23)

Suppose $x_{u_{i_1}^l}=-x_{u_{i_4}^l}=z_{i1}^l$ and $x_{u_{i_2}^l}=-x_{u_{i_3}^l}=z_{i2}^l$, with $i=1,2,\cdots ,m$ and $l=1,2,\cdots ,k$. Let

$z={(z_{11}^1,z_{12}^1,z_{21}^1,z_{22}^1,\cdots ,z_{m1}^1,z_{m2}^1,\cdots ,z_{11}^k,z_{12}^k,z_{21}^k,z_{22}^k,\cdots ,z_{m1}^k,z_{m2}^k)}_{2km}^t.$ (4.24)

Note that ${\displaystyle \underset{l=1}{\overset{k}{\sum }}{\displaystyle \underset{u_{i_1}^l\in R_1^l}{\sum }\frac{1}{\sqrt{3(k+1)d_u}}}}{x}_{u_{i_1}^l}=0$, for all $u\in O$. Let $\stackrel{\to }{W}(G)={[\stackrel{\to }{I}(G),\stackrel{\to }{I}(G),\cdots ,\stackrel{\to }{I}(G)]}_{n\times 2km}$. Then we have

$\stackrel{\to }{W}(G)z=0.$

In view of Lemma 3.1, we know that $r(\stackrel{\to }{W}(G))=r(\stackrel{\to }{I}(G))=n-1$, system (4.24) has exactly $2km-n+1$ linearly independent solutions. Thus $p_{\mathcal{L}(R^k(G))}(1)=2km-n+1$. Let $p_{\mathcal{L}(R^k(G))}(\frac{3-\sqrt{6}}{3})=a$ and $p_{\mathcal{L}(R^k(G))}(\frac{3+\sqrt{6}}{3})=b$. By Lemma 3.3, we have

$\begin{array}{l}\tau (R^k(G))\\ =\frac{{\displaystyle {\prod }_{i=1}^{n+4km}{d}_i^{\text{'}}}\cdot {\displaystyle {\prod }_{i=2}^{n-1}\left[\frac{3+k}{9(k+1)}{\lambda }_i\right]}\cdot \frac{2k+6}{3(k+1)}\cdot \frac{6k+1}{3(k+1)}\cdot 1^{2km-n+1}\cdot {\left(\frac{3-\sqrt{6}}{3}\right)}^a\cdot {\left(\frac{3+\sqrt{6}}{3}\right)}^b}{2|E(R^k(G))|}\\ =3^{2km-2n+2-a}\cdot 2^{2km-1}\cdot (2k+6)\cdot {(}^k\cdot {\left(\frac{3+\sqrt{6}}{3}\right)}^{b-a}\cdot \tau (G).\end{array}$

Note that $\tau (R^k(G))$ and $\tau (G)$ are positive integers, we have $a=b$. Therefore, $p_{\mathcal{L}(R^k(G))}(\frac{3-\sqrt{6}}{3})=p_{\mathcal{L}(R^k(G))}(\frac{3+\sqrt{6}}{3})=km-n+1$ by counting the number of the eigenvalues of $R^k(G)$.

This completes the proofs of Theorem 2.2.

5. Application

5.1. The Normalized Laplacian, Multiplicative Degree-Kirchhoff Index, Kemeny’s Constant and Spanning Trees of $F_r^k(G)$

Note that $F_0^k(G)=G$, $F_1^k(G)=F^k(G)$, $F_r^k(G)=F^k(F_{r-1}^k(G))$. Let ${\epsilon }_r^k$ and ${\varsigma }_r^k$ be the size and order of $F_r^k(G)$, respectively, where $k\ge 2$ and $r\ge 1$. Then the following equations system can be obtained.

$\{\begin{array}{l}{\epsilon }_0^k=m,\\ {\varsigma }_0^k=n,\\ {\epsilon }_r^k=(5k+1){\epsilon }_{r-1}^k,r\ge 1\\ {\varsigma }_r^k={\varsigma }_{r-1}^k+3k{\epsilon }_{r-1}^k,r\ge 1\end{array}$.

Thus, we can get the general formula of ${\epsilon }_r^k$ and ${\varsigma }_r^k$,

${\epsilon }_r^k={(5k+1)}^{r}m$, ${\varsigma }_r^k=n+\frac{3[{(5k+1)}^r-1]}{5}m$. (5.1)

The roots of $\begin{array}{l}18(k+1){\sigma }^4-(72k+18\lambda +54){\sigma }^3+(94k+54\lambda +46){\sigma }^2\\ -(40k+46\lambda +2k\lambda +8)\sigma +(3k+8)\lambda =0\end{array}$ are denoted by $h_i(\lambda )$, with $i=1,2,3,4$. Let H be a multiset of real numbers, we have

$\begin{array}{l}{h}_1(H)={\displaystyle \underset{x\in H}{\cup }\left\{h_1(x)\right\}},h_2(H)={\displaystyle \underset{x\in H}{\cup }\left\{h_2(x)\right\}},h_3(H)={\displaystyle \underset{x\in H}{\cup }\left\{h_3(x)\right\}},\\ h_4(H)={\displaystyle \underset{x\in H}{\cup }\left\{h_4(x)\right\},}\end{array}$

where $h_1,h_2,h_3,h_4$ are defined as above. Then the following theorem directly follows by Theorem 2.1 and the construction of $F_r^k(G)$.

Theorem 5.1. Let G be a simple connected graph of order n and size m. Then

$S(F_r^k(G))=\{\begin{array}{l}{\displaystyle \underset{i=1}{\overset{4}{\cup }}{h}_i\left[S(F^k(G))\backslash \left\{0,2\right\}\right]\cup \left\{0,\frac{8k\pm \sqrt{4k^2+8k+13}+5}{6(k+1)},\frac{7k\pm \sqrt{13k^2+8k+4}+10}{6(k+1)}\right\}}\\ \cup \left\{\underset{km-n+1}{\underset{︸}{\frac{5\pm \sqrt{13}}{6},\cdots ,\frac{5\pm \sqrt{13}}{6}}}\right\}\cup \left\{\underset{km-n+1}{\underset{︸}{\frac{4}{3},\cdots ,\frac{4}{3}}}\right\},\text{if}r=1\text{and}G\text{is}\text{bipartite}\\ {\displaystyle \underset{i=1}{\overset{4}{\cup }}{h}_i\left[S(F_r^k(G))\backslash \left\{0\right\}\right]\cup \left\{0,\frac{8k\pm \sqrt{4k^2+8k+13}+5}{6(k+1)}\right\}}\\ \cup \left\{\underset{k{\epsilon }_{r-1}^k-{\varsigma }_{r-1}^k+1}{\underset{︸}{\frac{5\pm \sqrt{13}}{6},\cdots ,\frac{5\pm \sqrt{13}}{6}}}\right\}\cup \left\{\underset{k{\epsilon }_{r-1}^k-{\varsigma }_{r-1}^k+1}{\underset{︸}{\frac{4}{3},\cdots ,\frac{4}{3}}}\right\},\text{otherwise}\end{array}$

Theorem 5.2. Let G be a simple connected graph of order n and size m. Then

(i)

$\begin{array}{l}K{f}^{*}(F_r^k(G))={\left[\frac{8{(5k+1)}^2}{(3k+8)}\right]}^{r}K{f}^{*}(G)\\ +\frac{{(5k+1)}^r[(12765k+27269){(15k^2+43k+8)}^{r-1}-26720{(40k+8)}^{r-1}-549{(3k+8)}^{r-1}]}{1110{(3k+8)}^{r-1}}{m}^2\\ -\frac{61{(5k+1)}^r[{(40k+8)}^r-{(3k+8)}^r]}{74{(3k+8)}^r}mn\\ +\frac{(101k-483){(5k+1)}^{r-1}[{(40k+8)}^r-{(3k+8)}^r]}{74{(3k+8)}^r}m.\end{array}$

(ii)

$\begin{array}{l}Ke(F_r^k(G))={\left[\frac{8{(5k+1)}^2}{(3k+8)}\right]}^{r}Ke(G)\\ +\frac{(12765k+27269){(15k^2+43k+8)}^{r-1}-26720{(40k+8)}^{r-1}-549{(3k+8)}^{r-1}}{2220{(3k+8)}^{r-1}}m\\ -\frac{61[{(40k+8)}^r-{(3k+8)}^r]}{148{(3k+8)}^r}n+\frac{(101k-483)[{(40k+8)}^r-{(3k+8)}^r]}{148(5k+1){(3k+8)}^r}.\end{array}$

(iii)

$\tau (F_r^k(G))={(3k+8)}^{(n-1)r-m\left\{\frac{3r}{5}-\frac{3[{(5k+1)}^r-1]}{25k}\right\}}\cdot 2^{\frac{3m[(5k-3){(5k+1)}^r+15kr-5k+3]}{25k}+3r-3nr}\cdot \tau (G).$

Proof. (i) According to Theorem 2.1 (i), one can see that the four roots of $\begin{array}{l}18(k+1){\sigma }^4-(72k+18\lambda +54){\sigma }^3+(94k+54\lambda +46){\sigma }^2\\ -(40k+46\lambda +2k\lambda +8)\sigma +(3k+8)\lambda =0,\end{array}$ denoted by ${\sigma }_1({\lambda }_i),{\sigma }_2({\lambda }_i),{\sigma }_3({\lambda }_i),{\sigma }_4({\lambda }_i)$, are the four corresponding eigenvalues of $\mathcal{L}(F^k(G))$, when $\lambda \ne 0$.

By Vieta theorem, we obtain the following equation:

$\frac{1}{{\sigma }_1({\lambda }_i)}+\frac{1}{{\sigma }_2({\lambda }_i)}+\frac{1}{{\sigma }_3({\lambda }_i)}+\frac{1}{{\sigma }_4({\lambda }_i)}=\frac{2k+46}{3k+8}+\frac{40k+8}{(3k+8){\lambda }_i},$

${\sigma }_1({\lambda }_i){\sigma }_2({\lambda }_i){\sigma }_3({\lambda }_i){\sigma }_4({\lambda }_i)=\frac{3k+8}{18(k+1)}{\lambda }_i.$ (5.2)

Based on Theorem 2.1, Lemma 3.4, (5.1) and (5.2), we have

$\begin{array}{l}K{f}^{*}(F^k(G))\\ =2{\epsilon }_1^k\left\{{\displaystyle \underset{i=2}{\overset{n}{\sum }}\left[\frac{2k+46}{3k+8}+\frac{40k+8}{(3k+8){\lambda }_i}\right]}+\frac{8k+5}{5k+1}+\frac{3}{4}(km-n+1)+\left(\frac{6}{5-\sqrt{13}}+\frac{6}{5+\sqrt{13}}\right)(km-n)\right\}\\ =\frac{16{(5k+1)}^{2}m}{3k+8}{\displaystyle \underset{i=2}{\overset{n}{\sum }}\frac{1}{{\lambda }_i}+\frac{23k(5k+1)}{2}{m}^2}-\frac{61k(5k+1)}{2(3k+8)}mn+\frac{k(101k-483)}{2(3k+8)}m\\ =\frac{8{(5k+1)}^2}{3k+8}K{f}^{*}(G)+\frac{23k(5k+1)}{2}{m}^2-\frac{61k(5k+1)}{2(3k+8)}mn+\frac{k(101k-483)}{2(3k+8)}m.\end{array}$

Based on the above equation and the construction of $F_r^k(G)$ ( $k\ge 2,r\ge 1$ ), we have

$\begin{array}{c}K{f}^{*}(F_r^k(G))=\frac{8{(5k+1)}^2}{3k+8}K{f}^{*}(F_{r-1}^k(G))+\frac{23k(5k+1)}{2}{(}^{{\epsilon }_{r-1}^k}\\ -\frac{61k(5k+1)}{2(3k+8)}{\epsilon }_{r-1}^k{\varsigma }_{r-1}^k+\frac{k(101k-483)}{2(3k+8)}{\epsilon }_{r-1}^k\\ ={\left[\frac{8{(5k+1)}^2}{3k+8}\right]}^{r}K{f}^{*}(G)+\frac{23k(5k+1)}{2}{\displaystyle \underset{i=0}{\overset{r-1}{\sum }}{\left[\frac{8{(5k+1)}^2}{3k+8}\right]}^{r-1-i}}{(}^{{\epsilon }_i^k}\\ -\frac{61k(5k+1)}{2(3k+8)}{\displaystyle \underset{i=0}{\overset{r-1}{\sum }}{\left[\frac{8{(5k+1)}^2}{3k+8}\right]}^{r-1-i}}{\epsilon }_i^k{\varsigma }_i^k\\ +\frac{k(101k-483)}{2(3k+8)}{\displaystyle \underset{i=0}{\overset{r-1}{\sum }}{\left[\frac{8{(5k+1)}^2}{3k+8}\right]}^{r-1-i}{\epsilon }_i^k}\end{array}$

By simple calculation, the conclusion can be easily drawn.

(ii) In view of Lemma 3.5, Theorem 5.2 (i) and (5.1), we can obtain that

$\begin{array}{l}Ke(F^k(G))=\frac{1}{2{\epsilon }_1^k}K{f}^{*}(F^k(G))\\ =\frac{1}{2(5k+1)m}\left[\frac{8{(5k+1)}^2}{3k+8}K{f}^{*}(G)+\frac{23k(5k+1)}{2}{m}^2-\frac{61k(5k+1)}{2(3k+8)}mn+\frac{k(101k-483)}{2(3k+8)}m\right]\\ =\frac{8(5k+1)}{3k+8}Ke(G)+\frac{23}{4}km-\frac{61k}{4(3k+8)}n+\frac{k(101k-483)}{4(5k+1)(3k+8)}.\end{array}$

Based on the above equation and the construction of $F_r^k(G)$ ( $k\ge 2,r\ge 1$ ), we have

$\begin{array}{l}Ke(F_r^k(G))\\ =\frac{8(5k+1)}{3k+8}Ke(G)+\frac{23}{4}km-\frac{61k}{4(3k+8)}n+\frac{k(101k-483)}{4(5k+1)(3k+8)}\\ ={\left[\frac{8(5k+1)}{3k+8}\right]}^{r}Ke(G)+\frac{23}{4}k{\displaystyle \underset{i=0}{\overset{r-1}{\sum }}{\left[\frac{8(5k+1)}{3k+8}\right]}^{r-1-i}}{\epsilon }_i^k\\ -\frac{61k}{4(3k+8)}{\displaystyle \underset{i=0}{\overset{r-1}{\sum }}{\left[\frac{8(5k+1)}{3k+8}\right]}^{r-1-i}}{\varsigma }_i^k+\frac{k(101k-483)}{4(5k+1)(3k+8)}{\displaystyle \underset{i=0}{\overset{r-1}{\sum }}{\left[\frac{8(5k+1)}{3k+8}\right]}^i}\end{array}$

By simple calculation, the conclusion can be easily drawn.

(iii) According to Theorem 2.1, Lemma 3.2, and (5.1), one can see

$\begin{array}{l}\tau (F^k(G))\\ =\frac{{\displaystyle {\prod }_{i=1}^{{\varsigma }_1^k}{d}_i^{\text{'}}\cdot {\displaystyle {\prod }_{i=2}^n\left[\frac{3k+8}{18(k+1)}{\lambda }_i\right]\cdot {\left(\frac{5-\sqrt{13}}{6}\right)}^{km-n}\cdot {\left(\frac{5+\sqrt{13}}{6}\right)}^{km-n}\cdot {\left(\frac{4}{3}\right)}^{km-n+1}\cdot \frac{5k+1}{3(k+1)}}}}{2{\epsilon }_1^k}\\ =\frac{{(3k+8)}^{n-1}\cdot 2^{3km-3n+3}\cdot {\displaystyle {\prod }_{i=1}^n{d}_i\cdot {\displaystyle {\prod }_{i=2}^n{\lambda }_i}}}{2m}\\ ={(}^3\cdot 2^{3km-3n+3}\cdot \tau (G).\end{array}$

From the above equation and the construction of $F_r^k(G)$ ( $k\ge 2,r\ge 1$ ), we have

$\begin{array}{l}\tau (F_r^k(G))={(}^3\cdot 2^{3k{\epsilon }_{r-1}^k-3{\varsigma }_{r-1}^k+3}\cdot \tau (F_{r-1}^k(G))\\ ={(}^3\cdot 2^{{\displaystyle {\sum }_{i=0}^{r-1}(3k{\epsilon }_i^k-3{\varsigma }_i^k)+3r}}\cdot \tau (G)\\ ={(}^3\cdot 2^{\frac{3m[(5k-3){(5k+1)}^r+15kr-5k+3]}{25k}+3r-3nr}\cdot \tau (\; G\; )\end{array}$

This completes the proofs of Theorem 5.2.

5.2. The Normalized Laplacian, Multiplicative Degree-Kirchhoff Index, Kemeny’s Constant and Spanning Trees of $R_r^k(\; G\; )$

Note that $R_0^k(G)=G$, $R_1^k(G)=R^k(G)$, $R_r^k(G)=R^k(R_{r-1}^k(G))$. Let ${\epsilon }_r^k$ and ${\varsigma }_r^k$ be the size and order of $R_r^k(G)$, respectively, where $k\ge 2$ and $r\ge 1$. The following equations can be obtained.

$\{\begin{array}{l}{\epsilon }_0^k=m,\\ {\varsigma }_0^k=n,\\ {\epsilon }_r^k=(6k+1){\epsilon }_{r-1}^k,r\ge 1\\ {\varsigma }_r^k={\varsigma }_{r-1}^k+4k{\epsilon }_{r-1}^k,r\ge 1\end{array}$

It follows that

${\epsilon }_r^k={(6k+1)}^{r}m$, ${\varsigma }_r^k=n+\frac{2[{(6k+1)}^r-1]}{3}m$. (5.3)

The four roots of $\begin{array}{l}9(k+1){\mu }^4-(36k+9\lambda +27){\mu }^3+(45k+27\lambda +21){\mu }^2\\ -(18k+21+3)\mu +(3+k)\lambda =0\end{array}$ are denoted by $f_1(\lambda ),f_2(\lambda ),f_3(\lambda )$ and $f_4(\lambda )$, respectively. For a multiset H of for real numbers, we may define four new multiset:

$\begin{array}{l}{f}_1(H)={\displaystyle \underset{x\in H}{\cup }\left\{f_1(x)\right\}},f_2(H)={\displaystyle \underset{x\in H}{\cup }\left\{f_2(x)\right\}},\\ f_3(H)={\displaystyle \underset{x\in H}{\cup }\left\{f_3(x)\right\}},f_4(H)={\displaystyle \underset{x\in H}{\cup }\left\{f_4(x)\right\},}\end{array}$

Similarly, the following results on the spectrum of $R_r^k(G)$ ( $k\ge 2,r\ge 1$ ) follows immediately by Theorem 2.2 and the construction of $R_r^k(G)$ from G.

Theorem 5.3. Let G be a simple connected graph of order n and size m. Then

$S(R_r^k(G))=\{\begin{array}{l}{\displaystyle \underset{i=1}{\overset{4}{\cup }}{f}_i\left[S(R^k(G))\backslash \left\{0,2\right\}\right]\cup \left\{0,\frac{9k\pm \sqrt{3}\sqrt{3k^2+8k+8}+6}{6(k+1)},\frac{6k\pm \sqrt{3}\sqrt{4k^2+4k+3}+9}{6(k+1)}\right\}}\\ \cup \left\{\underset{2km-n+1}{\underset{︸}{1,\cdots ,1}}\right\}\cup \left\{\underset{km-n+1}{\underset{︸}{\frac{3\pm \sqrt{6}}{3},\cdots ,\frac{3\pm \sqrt{6}}{3}}}\right\},\text{if}r=1\text{and}G\text{is}\text{bipartite}\\ {\displaystyle \underset{i=1}{\overset{4}{\cup }}{f}_i\left[S(R_r^k(G))\backslash \left\{0\right\}\right]\cup \left\{0,\frac{9k\pm \sqrt{3}\sqrt{3k^2+8k+8}+6}{6(k+1)}\right\}}\\ \cup \left\{\underset{2k{\epsilon }_{r-1}^k-{\varsigma }_{r-1}^k+1}{\underset{︸}{1,\cdots ,1}}\right\}\cup \left\{\underset{k{\epsilon }_{r-1}^k-{\varsigma }_{r-1}^k+1}{\underset{︸}{\frac{3\pm \sqrt{6}}{3},\cdots ,\frac{3\pm \sqrt{6}}{3}}}\right\},\text{otherwise}\end{array}$

Theorem 5.4. Let G be a simple connected graph of order n and size m. Then

(i)

$\begin{array}{l}K{f}^{*}(R_r^k(G))={\left[\frac{3{(6k+1)}^2}{(k+3)}\right]}^{r}K{f}^{*}(G)\\ -\frac{{(6k+1)}^r[1944{(18k+3)}^{r-1}+28{(k+3)}^{r-1}-(1972+816k){(6k+1)}^{r-1}{(k+3)}^{r-1}]}{51{(k+3)}^{r-1}}{m}^2\\ -\frac{14{(6k+1)}^r[{(18k+3)}^r-{(k+3)}^r]}{17{(k+3)}^r}mn\\ +\frac{2{(6k+1)}^{r-1}(15k-74)[{(18k+3)}^r-{(k+3)}^r]}{17{(k+3)}^r}m.\end{array}$

(ii)

$\begin{array}{l}Ke(R_r^k(G))={\left[\frac{3{(6k+1)}^2}{(k+3)}\right]}^{r}Ke(G)\\ -\frac{972{(18k+3)}^{r-1}+14{(k+3)}^{r-1}-(986+408k){(6k+1)}^{r-1}{(k+3)}^{r-1}}{51{(k+3)}^{r-1}}m\\ -\frac{7[{(18k+3)}^r-{(k+3)}^r]}{17{(k+3)}^r}n+\frac{(15k-74)[{(18k+3)}^r-{(k+3)}^r]}{17(6k+1){(k+3)}^r}.\end{array}$

(iii)

$\begin{array}{l}\tau (R_r^k(G))\\ ={(}^k\cdot 3^{(r-nr)+\frac{m[12kr-3r+(3k-2){(6k+1)}^r+2]}{18k}}\cdot 2^{\frac{m[{(6k+1)}^r-1]}{3}}\cdot \tau (G).\end{array}$

Proof. (i) By Theorem 2.2, the four corresponding eigenvalues ${\mu }_1({\lambda }_i),{\mu }_2({\lambda }_i),{\mu }_3({\lambda }_i),{\mu }_4({\lambda }_i)$ of $\mathcal{L}(R^k(G))$ are roots of $\begin{array}{l}9(k+1){\mu }^4-(36k+9\lambda +27){\mu }^3+(45k+27\lambda +21){\mu }^2\\ -(18k+21+3)\mu +(3+k)\lambda =0\end{array}$

Thus ${\mu }_1({\lambda }_i),{\mu }_2({\lambda }_i),{\mu }_3({\lambda }_i),{\mu }_4({\lambda }_i)$ satisfy the following equation:

$\frac{1}{{\mu }_1({\lambda }_i)}+\frac{1}{{\mu }_2({\lambda }_i)}+\frac{1}{{\mu }_3({\lambda }_i)}+\frac{1}{{\mu }_4({\lambda }_i)}=\frac{21}{k+3}+\frac{18k+3}{(k+3){\lambda }_i},$

${\mu }_1({\lambda }_i){\mu }_2({\lambda }_i){\mu }_3({\lambda }_i){\mu }_4({\lambda }_i)=\frac{k+3}{9(k+1)}{\lambda }_i.$ (5.4)

In view of Theorem 2.2, Lemma 3.3, (5.3) and (5.4), one can see

$\begin{array}{l}K{f}^{*}(R^k(G))\\ =2{\epsilon }_1^k\left\{{\displaystyle \underset{i=2}{\overset{n}{\sum }}\left[\frac{21}{k+3}+\frac{18k+3}{(k+3){\lambda }_i}\right]}+\frac{9k+6}{6k+1}+(2km-n+1)+\left(\frac{3}{3-\sqrt{6}}+\frac{3}{3+\sqrt{6}}\right)(km-n)\right\}\\ =\frac{6{(6k+1)}^{2}m}{k+3}{\displaystyle \underset{i=2}{\overset{n}{\sum }}\frac{1}{{\lambda }_i}+16k(6k+1)m^2}-\frac{14k(6k+1)}{k+3}mn+\frac{2k(15k-74)}{k+3}m\\ =\frac{3{(6k+1)}^2}{k+3}K{f}^{*}(G)+16k(6k+1)m^2-\frac{14k(6k+1)}{k+3}mn+\frac{2k(15k-74)}{k+3}m.\end{array}$

Based on the above equation and the construction of $R^k(G)$ ( $k\ge 2,r\ge 1$ ), we have

$\begin{array}{c}K{f}^{*}(R_r^k(G))=\frac{3{(6k+1)}^2}{k+3}K{f}^{*}(R_{r-1}^k(G))+16k(6k+1){(}^{{\epsilon }_{r-1}^k}\\ -\frac{14k(6k+1)}{k+3}{\epsilon }_{r-1}^k{\varsigma }_{r-1}^k+\frac{2k(15k-74)}{k+3}{\epsilon }_{r-1}^k\\ ={\left[\frac{3{(6k+1)}^2}{k+3}\right]}^{r}K{f}^{*}(G)+16k(6k+1){\displaystyle \underset{i=0}{\overset{r-1}{\sum }}{\left[\frac{3{(6k+1)}^2}{k+3}\right]}^{r-1-i}}{(}^{{\epsilon }_i^k}\\ -\frac{14k(6k+1)}{k+3}{\displaystyle \underset{i=0}{\overset{r-1}{\sum }}{\left[\frac{3{(6k+1)}^2}{k+3}\right]}^{r-1-i}}{\epsilon }_i^k{\varsigma }_i^k\\ +\frac{2k(15k-74)}{k+3}{\displaystyle \underset{i=0}{\overset{r-1}{\sum }}{\left[\frac{3{(6k+1)}^2}{k+3}\right]}^{r-1-i}{\epsilon }_i^k}.\end{array}$

By simple calculation, the conclusion can be easily drawn.

(ii) In view of Lemma 3.5, Theorem 5.4 (i) and (5.4), we obtain that

$\begin{array}{l}Ke(R^k(G))=\frac{1}{2{\epsilon }_1^k}K{f}^{*}(R^k(G))\\ =\frac{1}{2(6k+1)m}\left[\frac{3{(6k+1)}^2}{k+3}K{f}^{*}(G)+16k(6k+1)m^2-\frac{14k(6k+1)}{k+3}mn+\frac{2k(15k-74)}{k+3}m\right]\\ =\frac{3(6k+1)}{k+3}Ke(G)+8km-\frac{7k}{k+3}n+\frac{k(15k-74)}{(6k+1)(k+3)}.\end{array}$

Based on the above equation and the construction of $R^k(G)$ ( $k\ge 2,r\ge 1$ ) that

$\begin{array}{l}Ke(R_r^k(G))\\ =\frac{3(6k+1)}{k+3}Ke(G)+8km-\frac{7k}{k+3}n+\frac{k(15k-74)}{(6k+1)(k+3)}\\ ={\left[\frac{3(6k+1)}{k+3}\right]}^{r}Ke(G)+8k{\displaystyle \underset{i=0}{\overset{r-1}{\sum }}{\left[\frac{3(6k+1)}{k+3}\right]}^{r-1-i}}{\epsilon }_i^k\\ -\frac{7k}{k+3}{\displaystyle \underset{i=0}{\overset{r-1}{\sum }}{\left[\frac{3(6k+1)}{k+3}\right]}^{r-1-i}}{\varsigma }_i^k+\frac{k(15k-74)}{(6k+1)(k+3)}{\displaystyle \underset{i=0}{\overset{r-1}{\sum }}{\left[\frac{3(6k+1)}{k+3}\right]}^i}.\end{array}$

By simple calculation, the conclusion can be easily drawn.

(iii) According to Theorem 2.2, Lemma 3.2, (5.3) and (5.4), we can obtain

$\begin{array}{l}\tau (F^k(G))\\ =\frac{{\displaystyle {\prod }_{i=1}^{{\varsigma }_1^k}{d}_i^{\text{'}}\cdot {\displaystyle {\prod }_{i=2}^n\left[\frac{k+3}{9(k+1)}{\lambda }_i\right]\cdot {\left(\frac{3-\sqrt{6}}{3}\right)}^{km-n}\cdot {\left(\frac{3+\sqrt{6}}{3}\right)}^{km-n}\cdot 1^{km-n+1}\cdot \frac{6k+1}{3(k+1)}}}}{2{\epsilon }_1^k}\\ =\frac{{(k+3)}^{n-1}\cdot 2^{2km}\cdot 3^{km-n+1}\cdot {\displaystyle {\prod }_{i=1}^n{d}_i\cdot {\displaystyle {\prod }_{i=2}^n{\lambda }_i}}}{2m}\\ ={(}^k\cdot 2^{2km}\cdot 3^{km-n+1}\cdot \tau (G).\end{array}$

Based on the above equation and the construction of $R^k(G)$ ( $k\ge 2,r\ge 1$ ), we have

$\begin{array}{l}\tau (R_r^k(G))\\ ={(}^k\cdot 2^{3k{\epsilon }_{r-1}^k}\cdot 3^{k{\epsilon }_{r-1}^k-{\varsigma }_{r-1}^k+1}\cdot \tau (R_{r-1}^k(G))\\ ={(}^k\cdot 2^{2k{\displaystyle {\sum }_{i=0}^{r-1}({\epsilon }_i^k)}}\cdot 3^{{\displaystyle {\sum }_{i=0}^{r-1}(k{\epsilon }_i^k-{\varsigma }_i^k)+r}}\cdot \tau (G)\\ ={(}^k\cdot 3^{(r-nr)+\frac{m[12kr-3r+(3k-2){(6k+1)}^r+2]}{18k}}\cdot 2^{\frac{m[{(6k+1)}^r-1]}{3}}\cdot \tau (G).\end{array}$

This completes the proofs of Theorem 5.4.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Liu, C., Pan, Y.G. and Li, J.P. (2019) On the Laplacian Spectrum and Kirchhoff Index of Generalized Phenylenes. Polycycl. Aromat. Comp. https://doi.org/10.1080/10406638.2019.1703765
[2]	Pan, Y.G., Liu, C. and Li, J.P. (2020) Kirchhoff Indices and Numbers of Spanning Trees of Molecular Graphs Derived from Linear Crossed Polyomino Chain. Polycycl. Aromat. Comp. https://doi.org/10.1080/10406638.2020.1725898
[3]	Chen, H. and Zhang, F. (2007) Resistance Distance and the Normalized Laplacian Spectrum. Discrete. Appl. Math, 155, 654-661. https://doi.org/10.1016/j.dam.2006.09.008
[4]	Chung, F.R. and Graham, F.C. (1997) Spectral Graph Theory (No. 92). American Mathematical Soc.
[5]	Hunter, J.J. (2014) The Role of Kemeny’s Constant in Properties of Markov Chains. Commumn Stat Theor Methods, 43, 1309-1321. https://doi.org/10.1080/03610926.2012.741742
[6]	Butler, S. and Grout, J. (2011) A Construction of Cospectral Graphs for the Normalized Laplacian. Electronic. J. Comb, 231-231. https://doi.org/10.37236/718
[7]	Huang, J. and Li, S. (2018) The Normalized Laplacians on Both K-Triangle Graph and K-Quadrilateral Graph with Their Applications. Appl. Math. Comput, 320, 213-225. https://doi.org/10.1016/j.amc.2017.09.035
[8]	Huang, J., Li, S. and Li, X. (2016) The Normalized Laplacian, Degree-Kirchhoff Index and Spanning Trees of the Linear Polyomino Chains. Appl. Math. Comput, 289, 324-334. https://doi.org/10.1016/j.amc.2016.05.024
[9]	Li, D. and Hou, Y. (2017) The Normalized Laplacian Spectrum of Quadrilateral Graphs and Its Applications. Appl. Math. Comput, 297, 180-188. https://doi.org/10.1016/j.amc.2016.10.041
[10]	Pan, Y.G., Li, J.P., Li, S. and Luo, W.J. (2018) On the Normalized Laplacians with Some Classical Parameters Involving Graph Transformations, Linear Multilinear Algebra. https://doi.org/10.1016/j.amc.2016.10.041
[11]	Xie, P., Zhang, Z. and Comellas, F. (2016) The Normalized Laplacian Spectrum of Subdivisions of a Graph. Appl. Math. Comput, 286, 250-256. https://doi.org/10.1016/j.amc.2016.04.033
[12]	Cvetkovic, D.M., Rowlinson, P. and Simic, S. (2010) An Introduction to the Theory of Graph Spectra. Cambridge University Press, Cambridge, 230-231. https://doi.org/10.1017/CBO9780511801518
[13]	Bapat, R.B. (2010) Graphs and Matrices (Vol. 27). Springer, London. https://doi.org/10.1007/978-1-84882-981-7
[14]	Butler, S. (2016) Algebraic Aspects of the Normalized Laplacian. In: Recent Trends in Combinatorics, Springer, Cham., 295-315. https://doi.org/10.1007/978-3-319-24298-9_13