Mapping the evolving complexity of large hydropower project finance in low and lower-middle income countries

1.   Introduction

Let $G$ be a simple graph with vertex set $V(G) = \left \{ 1, 2, \dots, n \right\}$ and edge set $E(G)$. The adjacency matrix of $G$ is an $n\times n$ matrix $A(G) = (a_{ij})$, where $a_{ij} = 1$ if vertex $i$ is adjacency to vertex $j$, and $0$ otherwise. We use the notation $i\sim j$ (or $ij\in E(G)$) to indicate that vertices $i, j$ are adjacent in $G$. The adjacency eigenvalues of $G$ are just the eigenvalues of $A(G)$. For an eigenvalue $\mu$, let $\mathcal{E} (\mu)$ be the eigenspace $\left\{ x \in \mathbb{R}^n | A(G)x = \mu x \ \right\}$. For more details on graph spectra, see ^[4].

Let $\mu$ be an eigenvalue of $G$ with multiplicity $k$. A star set for $\mu$ in $G$ is a subset $X$ of $V(G)$ such that $\left | X \right | = k$ and $\mu$ is not an eigenvalue of $G-X$, where $G-X$ is the subetaaph of $G$ induced by $\overline{X} = V(G)\setminus X$. In this situation $H = G-X$ is called a star complement for $\mu$. Star sets and star complements exist for any eigenvalue of a graph, and they need not to be unique. The basic properties of star sets are established in Chapter $7$ of ^[5] and Chapter $5$ of ^[7].

There is another equivalent geometric definition for star sets and star complements. Let $G$ be a graph with vertex set $V(G) = \left\{1, \dots, n \right\}$ and adjacency matrix $A$. Let $\left\{e_1, \dots, e_n\right\}$ be the standard orthonormal basis of $\mathbb{R}^n$ and $P$ be the matrix which represents the orthogonal projection of $\mathbb{R}^n$ onto the eigenspace $\mathcal{E} (\mu) = \left\{ x \in \mathbb{R}^n : A(G)x = \mu x \ \right\}$ of $A$ with respect to $\left\{e_1, \dots, e_n\right\}$. Since $\mathcal{E} (\mu)$ is spanned by the vectors $Pe_j(j = 1, \dots, n)$, there exists $X \subseteq V (G)$ such that the vectors $Pe_j(j \in X)$ form a basis for $\mathcal{E} (\mu)$. Such a subset $X$ of $V(G)$ is called a star set for $\mu$ in $G$. In this situation $H = G-X$ is called a star complement for $\mu$ (^[5,7]).

For any graph $G$ of order $n$ with distinct eigenvalues $\lambda_1, \dots, \lambda_m$, there exists a partition $V(G) = V_1 \bigcup \cdots \bigcup V_m$ such that $V_i$ is a star set for eigenvalue $\lambda_i \ (i = 1, \dots, m)$. Such a partition is called a star partition of $G$. For any graph $G$, there exists at least one star partition (^[5]). Each star partition determines a basis for $\mathbb{R}^n$ consisting of eigenvectors of an adjacency matrix. It provides a strong link between graph structure and linear algebra.

In ^[7], it was proved that if $Y\subset X$ then $X\setminus Y$ is a star set for $\mu$ in $G-Y$. Thus the induced subetaaph $G-Y$ also has $H$ as a star complement for $\mu$. If $G$ has $H$ as a star complement for $\mu$, and $G$ is not a proper induced subetaaph of some other graph with $H$ as a star complement for $\mu$, then $G$ is a maximal graph with $H$ as a star complement for $\mu$, or it is an $H$- maximal graph for $\mu$. Accordingly, in determining all the graphs with $H$ as a star complement for $\mu$, it suffices to describe the maximal graphs which arise.

There are a lot of literatures about using star complements to construct and characterize certain graphs. Regular graphs with a prescribed graph such as $K_{1, s}$, $K_{2, s}$, $K_{1, 1, t}$, $K_{1, 1, 1, t}$, $\overline{sK_1\cup K_t}$, $P_t$, $K_{r, r, r}$ or $K_{r, s}+tK_1$ as a star complement are discussed in the literature (^{[1,8,10,12,15,16,17,18]}). Bipartite graphs with complete bipartite $K_{r, s}$ as a star complement is considered by Rowlinson in 2014 (^[9]). Maximal graphs with a prescribed graph such as $S_m$, $K_m$, $S_{m, n}$, $K_{2, 5}$, $K_{1, 1, t}$, $C_t$, $P_t$, $\overline{L(R_t)}$, $\overline{L(Q_t)}$ or unicyclic graph as a star complement for given eigenvalue are well studied in the literature (^{[2,3,6,11,13,14,17,18]}). In this paper, we introduce some results on the theory of star complements in Section 2, characterize the maximal graphs with the bipartite graph $K_{2, s}$ as a star complement for eigenvalues $\mu = -2, 1$ in Section 3, and study the cases of other eigenvalues for further research in Section 4.

2.   Preliminaries

In this section, we introduce some results of star sets and star complements that will be required in the sequel. The following fundamental result combines the Reconstruction Theorem ([5,Theorem 7.4.1]) with its converse ([5,Theorem 7.4.4]).

Theorem 2.1. (^[5]) Let $X$ be a set of vertices in the graph $G$. Suppose that $G$ has adjacency matrix

where $A_X$ is the adjacency matrix of the subetaaph induced by $X$. Then $X$ is a star set for $\mu$ in $G$ if and only if $\mu$ is not an eigenvalue of $C$ and

Note that if $X$ is a star set for $\mu$, then the corresponding star complement $H( = G-X)$ has adjacency matrix $C$, and (2.1) tells us that $G$ is determined by $\mu$, $H$ and the $H$-neighbourhood of vertices in $X$, where the $H$-neighbourhood of vertex $u\in X$, denoted by $N_H(u)$, is defined as $N_H(u) = \left\{v\mid v\sim u, v\in V(H)\right\}$.

It is usually convenient to apply (2.1) in the form $m(\mu)(\mu I-A_X) = B^Tm(\mu)(\mu I-C)^{-1}B,$ where $m(x)$ is the minimal polynomial of $C$. This is because $m(\mu)(\mu I-C)^{-1}$ is given explicitly as follows.

Proposition 2.2. (^[6], Proposition 0.2) Let $C$ be a square matrix with minimal polynomial

If $\mu$ is not an eigenvalue of $C$, then

where $a_d = 1$ and for $0 < i\leq d$, $a_{d-i} = \mu ^i+c_d \mu^{i-1}+c_{d-1} \mu^{i-2}+\cdots+c_{d-i+1}.$

In order to find all the graphs with a prescribed star complement for $\mu$, we need to find, for given $\mu$ and $C$ where $\mu$ is not an eigenvalue of $C$, all $A_X$ and $B$ satisfying $\mu I-A_X = B^T(\mu I-C)^{-1}B$. For any $\textbf{x}, \textbf{y} \in \mathbb{R}^q$, where $q = \left|V(H) \right|$, let

Let $\textbf{b}_u$ be the column of $B$ for any $u \in X$. By Theorem 2.1, we have

Corollary 2.3. (^[7], Corollary 5.1.8) Suppose that $\mu$ is not an eigenvalue of the graph $H$, where $\left|V(H)\right| = q$. There exists a graph $G$ with a star set $X = \left\{u_1, u_2, \dots, u_k\right\}$ for $\mu$ such that $G-X = H$ if and only if there exist $(0, 1)$-vectors $\boldsymbol{b}_{u_1}, \boldsymbol{b}_{u_2}, \dots, \boldsymbol{b}_{u_k}$ in $\mathbb{R}^q$ such that

(1) $\left \langle \boldsymbol{b}_u, \boldsymbol{b}_u \right \rangle = \mu$ for all $u \in X$, and

(2) $\rm$ $\left \langle \boldsymbol{b}_u, \boldsymbol{b}_v \right \rangle = \left\{\begin{matrix} -1, & u \sim v \\ 0, & u \nsim v \end{matrix}\right.$ for all pairs $u, v$ in $X$.

Given a graph $H$, a subset $U$ of $V(H)$ and a vertex $u$ not in $V(H)$, denote by $H(U)$ the graph obtained from $H$ by joining $u$ to all vertices of $U$. We will say that $u\ (resp.\ U, H(U))$ is a good vertex (resp. good set, good extension) for $\mu$ and $H$, if $\mu$ is an eigenvalue of $H(U)$ but is not an eigenvalue of $H$. By Theorem 2.1, a vertex $u$, or a subset $U$, or a graph $H(U)$ is good if and only if $\left \langle \textbf{b}_u, \textbf{b}_u \right \rangle = \mu$, and two vertices $u$ and $v$ are good partners if and only if $\left \langle \textbf{b}_u, \textbf{b}_v \right \rangle \in \left\{-1, 0\right\}$. It follows that any vertex set $X$ in which all vertices are good and any two vertices are good partners, gives rise to a extensional graph, say $G$. In this situation, $X$ can be viewed as a star set for $\mu$ with $H$ as the corresponding star complement.

In view of the two conditions in the above corollary, we have

Lemma 2.4. (^[5]) Let $X$ be a star set for $\mu$ in $G$, and $H = G-X$.

(1) If $\mu \neq 0$, then $V(H)$ is a dominating set for $G$, that is, the $H$-neighbourhood of any vertex in $X$ are non-empty;

(2) If $\mu \notin \left\{ -1, 0 \right\}$, then $V(H)$ is a location-dominating set for $G$, that is, the $H$-neighbourhood of distinct vertices in $X$ are distinct and non-empty.

It follows from (2) of Lemma 2.4 that there are only finitely maximal graphs with a prescribed star complement for $\mu \notin \left\{-1, 0\right\}$.

Let $H\cong K_{t, s}\ (s\geq t\geq 1)$, $(R, S)$ be the bipartition of the graph $K_{t, s}$ with $R = \left\{ i_1, i_2, \dots, i_t \right\}$, $S = \left\{ j_1, j_2, \dots, j_s \right\}$. A vertex $u \in X$ is said to be of type $(a, b)$ if it has $a$ neighbours in $R$ and $b$ neighbours in $S$, thus $(a, b)\neq (0, 0)$ and $0\leq a\leq t$, $0\leq b\leq s$. The following (2.3) and (2.4) have been given in ^[11], and now we express them in the form of a necessary and sufficient condition and give a proof.

Proposition 2.5. (^[11]) Let $H\cong K_{t, s}\ (s\geq t\geq 1)$, $R, S$ defined as above, and $\mu$ be not an eigenvalue of the graph $H$. Then $G$ is a graph with $H$ as a star complement for $\mu$ if and only if the vertex set $X$ such that $G-X = H$ satisfies the following two conditions:

$\rm (1)$ for any $u\in X$ of type $(a, b)$, we have

$\rm (2)$ for any two distinct vertices $u, v\in X$ of type $(a, b)$, $(c, d)$, respectively, $\rho_{uv} = \left |N_H(u)\cap N_H(v)\right|$, and $a_{uv} = \left\{\begin{matrix} 1, & u \sim v, \\ 0, & u \nsim v, \end{matrix}\right.$ we have

Proof. Let $C$ be the adjacency matrix of $H$. Then $C = \begin{pmatrix} O_{t\times t} & J_{t\times s} \\ J_{s\times t} & O_{s\times s} \end{pmatrix}$, where $O_{t\times t}$ and $J_{t\times s}$ denote all-$0$ matrix of size $t\times t$ and all-$1$ matrix of size $t\times s$, respectively. Thus we have $C^2 = \begin{pmatrix} sJ_{t\times t} & O_{t\times s} \\ O_{s\times t} & tJ_{s\times s} \end{pmatrix},$ and $C$ has minimal polynomial $m(x) = x(x^2-ts).$

Since $\mu$ is not an eigenvalue of $C$, we have $\mu \neq 0$ and $\mu^2 \neq ts$. From Proposition 2.2, we have

Let $\textbf{b}_u = (\textbf{b}_{R}^T, \textbf{b}_{S}^T)^T\in R^{t+s}$, where $\textbf{b}_{R}$ and $\textbf{b}_{S}$ are vectors of size $t\times 1$ and size $s\times 1$, respectively. For any $u\in X$ of type $(a, b)$, by $\left \langle \textbf{b}_u, \textbf{b}_u \right \rangle = \mu$, (2.2) and (2.5), we have

Thus we obtain (2.3).

Similarly, for any two distinct vertices $u, v\in X$ of type $(a, b)$, $(c, d)$, respectively, $\rho_{uv} = \left |N_H(u)\cap N_H(v)\right|$, by $\left \langle \textbf{b}_u, \textbf{b}_v \right \rangle = -a_{uv}$, (2.2) and (2.5), we have

Thus we obtain (2.4).

By Corollary 2.3, we complete the proof.

The following lemma is important for us to establish the location of an eigenvalue of a graph. It is a natural extension of Interlacing Theorem.

Lemma 2.6. (^[8]) Given a graph of order $n$ with eigenvalue $\mu$ of multiplicity $k\geq 1$, let $H$ be a star complement for $\mu$ in $G$. Let $\lambda _{r+1}(H) < \mu < \lambda_r(H)$ for some $0\leq r \leq n-k$, where $\lambda_0(H) = \infty$. Then $\lambda _{r+1}(G) = \cdots = \lambda _{r+k}(G) = \mu$.

3.   Maximal graphs with $K_{2, s}$ as a star complement for given eigenvalues

As far as we know, researchers can use the star complement technique to construct graphs with certain spectral properties. In fact, we are usually interested in the eigenvalues with large multiplicity in graphs.

Maximal graphs with a prescribed graph such as $S_m$, $K_m$, $S_{m, n}$, $K_{2, 5}$, $K_{1, 1, t}$, $C_t$, $P_t$, $\overline{L(R_t)}$ or $\overline{L(Q_t)}$ as a star complement for given eigenvalue $\mu$ is well studied in the literature(^{[2,3,6,11,13,17,18]}), see Table 1.

In this section, we study the maximal graphs with $K_{2, s}$ as a star complement for $\mu = -2$ and $\mu = 1$.

3.1.   $\mu=-2$

Let $\mu = -2$, $H = G-X \cong K_{2, s}$ and $(R, S)$ be the bipartition of the graph $H\cong K_{2, s}$. In this subsection, we prove that $K_{2, 1}$, $K_{2, 10}$, $K_{2, 11}$, $K_{2, 12}$, $K_{2, 18}$, $K_{2, 20}$ and $K_{2, 27}$ are the only graphs among $K_{2, s}$ which can be star complements for $\mu = -2$, and then we take $K_{2, 10}$ as an example to characterize the maximal graphs with it as a star complement for $-2$.

Let $\mu = -2$. Since $-2$ is not an eigenvalue of $H\cong K_{2, s}$, we have $\mu^2\not = 2s$, and then $s\not = 2$. Thus we have the following Proposition.

Proposition 3.1. Let $H\cong K_{2, s}$ be a star complements for $\mu = -2$. Then $s\neq 2$.

Theorem 3.2. The graphs $K_{2, 1}$, $K_{2, 10}$, $K_{2, 11}$, $K_{2, 12}$, $K_{2, 18}$, $K_{2, 20}$ and $K_{2, 27}$ are the only graphs among $K_{2, s}$ which can be star complements for $\mu = -2$.

Proof. Let $u \in X$ be a vertex of type $(a, b)$ which means that it has $a$ neighbours in $R$ and $b$ neighbours in $S$. Then $(a, b)\neq (0, 0)$ and $a \in \left\{0, 1, 2\right\}$, $0\leq b\leq s$.

Case 1: $a = 0$.

Then by (2.3), we have

Since $b$ is an integer, then $(2-s)^2+4\times 4(2-s) = (s-10)^2-64$ must be a perfect square, so $s\in \left\{2, 18, 20, 27\right\}$. Thus only $K_{2, 18}$, $K_{2, 20}$ and $K_{2, 27}$ can be star complements for $-2$ by Proposition 3.1.

Case 2: $a = 1$.

Then by (2.3), we have

Since $b$ is an integer, then $(2s)^2-4\times 2 \times (7s-12) = (2s-14)^2-100$ must be a perfect square, so $s\in \left\{2, 12, 20\right\}$. Thus only $K_{2, 12}$ and $K_{2, 20}$ can be star complements for $-2$ by Proposition 3.1.

Case 3: $a = 2$.

Then by (2.3), we have

Since $b$ is an integer, then $(2+s)^2-4\times 4\times (s-1) = (s-6)^2-16$ must be a perfect square, so $s\in \left\{1, 2, 10, 11\right\}$. Thus only $K_{2, 1}$, $K_{2, 10}$ and $K_{2, 11}$ can be star complements for $-2$ by Proposition 3.1.

Combining the above three cases, we complete the proof.

Recalling the definitions of a good vertex $u$, a good set $U$ and a good extension $H(U)$ in Section 2, we now proceed to identify all good sets $U$, i.e., to identify the sets $U$ for which graph $H(U)$ has $-2$ as an eigenvalue, where $H \in \left\{K_{2, 1}, K_{2, 10}, K_{2, 11}, K_{2, 12}, K_{2, 18}, K_{2, 20}, K_{2, 27}\right\}$. We denote the $a$-subset of $R$ by $R_a$ and the $b$-subset of $S$ by $S_b$, where $(R, S)$ is the bipartition of the graph $K_{2, s}$.

Lemma 3.3. For $\mu = -2$, we have

(1) $K_{2, 1}(U)$ is good if and only if $U = R_2$;

(2) $K_{2, 10}(U)$ is good if and only if $U = R_2\cup S_6$;

(3) $K_{2, 11}(U)$ is good if and only if $U\in\{R_2\cup S_5, R_2\cup S_8\}$;

(4) $K_{2, 12}(U)$ is good if and only if $U = R_1 \cup S_6$;

(5) $K_{2, 18}(U)$ is good if and only if $U = S_8$;

(6) $K_{2, 20}(U)$ is good if and only if $U\in\{S_6, S_{12}, R_1\cup S_4, R_1\cup S_{16}\}$;

(7) $K_{2, 27}(U)$ is good if and only if $U\in\{S_5, S_{20}\}$.

Proof. The integral solutions of (3.1), (3.2) and (3.3) are shown in Table 2.

By the definitions of a good vertex $u$, a good set $U$ and a good extension $H(U)$ in Section 2, Theorem 2.1, Corollary 2.3 and Table 2, we complete the proof.

Theorem 3.4. A Graph $G$ is a maximal graph with $H \cong K_{2, s}$ as a star complement for $\mu = -2$ if and only if the following two conditions hold:

$\rm (1)$ $H\in \left\{K_{2, 1}, K_{2, 10}, K_{2, 11}, K_{2, 12}, K_{2, 18}, K_{2, 20}, K_{2, 27}\right\}$.

$\rm (2)$ The vertex set $X$ such that $G-X = H$ satisfies the following $\rm(i)$ $\sim$ $\rm(iii)$:

$\rm (i)$ for any $u\in X$, $u$ is a good vertex, say, $N_H(u) = U$ satisfies Lemma 3.3;

$\rm (ii)$ for any two distinct vertices $u, v\in X$ of type $(a, b)$, $(c, d)$, respectively, $u, v$ are good partners, say, $\rho_{uv} = \left |N_H(u)\cap N_H(v)\right|$ and $a_{uv} = \left\{\begin{matrix} 1, & u \sim v \\ 0, & u \nsim v \end{matrix}\right.$ satisfy Table 3.

$\rm (iii)$ $X_U = \{U = N_H(u)\hskip.1cm |\hskip.1cm u\in X\}$ is a maximal family, say, there is no other family $X_U^{\prime}$ satisfies $\rm(i), (ii)$, and $X_U\subset X_U^{\prime}$.

Proof. By Proposition 2.5, Theorem 3.2, Lemma 3.3 and the definition of maximal, we only need to show (2.4) is equivalent to (ⅱ).

Since the proof is similar, we only show the case of $H = K_{2, 10}$. We note that $\mu = -2, t = 2, s = 10, a = c = 2, b = d = 6$, then

By similar way, we can complete the proof.

Now we want to characterize all the maximal graphs with the star complements $H$ given in Theorem 3.2 for $-2$. As mentioned in Reference ^[7], we can invoke an algorithm to find the maximal family by using a computer and thus find the maximal graphs. Now we're just focusing on the cases of $H\in\{K_{2, 1}, K_{2, 10}\}$.

Since $K_{2, 1}\cong S_3$, we have the following results by Theorem 3.2 in ^[18].

Theorem 3.5. (^[18]) The $4$-cycle $C_4$ is the unique maximal graph with $K_{2, 1}$ as a star complement for $\mu = -2$ which is the smallest eigenvalue of $C_4$.

Let $(R, S)$ be the bipartition of the graph $H = K_{2, 10}$ with $R = \left\{ 1', 2' \right\}$ and $S = \left\{ 1, 2, \dots, 10\right\}$. Now we characterize the maximal graph $G$ with the star complement $K_{2, 10}$ for $\mu = -2$.

Let $X = \left\{u_1, \dots, u_k \right\}$ be the star set for $\mu = -2$, and $X_U = \left\{U_1, \dots, U_k \right\}$ be the collection of good sets, where $U_i$ is the corresponding good set of vertex $u_i$. Then for each $1\leq i\leq k$, vertex $u_i$ is of type $(2, 6)$ and $U_i = \left\{1', 2'\right\}\cup V_i$ by Theorem 3.4, where $V_i$ is a $6$-subset of $S$. In addition, each pair of sets in $X_V = \left\{V_i \mid 1\leq i \leq k\right\}$ are compatible, which means $|V_i\cap V_j| = 2$ or 4 for any $1\leq i < j\leq k$ by $\rho_{uv} = 4$ or 6 from Table 3.

Therefore, finding the maximal graphs with $K_{2, 10}$ as a star complement for $\mu = -2$ is equivalent to finding the maximal family of the $6$-subsets of the $10$-set $S$ such that any two $6$-sets in the family has $2$ or $4$ common elements. If there exists a bijection of elements between two families, we say these two families are isomorphic.

Lemma 3.6. Let $S = \left\{ 1, 2, \dots, 10\right\}$ be a $10$-set. Then there exist exactly two non-isomorphic maximal families of $6$-subsets of $S$ such that any two $6$-sets in each family has $2$ or $4$ common elements.

Proof. Let $X_V = \left\{V_1, V_2, \dots, V_k \mid V_i\subset S, |V_i| = 6, 1\leq i\leq k\right\}$ be a maximal family such that each pair of sets in $X_V$ are compatible, which means $|V_i\cap V_j| = 2$ or 4 for any $1\leq i < j\leq k$.

Claim 1: Let $V_i, V_j \in X_V$. If $|V_i\cap V_j| = 4$, then $V_p = (V_i\cap V_j)\cup (S \setminus (V_i\cup V_j))\in X_V$.

Without loss of generality, we can assume that $V_i = \left\{1, 2, 3, 4, 5, 6\right\}$ and $V_j = \left\{1, 2, 3, 4, 7, 8\right\}$, then $V_p = \left\{1, 2, 3, 4, 9, 10\right\}$. Assume to the contrary, $V_p \notin X_V$. Then there exist a set $V_l\in X_V$ such that $|V_p\cap V_l| = 3$ or $5$ since any two 6-subsets has at least 2 common elements in 10-set $S$ and $X_V$ is maximal.

If $|V_p\cap V_l| = 3$, then $V_l$ contains three elements in $S\setminus V_p = \left\{5, 6, 7, 8\right\}$ and $|\{1, 2, 3, 4\}\cap V_l|\geq 1$, which implies one of $|V_i\cap V_l|$ and $|V_j\cap V_l|$ must be odd, it is a contradiction with $|V_i\cap V_l| = 2$ or 4, $|V_j\cap V_l| = 2$ or 4. If $|V_p\cap V_l| = 5$, we get a contradiction in a similar way. Thus $V_p \in X_V$. Claim 1 holds.

Claim 2: There are at least two sets in $X_V$ having exactly two elements in common.

Assume the contrary. Then any two sets in $X_V$ have exactly four elements in common. Without loss of generality, we can assume $V_1 = \left\{1, 2, 3, 4, 5, 6\right\}$, $V_2 = \left\{1, 2, 3, 4, 7, 8\right\} \in X_V$. Then by Claim 1, we have $V_3 = \left\{1, 2, 3, 4, 9, 10\right\}\in X_V$.

The maximality of $X_V$ implies that there exist other sets in $X_V$. Let $V_4 = \{a, b, c, d, e, f\}\in X_V$, where $1\leq a < b < c < d < e < f\leq 10$. Then $a\leq 4$, otherwise $V_4 = \{5, 6, 7, 8, 9, 10\}$ and $|V_4\cap V_i| = 2$ for any $i\in\{1, 2, 3\}$, it is a contradiction.

If $1\leq a < b < c < d\leq 4 < e < f \leq 10$, then there exist some $i\in\{1, 2, 3\}$ such that $|V_4\cap V_i|\geq 5$, it is a contradiction; if $1\leq a < b\leq 4 < c < d < e < f \leq 10$, then there exist some $i\in\{1, 2, 3\}$ such that $|V_4\cap V_i|\leq 3$, it is a contradiction; if $1\leq a\leq 4 < b < c < d < e < f \leq 10$, then for any $i\in\{1, 2, 3\}$, we have $|V_4\cap V_i|\leq 3$, it is a contradiction. Thus $1\leq a < b < c\leq 4 < d < e < f \leq 10$.

Clearly, $d\in\{5, 6\}, e\in\{7, 8\}, f\in\{9, 10\}$ by the fact $|V_4\cap V_i| = 4$ for any $i\in\{1, 2, 3\}$ and $1\leq a < b < c\leq 4 < d < e < f \leq 10$. Without loss of generality, we take $V_4 = \left\{a, b, c, 5, 7, 9\right\}\in X_V$. By Claim 1, we have $V_5 = \left\{a, b, c, 5, 8, 10\right\}$, $V_6 = \left\{a, b, c, 6, 7, 10\right\}$, $V_7 = \left\{a, b, c, 6, 8, 9\right\} \in X_V$, and we can check that any other set $V_8 = \left\{a', b', c', d', e', f'\right\}$ such that $1\leq a' < b' < c'\leq 4 < d' < e' < f' \leq 10$ cannot have four elements in common with each of $V_1, \dots, V_7$, so $X_V = \{V_1, V_2, \dots, V_7\}$.

Let $V_9 = \left\{a, b, g, 5, 7, 10\right\}$, $g\in\{1, 2, 3, 4\}\setminus \{a, b, c\}$. We can check that $|V_9\cap V_i| = 4$ for $1\leq i\leq 6$ and $|V_9\cap V_7| = 2$. Therefore, $X_V\cup\{V_9\}\supseteq X_V$, it implies a contradiction with the maximality of $X_V$. Thus there exists at least two sets in $X_V$ having exactly two elements in common. Claim 2 holds.

Claim 3: Let $V_i, V_j \in X_V$. If $V_i\cap V_j = \{a, b\}$, then for any $V_p\in X_V$, $\{a, b\}\subseteq V_p$ or $\{a, b\}\cap V_p = \phi$.

Without loss of generality, we can assume $V_1 = \left\{1, 2, 3, 4, 5, 6\right\}$, $V_2 = \left\{1, 2, 7, 8, 9, 10\right\} \in X_V$. If $V_3\in X_V$ and $|\{1, 2\}\cap V_3| = 1$, then one of $|V_1\cap V_3|$ and $|V_2\cap V_3|$ must be odd, it is a contradiction. Then Claim 3 holds.

Now we study the structure of $X_V$. Due to Claim 2, we can assume $V_1 = \left\{1, 2, 3, 4, 5, 6\right\}$, $V_2 = \left\{1, 2, 7, 8, 9, 10\right\} \in X_V$. By Claim 3, we consider the following two cases.

Case 1: Each set in $X_V$ contains elements $1$ and $2$.

In this case, every set in $X_V$ has the form $\left\{1, 2, c, d, e, f\right\}$ where $3\leq c < d\leq 6$ and $7\leq e < f\leq 10$ by $|V_i\cap V_j| = 2$ or 4 for any $V_i, V_j\in X_V$, and the symmetry between $\{3, 4, 5, 6\}$ and $\{7, 8, 9, 10\}$. If we divide 3, 4, 5, and 6 into two groups of two numbers, there are three ways to divide them, say, $\{3, 4\}$ and $\{5, 6\}$, $\{3, 5\}$ and $\{4, 6\}$, $\{3, 6\}$ and $\{4, 5\}$. For example, we take divide 3, 4, 5, and 6 into $\{3, 4\}$ and $\{5, 6\}$, then in the sense of isomorphism, we have $2\times 2 = 4$ ways to take $\left\{c, d, e, f\right\}$, say, $\{3, 4, 7, 8\}$, $\{3, 4, 9, 10\}$, $\{5, 6, 7, 8\}$, $\{5, 6, 9, 10\}$. Then $|X_V|\leq 1+1+3\times 4 = 14$.

Without loss of generality, we can assume that $V_3 = \left\{1, 2, 3, 4, 7, 8\right\}$, $V_4 = \left\{1, 2, 3, 5, 7, 9\right\}$, $V_{5} = \left\{1, 2, 3, 6, 7, 10\right\}$. By Claim 1, we have $V_6 = \left\{1, 2, 3, 4, 9, 10\right\}\in X_V$, $V_7 = \left\{1, 2, 5, 6, 7, 8\right\}\in X_V$, $V_8 = \left\{1, 2, 3, 5, 8, 10\right\}\in X_V$, $V_9 = \left\{1, 2, 4, 6, 7, 9\right\}\in X_V$, $V_{10} = \left\{1, 2, 3, 6, 8, 9\right\}\in X_V$, $V_{11} = \left\{1, 2, 5, 6, 9, 10\right\}\in X_V$, $V_{12} = \left\{1, 2, 4, 6, 8, 10\right\}\in X_V$, $V_{13} = \left\{1, 2, 4, 5, 8, 9\right\}\in X_V$, $V_{14} = \left\{1, 2, 4, 5, 7, 10\right\}\in X_V$.

It is easy to check that every pair $V_i, V_{j}\ (1\leq i, j\leq 14)$ are compatible. Then $|X_V| = 14$, say, $X_V$ is a maximal family.

Case 2: There exists a set in $X_V$ does not contain elements $1$ and $2$.

Let $V_3'\in X_V$ be a set that does not contain elements $1$ and $2$. Then it must have two elements in common with one of sets $V_1$, $V_2$ and four elements in common with the other. In the sense of isomorphism, noting that the symmetry between $\{3, 4, 5, 6\}$ and $\{7, 8, 9, 10\}$, $\{3, 4\}$ and $\{5, 6\}$, $\{7, 8\}$ and $\{9, 10\}$, we can assume $V_3' = \left\{3, 4, 5, 6, 7, 8\right\}$.

Subcase 2.1: $V_{4}' = \left\{3, 4, 7, 8, 9, 10\right\}\in X_V$.

Then by Claim 1, we have $V_5' = \left\{3, 4, 5, 6, 9, 10\right\}$, $V_{6}' = \left\{1, 2, 3, 4, 9, 10\right\}$, $V_{7}' = \left\{5, 6, 7, 8, 9, 10\right\}$, $V_{8}' = \left\{1, 2, 5, 6, 9, 10\right\}$, $V_{9}' = \left\{1, 2, 5, 6, 7, 8\right\}$, $V_{10}' = \left\{1, 2, 3, 4, 7, 8\right\}\in X_V$.

It is easy to check that any two set of $\{V_1, V_2, V_3', \dots, V_{10}' \}$ are compatible, say, having two or four common elements. Thus $\{V_1, V_2, V_3', \dots, V_{10}' \}\subseteq X_V$.

Now we show $X_V = \{V_1, V_2, V_3', \dots, V_{10}' \}$. Otherwise, we can assume that there exists $V_{11}'\in X_V$. For the five sets $W_1 = \{1, 2\}, W_2 = \{3, 4\}, W_3 = \{5, 6\}, W_4 = \{7, 8\}, W_5 = \{9, 10\}$, any 6-set formed by the union of three 2-sets from $\{W_1, W_2, W_3, W_4, W_5\}$ is in $\{V_1, V_2, V_3', \dots, V_{10}' \}$. Then there exist at least two sets $W_i, W_j$ such that $|W_i\cap V_{11}'| = |W_j\cap V_{11}'| = 1$ for $2\leq i < j\leq 5$ by Claim 3.

Without loss of generality, we assume that $3, 5\in V_{11}'$ and $4, 6\notin V_{11}'$, then one of $|V_{11}'\cap V_{6}'|$, $|V_{11}'\cap V_{7}'|$ and $|V_{11}'\cap V_{10}'|$ is odd, it is a contradiction because any two set of $X_V$ are compatible.

Combining the above arguments, we have $X_V = \{V_1, V_2, V_3', \dots, V_{10}' \}$ is another maximal family.

Subcase 2.2: $V_{4}' = \left\{3, 4, 7, 8, 9, 10\right\}\notin X_V$.

Then there exist a set $V_m\in X_V$ such that $|V_m\cap V_4'| = 3$ or $5$ since any two 6-subsets has at least 2 common elements in 10-set $S$.

If $|V_m\cap V_4'| = 3$, then $V_m$ contains three elements in $S\setminus V_4' = \left\{1, 2, 5, 6\right\}$. By Claim 3, $\{1, 2\}\subseteq V_m$ and thus $|V_m\cap \{5, 6\}| = 1$. Since $|V_m| = 6$, $|V_m\cap V_2| = 2$ or 4, we have $|V_m\cap \{7, 8, 9, 10\}| = 2$, $|V_m\cap \{3, 4\}| = 1$. Without loss of generality, we assume that $V_m = \{1, 2, 3, 5, 7, 8\}$. By Claim 1 and $V_1, V_2, V_3', V_m$, we can obtain a new maximal family $X_V^1$.

Let $\psi$ be a mapping from $S$ to $S$ such that $\psi(3) = 6$, $\psi(6) = 3$ and $\psi(a) = a$ for any $a\in S\backslash \{3, 6\}$. Then $\psi$ is a bijection, thus $X_V^1$ and $\{V_1, V_2, V_3', \dots, V_{10}' \}$ are isomorphic.

If $|V_m\cap V_4'| = 5$, then $V_m$ contains one elements in $S\setminus V_4' = \left\{1, 2, 5, 6\right\}$. By Claim 3, $\{1, 2\}\not\subseteq V_m$ and thus $|V_m\cap \{5, 6\}| = 1$. Since $|V_m| = 6$, $|V_m\cap V_2| = 2$ or 4, we have $|V_m\cap \{7, 8, 9, 10\}| = 4$, $|V_m\cap \{3, 4\}| = 1$. Without loss of generality, we assume that $V_m = \{3, 5, 7, 8, 9, 10\}$. By Claim 1 and $V_1, V_2, V_3', V_m$, we can obtain another new maximal family $X_V^2$.

Let $\varphi$ be a mapping from $S$ to $S$ such that $\varphi(4) = 5$, $\varphi(5) = 4$ and $\varphi(a) = a$ for any $a\in S\backslash \{4, 5\}$. Then $\varphi$ is a bijection, $X_V^2$ and $\{V_1, V_2, V_3', \dots, V_{10}' \}$ are isomorphic.

Combining the above two subcases, we obtain another maximal family $X_V = \{V_1, V_2, V_3', \dots, V_{10}' \}$.

By Case 1 and Case 2, we complete the proof.

Let $(R, S)$ be the bipartition of $H = K_{2, 10}$ with $R = \left\{ 1', 2' \right\}$, $S = \left\{ 1, 2, \dots, 10\right\}$. We define two graphs $G_1, G_2$ as follows:

(1) $X = \{u_1, u_2, \dots, u_{14}\}, \ V(G_1) = V(H)\cup X,$ and $G_1[X] = K_{14}-u_1u_2-u_3u_{11}-u_4u_{12}-u_{5}u_{13}-u_6u_7-u_8u_9-u_{10}u_{14},$ and $N_H(u_{1}) = \left\{1', 2', 1, 2, 3, 4, 5, 6\right\}, \ N_H(u_{2}) = \left\{1', 2', 1, 2, 7, 8, 9, 10\right\}$, $N_H(u_{3}) = \left\{1', 2', 1, 2, 3, 4, 7, 8\right\}$, $N_H(u_{4}) = \left\{1', 2', 1, 2, 3, 5, 7, 9\right\}$, $N_H(u_{5}) = \left\{1', 2', 1, 2, 3, 6, 7, 10\right\}$, $N_H(u_{6}) = \left\{1', 2', 1, 2, 3, 4, 9, 10\right\}$, $N_H(u_{7}) = \left\{1', 2', 1, 2, 5, 6, 7, 8\right\}$, $N_H(u_{8}) = \left\{1', 2', 1, 2, 3, 5, 8, 10\right\}$, $N_H(u_{9}) = \left\{1', 2', 1, 2, 4, 6, 7, 9\right\}$, $N_H(u_{10}) = \left\{1', 2', 1, 2, 3, 6, 8, 9\right\}$, $N_H(u_{11}) = \left\{1', 2', 1, 2, 5, 6, 9, 10\right\}$, $N_H(u_{12}) = \left\{1', 2', 1, 2, 4, 6, 8, 10\right\}$, $N_H(u_{13}) = \left\{1', 2', 1, 2, 4, 5, 8, 9\right\}$, $N_H(u_{14}) = \left\{1', 2', 1, 2, 4, 5, 7, 10\right\}$.

(2) $X = \{v_1, v_2, \dots, v_{10}\}$, $V(G_2) = V(H)\cup X$, and $G_2[X] = K_{10}-v_1v_2-v_1v_4-v_1v_{7}-v_2v_3-v_2v_5-v_{3}v_{6}-v_{3}v_{8}-v_{4}v_{8}$ - $v_{4}v_{9}-v_{5}v_{9}-v_{5}v_{10}-v_{6}v_{7}-v_{6}v_{9}-v_{7}v_{10}-v_{8}v_{10}$, and $N_H(v_{1}) = \left\{1', 2', 1, 2, 3, 4, 5, 6\right\}$, $N_H(v_{2}) = \left\{1', 2', 1, 2, 7, 8, 9, 10\right\}$, $N_H(v_{3}) = \left\{1', 2', 3, 4, 5, 6, 7, 8\right\}$, $N_H(v_{4}) = \left\{1', 2', 3, 4, 7, 8, 9, 10\right\}$, $N_H(v_{5}) = \left\{1', 2', 3, 4, 5, 6, 9, 10\right\}$, $N_H(v_{6}) = \left\{1', 2', 1, 2, 3, 4, 9, 10\right\}$, $N_H(v_{7}) = \left\{1', 2', 5, 6, 7, 8, 9, 10\right\}$, $N_H(v_{8}) = \left\{1', 2', 1, 2, 5, 6, 9, 10\right\}$, $N_H(v_{9}) = \left\{1', 2', 1, 2, 5, 6, 7, 8\right\}$, $N_H(v_{10}) = \left\{1', 2', 1, 2, 3, 4, 7, 8\right\}$.

Clearly, $G_1$ has $26$ vertices, where $2$ vertices of degree $24$, $14$ vertices of degree $20$, $2$ vertices of degree $16$, and $8$ vertices of degree $9$, its spectrum is $[-4.70096, -2^{14}, 0^2, 0.66031, 2^7, 18.04065]$; $G_2$ has $22$ vertices, where $2$ vertices of degree $20$, $10$ vertices of degree $14$, and $10$ vertices of degree $8$, its spectrum is $[-4.71780, -2^{10}, 0^6, 3^4, 12.71780]$.

By Theorem 3.4 and Lemma 3.6, we can conclude that there are exactly two non-isomorphic maximal graphs with $K_{2, 10}$ as a star complement for $\mu = -2$.

Theorem 3.7. Let $G$ be a graph with $K_{2, 10}$ as a star complement for $\mu = -2$. Then $G$ is maximal if and only if $G\cong G_1$ or $G\cong G_2$.

Remark 3.8. Let $S = \left\{ 1, 2, \dots, 10\right\}$, $S_1, S_2, \dots, S_{210}$ be all the 6-subsets of $S$. We construct a graph $G^X$ of order $210$ with $V(G^X) = \{v_1, v_2, \dots, v_{210}\}$ and $v_iv_j\in E(G^X)$ if $|S_i\cap S_j| = 2$ or 4.

Then finding the maximal graphs with $H\cong K_{2, 10}$ as a star complement for $\mu = -2$ is equivalent to finding the maximal family of the $6$-subsets of a $10$-set such that the intersection of any two 6-sets in the family has $2$ or $4$ elements, is equivalent to finding all maximal cliques in $G^X$.

By Lemma 3.6, $G^X$ has two maximal cliques in the sense of isomorphism, one is order 14 and the other is order 10. When $H \in \left\{K_{2, 11}, K_{2, 12}, K_{2, 18}, K_{2, 20}, K_{2, 27}\right\}$, we can study the maximal graphs by a similar way, and now we ignore the characterization.

Finally, it is obvious to obtain the following result.

Corollary 3.9. $K_{2, 10}$, $K_{2, 11}$, $K_{2, 12}$, $K_{2, 18}$, $K_{2, 20}$ and $K_{2, 27}$ are the only graphs among $K_{2, s}$ which can be star complements for the second smallest eigenvalue $\lambda_{n-1} = -2$.

Proof. Let $G$ be a graph of order $n$ with $H$ as a star complement for an eigenvalue $-2$ of multiplicity $n-s-2$, where $H\cong K_{2, s}\ (s > 2)$. We know that $K_{2, s}$ has spectrum: $0^s$, $-\sqrt{2s}$, $\sqrt{2s}$. If $s > 2$, then

By Lemma 2.6, we have $\lambda_{s+2}(G) = \lambda_{s+3}(G) = \cdots = \lambda_{n-1}(G) = -2$.

3.2.   $\mu=1$

In this subsection, we study the maximal graphs with $K_{2, s}$ as a star complement for $\mu = 1$. Clearly, 1 is not an eigenvalue of $K_{2, s}$. Then by (2.3), we have

Theorem 3.10. $K_{2, 5}$ and $K_{2, 13}$ are the only two graphs among $K_{2, s}$ which can be star complements for $\mu = 1$.

Proof. Let $u \in X$ be a vertex of type $(a, b)$ which means that it has $a$ neighbours in $R$ and $b$ neighbours in $S$. Then $(a, b)\neq (0, 0)$ and $a \in \left\{0, 1, 2\right\}$, $0\leq b\leq s$.

If $a = 0$, then by (2.3), we have

Since $b$ is an integer, then $(1-2s)^2-8\times (2s-1) = (2s-5)^2-16$ must be a perfect square, so $s = 5$. Therefore, only $K_{2, 5}$ can be a star complement for $\mu = 1$.

If $a = 1$, then by (2.3), we have

Since $b$ is an integer, then $(3-2s)^2-8s = (2s-5)^2-16$ must be a perfect square, so $s = 5$. Therefore, only $K_{2, 5}$ can be a star complement for $\mu = 1$.

If $a = 2$, then by (2.3), we have

Since $b$ is an integer, then $(5-2s)^2-8\times (1+2s) = (2s-9)^2-64$ must be a perfect square, so $s = 13$. Therefore, only $K_{2, 13}$ can be a star complement for $\mu = 1$.

Combining the above arguments, we complete the proof.

Recalling the definitions of good vertex $u$, good set $U$ and good extension $H(U)$ in Section 2, we now proceed to identify all good sets $U$, i.e., to identify the sets $U$ for which graph $H(U)$ has $1$ as an eigenvalue, where $H \in \left\{K_{2, 5}, K_{2, 13}\right\}$. We denote the $a$-subset of $R$ by $R_a$ and the $b$-subset of $S$ by $S_b$, where $(R, S)$ is the bipartition of the graph $K_{2, s}$.

Lemma 3.11. For $\mu = 1$, we have

(1) $K_{2, 5}(U)$ is good if and only if $U\in\{S_3, R_1\cup S_1\}$;

(2) $K_{2, 13}(U)$ is good if and only if $U = R_2\cup S_9$.

Proof. The integral solutions of (3.4), (3.5) and (3.6) are shown in Table 4.

By the definitions of good vertex $u$, good set $U$ and good extension $H(U)$ in Section 2, Theorem 2.1, Corollary 2.3 and Table 4, we complete the proof.

When $H\cong K_{2, 5}$, ^[11] characterized the unique maximal graph with $K_{2, 5}$ as a star complement for $\mu = 1$.

Theorem 3.12. (^[11]) The complement of Schl$\ddot{a}$fli graph is the unique maximal graph with $K_{2, 5}$ as a star complement for $\mu = 1$.

Theorem 3.13. Let $H\cong K_{2, 13}$. Then $G$ is the maximal graph with $H$ as a star complement for $\mu = 1$ if and only if the vertex set $X$ such that $G-X = H$ satisfies the following three conditions:

$\rm (1)$ for any $u\in X$, $u$ is a good vertex, say, $N_H(u) = U = R_2\cup S_9$;

$\rm (2)$ for any two distinct vertices $u, v\in X$ of type $(a, b)$, $(c, d)$, respectively, $u, v$ are good partners, say, $\rho_{uv} = |N_H(u)\cap N_H(v)| = \begin{cases} 9, & \mathit{\rm{if}} u \sim v, \\ 10, & \mathit{\rm{if}} u \nsim v. \end{cases}$

$\rm (3)$ $X_U = \{U = N_H(u)\hskip.1cm |\hskip.1cm u\in X\}$ is a maximal family, say, there is no other family $X_U^{\prime}$ satisfies $\rm(1), (2)$, and $X_U\subset X_U^{\prime}$.

Proof. By Proposition 2.5, Theorem 3.2, Lemma 3.11 and the definition of maximal, we only need to show (2.4) is equivalent to (2).

We note that $\mu = 1, t = 2, s = 13, a = c = 2, b = d = 9$, then

Remark 3.14. Let $(R, S)$ be the bipartition of the graph $H = K_{2, 13}$ with $R = \left\{ 1', 2' \right\}$ and $S = \left\{ 1, 2, \dots, 13\right\}$, $X = \left\{u_1, \dots, u_k \right\}$ be the star set for $\mu = 1$, and $X_U = \left\{U_1, \dots, U_k \right\}$ be the collection of good sets, where $U_i$ is the corresponding good set of vertex $u_i$. Then for each $1\leq i\leq k$, vertex $u_i$ is of type $(2, 9)$ and $U_i = \left\{1', 2'\right\}\cup F_i$ by Lemma 3.11, where $F_i$ is a $9$-subset of $S$. In addition, each pair of sets in $\mathcal{F} = \left\{F_i \mid 1\leq i\leq k\right\}$ are compatible, which means $|F_i\cap F_j| = 7$ or 8 for any $1\leq i < j\leq k$ by $\rho_{uv} = 9$ or 10 from Theorem 3.13.

Therefore, finding the maximal graphs with $K_{2, 13}$ as a star complement for $\mu = 1$ is equivalent to finding the non-isomorphic maximal family of the $9$-subsets of the $13$-set $S$ such that any two $9$-sets in the family has $7$ or $8$ common elements.

As mentioned in Reference ^[7], we can invoke an algorithm to find the maximal family by using a computer and thus find the maximal graphs. Now we only give two examples to illustrate the existence of maximal families.

Example 3.15. Let $S = \left\{ 1, 2, \dots, 13\right\}$, $F_1 = \{1, 2, \dots, 9\}$, $\overline{F_1} = \{10, 11, 12, 13\}$, and $\mathcal{F} = \{F_1\}\bigcup \{F_i\mid |F_i\cap F_1| = 8, |F_i\cap \overline{F_1}| = 1\}$ be a family of 9-subsets of $S$. Then $\mathcal{F}$ is a maximal family such that any two sets in $\mathcal{F}$ has $7$ or $8$ common elements.

Proof. First, we prove that all sets in $\mathcal{F}$ are compatible. For any $F_i\in \mathcal{F}\backslash {F_1}$, we have $|F_1\cap F_i| = 8$. For any two sets $F_i, F_j\in \mathcal{F}\backslash {F_1}$, $i\neq j$, if $(F_i\cap \overline{F_1})\cap (F_j\cap \overline{F_1}) = \varnothing$, then $|(F_i\cap F_1)\cap (F_j\cap F_1)| = 7$ or $8$ since $|F_1| = 9$, $|F_1\cap F_i| = 8$ and $|F_1\cap F_j| = 8$, thus $|F_i\cap F_j| = 7$ or $8$; if $|(F_i\cap \overline{F_1})\cap (F_j\cap \overline{F_1})| = 1$, then $|(F_i\cap F_1)\cap (F_j\cap F_1)| = 7$ since $F_i\not = F_j$, thus $|F_i\cap F_j| = 8$. Therefore, all sets in $\mathcal{F}$ are compatible.

Next, we prove that the family is maximal. Assume to the contrary, if $\mathcal{F}$ is not maximal, then there is a set $F\not\in \mathcal{F}$ such that $|F| = 9$ and $F$ is compatible with all sets in $\mathcal{F}$, say, $|F\cap F_i| = 7$ or $8$ for any $F_i\in \mathcal{F}$. Since $F_1 = \{1, 2, \dots, 9\}\in \mathcal{F}$, we have $|F\cap F_1| = 7$ or $8$.

If $|F\cap F_1| = 8$, then $F \in \mathcal{F}$, it implies a contradiction. If $|F\cap F_1| = 7$, without loss of generality, we assume that $F = \{1, 2, 3, 4, 5, 6, 7, 10, 11\}$, then there is a set $F_q = \{2, 3, 4, 5, 6, 7, 8, 9, 12\}\in \mathcal{F}$ such that $|F\cap F_q| = 6$, it is a contradiction.

Therefore, $\mathcal{F}$ is a maximal family such that the intersection of any two sets in $\mathcal{F}$ has $7$ or $8$ elements.

Example 3.16. Let $S = \left\{ 1, 2, \dots, 13\right\}$, $F_1 = \{1, 2, \dots, 9\}$, $\overline{F_1} = \{10, 11, 12, 13\}$, $S_1 = \{1, 2, \dots, 7\}$, $S_2 = \{1, 2, \dots, 7, 8\}$, $S_3 = \{1, 2, \dots, 7, 9\}$, and $\mathcal{F}^* = \{F_1\}\bigcup\{F_i\mid S_1\subseteq F_i, \hskip.15cm |F_i\cap \overline{F_1}| = 2\} \bigcup\{F_i\mid S_2\subseteq F_i, \hskip.15cm |F_i\cap \overline{F_1}| = 1\} \bigcup\{F_i\mid S_3\subseteq F_i, \hskip.15cm |F_i\cap \overline{F_1}| = 1\}$ be a family of 9-subsets of $S$. Then $\mathcal{F}^*$ is a maximal family such that the intersection of any two sets in $\mathcal{F}^*$ has $7$ or $8$ elements.

Proof. First, we prove that all sets in $\mathcal{F}^*$ are compatible. For any two sets $F_p, F_q \in \mathcal{F}^*$, we have $|F_p\cap F_q|\geq 7$ since $|S_1\cap S_2| = |S_1\cap S_3| = |S_2\cap S_3| = 7$. On the other hand, $|F_p| = |F_q| = 9$, and $F_p\not = F_q$, thus $|F_p\cap F_q| = 7$ or $8$. Therefore, all sets in $\mathcal{F}^*$ are compatible.

Next, we prove that the family is maximal. Assume to the contrary, if $\mathcal{F}^*$ is not maximal, then there is a set $F\not\in \mathcal{F}^*$ such that $|F| = 9$ and $F$ is compatible with all sets in $\mathcal{F}^*$, say, $|F\cap F_i| = 7$ or $8$ for any $F_i\in \mathcal{F}^*$. Since $F_1 = \{1, 2, \dots, 9\}\in \mathcal{F}^*$, we have $|F\cap F_1| = 7$ or $8$.

Case 1: $|F\cap F_1| = 7$.

Then $|F\cap S_1| = 5, 6$ or $7$. If $|F\cap S_1| = 7$, then $F\in \{F_i\mid S_1\subseteq F_i, \hskip.15cm |F_i\cap \overline{F_1}| = 2\}\subseteq \mathcal{F}^*$, it is a contradiction. If $|F\cap S_1| = 6$, without loss of generality, we assume that $F = \{1, 2, 3, 4, 5, 6, 8, 10, 11\}$, then there is a set $F_l = \{1, 2, 3, 4, 5, 6, 7, 12, 13\}\in\{F_i\mid S_1\subseteq F_i, \hskip.15cm |F_i\cap \overline{F_1}| = 2\}\subseteq \mathcal{F}^*$ such that $|F\cap F_l| = 6$, it is a contradiction. If $|F\cap S_1| = 5$, without loss of generality, we assume that $F = \{1, 2, 3, 4, 5, 8, 9, 10, 11\}$, then there is a set $F_l = \{1, 2, 3, 4, 5, 6, 7, 12, 13\}\in\mathcal{F}^*$ such that $|F\cap F_l| = 5$, it is a contradiction.

Case 2: $|F\cap F_1| = 8$.

Then $|F\cap S_1| = 6$ or 7. If $|F\cap S_1| = 7$, then $F\in \{F_i\mid S_2\subseteq F_i, \hskip.15cm |F_i\cap \overline{F_1}| = 1\} \bigcup\{F_i\mid S_3\subseteq F_i, \hskip.15cm |F_i\cap \overline{F_1}| = 1\}\subseteq \mathcal{F}^*$, it is a contradiction. If $|F\cap S_1| = 6$, without loss of generality, we assume that $F = \{1, 2, 3, 4, 5, 6, 8, 9, 10\}$, then there is a set $F_l = \{1, 2, 3, 4, 5, 6, 7, 12, 13\}\in\mathcal{F}^*$ such that $|F\cap F_l| = 6$, it is a contradiction.

Combining the above arguments, $\mathcal{F}^*$ is a maximal family such that the intersection of any two sets in $\mathcal{F}^*$ has $7$ or $8$ elements.

Corollary 3.17. $K_{2, 5}$ and $K_{2, 13}$ are the only graphs among $K_{2, s}$ which can be star complements for the second largest eigenvalue $\lambda_{2} = 1$.

Proof. Let $G$ be a graph of order $n$ with $H$ as a star complement for an eigenvalue $1$ of multiplicity $k$, where $H\cong K_{2, s}$. We know that $K_{2, s}$ has spectrum: $0^s$, $-\sqrt{2s}$, $\sqrt{2s}$, then

By Lemma 2.6, we have $\lambda_{2}(G) = \lambda_{3}(G) = \cdots = \lambda_{1+k}(G) = 1$.

4.   The cases of other eigenvalues and some remarks

By Table 1, we can see that the known research on the maximal graph with $H$ as a star complement is about a relatively small eigenvalue, such as $1$ and $-2$. We are curious about what will happen to the maximal graph when the eigenvalue becomes larger.

In this section, we will study the maximal graphs with $K_{2, s}$ as a star complement for other eigenvalues, such as $\mu = 2, 3, -3, 4$.

Proposition 4.1. The only graphs among $K_{2, s}$ which can be star complements for $\mu = 2, -3, 3, 4$ are shown in Table 5.

Proof. We only prove the case of $\mu = 2$. The proofs for $\mu = -3, 3, 4$ are similar, so we omit them.

Let $u \in X$ be a vertex of type $(a, b)$ which means that it has $a$ neighbours in $R$ and $b$ neighbours in $S$. Then $(a, b)\neq (0, 0)$ and $a \in \left\{0, 1, 2\right\}$, $0\leq b\leq s$.

By (2.3), $\mu = 2$ and $t = 2$, we have

Since $b$ is an integer, the discriminant of (4.1), $4s^2-80s-8sa^2+16a^2+144$ must be a perfect square. Table 6 shows the possible values of $s$ and $(s, b)$ when $a = 0, 1, 2$.

Since $\mu = 2$ is not the eigenvalue of $H\cong K_{2, s}$, so $\mu^2\not = 2s$, and then $s\not = 2$. Therefore only $K_{2, 1}$, $K_{2, 18}$, $K_{2, 20}$, $K_{2, 26}$, $K_{2, 27}$, $K_{2, 29}$, $K_{2, 34}$, $K_{2, 51}$ and $K_{2, 52}$ can be star complements for $\mu = 2$.

Similar to the cases of $\mu = 1$ and $\mu = -2$, we can study the maximum graphs. Now we only characterize the following cases.

Firstly, we define two graph $G_3$ and $G_4$. Let $(R, S)$ be the bipartition of $H = K_{2, 4}$ with $R = \left\{ 1', 2' \right\}$, $S = \left\{ 1, 2, 3, 4\right\}$. We define a graph $G_3$ as follows: $X = \{u\}$, $V(G_3) = V(H)\cup X$, and $N_H(u) = \left\{1', 2', 1\right\}$ (see Figure 1). The spectrum of $G_3$ is $[-3, -1, 0^3, 0.58579, 3.41421]$.

Let $(R', S')$ be the bipartition of $H = K_{2, 6}$ with $R' = \left\{ 1', 2' \right\}$, $S' = \left\{ 1, 2, \dots, 6\right\}$. We define a graph $G_4$ as follows: $X = \{v\}$, $V(G_4) = V(H)\cup X$, and $N_H(v) = \left\{1', 1, 2, 3\right\}$ (see Figure 2). The spectrum of $G_4$ is $[-3.51414, -1.57199, 0^5, 1.08613, 4]$.

Theorem 4.2. The graph $G$ shown in Table 7 is the only graph with $H$ as a star complement for eigenvalue $\mu$.

Proof. When $\mu = 2$ and $H = K_{2, 1}$, it is clear that $a = c = 2,$ $b = d = 0$ by Proposition 4.1. By Proposition 2.5 and $\mu = 2$, $t = 2, s = 1$, we have $G$ is the graph with $K_{2, 1}$ as a star complement for $\mu = 2$ if and only if the vertex set $X$ satisfies $G-X = H$ and the following two conditions:(1) for any $u\in X$, $u$ is of type $(2, 0)$; (2) for any two vertices $u, v\in X$, we have $2a_{uv}+\rho_{uv}+2 = 0$.

But $\rho_{uv}\geq 0$ and $a_{uv} = 0$ or $1$ imply $|X| = 1$. Therefore, there is a unique (maximal) graph $K_{2, 2}$ with $K_{2, 1}$ as a star complement for $\mu = 2$.

Similarly, we can prove other cases in Table 7.

Remark 4.3. Let $G$ be a maximal graph with $K_{2, s}$ as a star complements for $\mu$. In order to study $G$, the first thing we need to do is to determine what value of $s$ that allows $K_{2, s}$ to be viewed as a star complement for a given eigenvalue. We compare the graphs among $K_{2, s}$ which can be star complements for distinct eigenvalues, for example, $\mu = 1$, $\mu = -2$, $\mu = 2$, $\mu = 3$, $\mu = -3$ and $\mu = 4$ (see Theorem 3.10, Theorem 3.2 and Table 5), and we find that:

(1) there are only two graphs among $K_{2, s}$ as star complements for $\mu = 1$;

(2) there are only seven graphs among $K_{2, s}$ as star complements for $\mu = -2$ and nine for $\mu = 2$;

(3) there are only eleven graphs among $K_{2, s}$ as star complements for $\mu = -3$ and ten for $\mu = 3$;

(4) there are nineteen graphs among $K_{2, s}$ as star complements for $\mu = 4$;

(5) as the absolute value of $\mu$ gets larger and larger, the value and the number of $s$ get larger and larger; even though the absolute values are the same, it seems that the value of $s$ corresponding to the positive eigenvalues is larger than the one corresponding to the negative eigenvalues.

It seems that (5) explains why known research choose eigenvalues with small absolute value for study.

It is well known that for any graph $G$, there exists at least one star partition (^[7]). The fact implies there exist star sets and star complements for any eigenvalue of any graph $G$. Then what graphs can not be as star complements for some given eigenvalues seems to be an interesting question worth studying.

Acknowledgments

The authors would like to thank the referees for their valuable comments, corrections, and suggestions, which lead to an improvement of the original manuscript.

The research is supported by the National Natural Science Foundation of China (Grant No. 11971180), the Guangdong Provincial Natural Science Foundation (Grant No. 2019A1515012052).

Conflict of interest

The authors declare that they have no competing interests.