# Integral Laplacian graphs with a unique double Laplacian eigenvalue, II

Abdul Hameed  School of Mathematical Sciences, Shanghai Jiao Tong University,
Shanghai, P.R.China<EMAIL_ADDRESS>and  Mikhail Tyaglov  School
of Mathematical Sciences, CMA-Shanghai, and MOE-LSC, Shanghai Jiao Tong
University, Shanghai, P.R.China  Department of Mathematics and Computer
Sciences, St. Petersburg State University, St.Peterburg, 199178, Russia
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

The set
$S_{\\{i,j\\}_{n}^{m}}=\\{0,1,2,\ldots,m-1,m,m,m+1,\ldots,n-1,n\\}\setminus\\{i,j\\},\quad
0<i<j\leqslant n$, is called Laplacian realizable if there exists a simple
connected graph $G$ whose Laplacian spectrum is $S_{\\{i,j\\}_{n}^{m}}$. In
this case, the graph $G$ is said to realize $S_{\\{i,j\\}_{n}^{m}}$. In this
paper, we completely describe graphs realizing the sets
$S_{\\{i,j\\}_{n}^{m}}$ with $m=1,2$ and determine the structure of these
graphs.

###### Key words and phrases:

Laplacian Integral graph, Laplacian matrix, Laplacian spectrum, integer
eigenvalues

##  1\. Introduction

In the present paper, we continue our previous work [12] where we studied
graphs whose Laplacian spectrum is

$S_{\\{i,j\\}_{n}^{m}}=\\{0,1,2,\ldots,m-1,m,m,m+1,\ldots,n-1,n\\}\setminus\\{i,j\\},\quad
0<i<j\leqslant n,$

with $m=n-1,n$. Here we cover the cases $m=1,2$ and give a complete
description of the correspondent graphs but certain cases directly related to
the so-called $S_{n,n}$-conjecture [7]. In this work we follow the notations
and preliminaries of the work [12], however, some of them will be stated here
for convenience of the reader.

Let $G=(V(G),E(G))$ be a simple graph (without loops or multiple edges) where
$V(G)={\\{v_{1},v_{2},\ldots,v_{n}}\\}$ is its vertex set and
$E(G)={\\{e_{1},e_{2},\ldots,e_{r}}\\}$ its edge set. The entries of its
Laplacian matrix are defined as follows

$l_{ij}=\begin{cases}&d_{i},\quad\text{if}\quad\ \ i=j,\\\ &-1,\ \ \
\text{if}\quad\ \ i\neq j\ \text{and}\ v_{i}\sim v_{j},\\\ &\ 0,\ \
\quad\text{otherwise},\end{cases}$

where $v_{i}\sim v_{j}$ means that the vertices $v_{i}$ and $v_{j}$ are
adjacent.

The Laplacian matrix $L(G)$ is positive semidefinite and singular, see e.g.
[27]. A graph $G$ whose Laplacian matrix has integer eigenvalues is called
Laplacian integral. As we noticed in [12], there are many famous families of
Laplacian integral graphs and we refer the reader to the works [1, 5, 7, 10,
13, 15, 16, 17, 18, 23, 24, 25] and references therein.

One of the most interesting families of Laplacian integral graphs considered
by S. Fallat et al. [7] is defined as follows: The set

$S_{i,n}=\\{0,1,2,\ldots,n-1,n\\}\setminus\\{i\\},\;\;i\leqslant n,$

is called Laplacian realizable if there exists a simple connected graph $G$
whose Laplacian spectrum is $S_{i,n}$. We also say that $G$ realizes
$S_{i,n}$. In [7] the authors established realizability of sets and completely
described the graphs realizing $S_{i,n}$. In addition, it is also conjectured
in [7] that the set $S_{n,n}$ is not Laplacian realizable for any $n\geqslant
2$. . This problem is now known as the $S_{n,n}$-conjecture and states that
$S_{n,n}$ is not Laplacian realizable for every $n\geqslant 2$. This
conjecture was proved for $n\leqslant 11$, for prime $n$, and for $n\equiv
2,3\mod 4$ in [7]. Later, Goldberger and Neumann [9] showed that the
conjecture is true for $n\geqslant 6,649,688,933$. The authors of the present
work established [11] that if a graph is the Cartesian product of two other
graphs, then it does not realize $S_{n,n}$.

As a way of investigating the class of Laplacian integral graphs, the authors
of the present work extended this concept further and studied a certain class
of Laplacian integral graphs introduced in [12] and is defined as follows.

######  Definition 1.1.

A graph $G$ is said to realize the set

(1.1)
$S_{\\{i,j\\}_{n}^{m}}=\\{0,1,2,\ldots,m-1,m,m,m+1,\ldots,n-1,n\\}\setminus\\{i,j\\}$

for some $i$ and $j$, $i<j\leqslant n$, if its Laplacian spectrum is the set
$S_{\\{i,j\\}_{n}^{m}}$. In this case, the set $S_{\\{i,j\\}_{n}^{m}}$ is
called Laplacian realizable. So the set $S_{\\{i,j\\}_{n}^{m}}$ does not
contain the numbers $i$ and $j$, while some number $m$ (and only this number)
is doubled.

The present work is the second part of our research on the set
$S_{\\{i,j\\}_{n}^{m}}$. In the first part [12], we considered graphs
realizing the sets $S_{\\{i,j\\}_{n}^{m}}$ for $m=n-1$ and $m=n$, and
completely described them. Moreover, we conjectured that the graphs realizing
sets $S_{\\{i,n\\}_{n}^{m}}$ (that is, without $n$) may not exist for large
$n$. In particular, we believe that for $n\geqslant 9$ the sets
$S_{\\{i,n\\}_{n}^{m}}$ are not Laplacian realizable. In this paper, we
continue our study and consider the cases $m=1$ and $m=2$.

First, we note that graphs realizing sets $S_{\\{i,j\\}_{n}^{1}}$ and
$S_{\\{i,j\\}_{n}^{2}}$ exist for small $n$. The Laplacian spectra of all the
graphs of order up to $5$ are listed in [3, p. 286–289]. From that list it
follows that for $n\leqslant 5$ the only Laplacian realizable
$S_{\\{i,j\\}_{n}^{1}}$ sets are $S_{\\{2,3\\}_{4}^{1}}$ and
$S_{\\{2,4\\}_{5}^{1}}$. In Figure 1, the graph $G_{1}$ is the star graph
$K_{1,3}$ on $4$ vertices realizing $S_{\\{2,3\\}_{4}^{1}}$ (see Table
LABEL:Table.1 in Appendix). The graph $G_{2}$ realizing the set
$S_{\\{2,4\\}_{5}^{1}}$ is of the form $\left(K_{2}\cup 2K_{1}\right)\vee
K_{1}$ (see Table LABEL:Table.1). Similarly, for $n\leqslant 5$, the only
Laplacian realizable $S_{\\{i,j\\}_{n}^{2}}$ sets are $S_{\\{1,3\\}_{4}^{2}}$
and $S_{\\{1,4\\}_{5}^{2}}$. In Figure 2, the graphs $G_{3}$ and $G_{4}$ are
the complete bipartite graphs $K_{2,2}$ (or the cycle $C_{4}$) and $K_{2,3}$
on $4$ and $5$ vertices respectively, realizing $S_{\\{1,3\\}_{4}^{2}}$ and
$S_{\\{1,4\\}_{5}^{2}}$ respectively (see Table LABEL:Table.2).

${G_{1}}$${G_{2}}$ Figure 1. Graphs $G_{1}$ and $G_{2}$ realizing
$S_{\\{2,3\\}_{4}^{1}}$ and $S_{\\{2,4\\}_{5}^{1}}$, respectively.
${G_{3}}$${G_{4}}$ Figure 2. Graphs $G_{3}$ and $G_{4}$ realizing
$S_{\\{1,3\\}_{4}^{2}}$ and $S_{\\{1,4\\}_{5}^{2}}$, respectively.

Considering the case $m=1$, we show that the set $S_{\\{i,j\\}_{n}^{1}}$ is
Laplacian realizable only if $j=n-1$, that is, only $S_{\\{i,n-1\\}_{n}^{1}}$
is Laplacian realizable for certain $i$, Theorem 2.8. Further, we list all
such $i$ for fixed $n$ and $j=n-1$, i.e., we find all the Laplacian realizable
sets of kind $S_{\\{i,n-1\\}_{n}^{1}}$, Theorem 3.2. We also present an
algorithm for constructing graphs realizing the sets
$S_{\\{i,n-1\\}_{n}^{1}}$, Theorem 3.3. For the case $m=2$, we show that if
$i>1$, then $j>n-3$, Theorem 4.1, and list all such $i$ for given $j$
considering $j=n-2$ and $n-1$ separately, Theorems 4.3 and 4.7. Theorems 4.4
and 4.8 describe the structure of graphs realizing the sets
$S_{\\{i,j\\}_{n}^{2}}$ for $j=n-2,n-1$. If $i=1$ then for all admissible $j$,
the set $S_{\\{1,j\\}_{n}^{2}}$ is Laplacian realizable only if $G=K_{1}\vee
F$, where the graph $F$ realizes $S_{\\{j-1,n-1\\}_{n-1}^{1}}$, Theorem 4.9.
However, for such case we believe that it may not exists for large $n$,
$n\geqslant 6$. Tables 1 and 2 in Appendix A illustrate the cases $m=1$ and
$m=2$.

As a result of our investigation on the set $S_{\\{i,j\\}_{n}^{m}}$, we
conclude that the values of $m$ are closely related to one another. For
instance, if $G$ realizes $S_{\\{i,j\\}_{n}^{n}}$ ($m=n$) then one can obtain
graphs realizing the sets $S_{\\{i,j\\}_{n}^{n-1}}$ ($m=n-1$) by using certain
graph operations such as union, join and complement. Similarly, the case
$m=n-2$ can be obtained from the case $m=n-1$ and so on. On the other hand, if
$G$ realizes $S_{\\{i,j\\}_{n}^{m}}$ for $m=n$, then using certain graph
operations, we obtain the graph realizes $S_{\\{i,j\\}_{n}^{m}}$ for $m=1$.
Similarly, $m=2$ can be obtained from the case $m=n-1$. So, either of the
cases can be obtained by using graph operations. However, it is not clear
whether the operations on graphs cover all the sets realizing
$S_{\\{i,j\\}_{n}^{m}}$ for particular value of $m$.

The paper is organized as follows. In Section 2, we introduce some basic
definitions and review some note worthy results from the literature that we
use in this work. We also prove some auxiliary theorems. In Section 3, a
complete characterization of all the graphs with double Laplacian eigenvalue
$m=1$ is given. The graphs with double Laplacian eigenvalue $m=2$ are
discussed in Section 4. We summarize this work in Section 5. Finally, in
Appendix A, we list all the Laplacian realizable sets $S_{\\{i,j\\}_{n}^{1}}$
and $S_{\\{i,j\\}_{n}^{2}}$ for $n=4,5,6,7,8$. The associated graphs realizing
those sets are presented.

##  2\. Preliminaries

An isolated vertex is a vertex of degree zero denoted by $K_{1}$, while a
pendant vertex is a vertex of degree one. The complement of a simple
undirected graph $G$ denoted by $\overline{G}$ is a simple graph on the same
set of vertices as $G$ in which two vertices are adjacent if and only if they
are not adjacent in $G$. Given two disjoint graphs $G_{1}$ and $G_{2}$, the
union of these graphs, $G_{1}\cup G_{2}$, is the graph formed from the unions
of the edges and vertices of the graphs $G_{1}$ and $G_{2}$. The join of the
graphs $G_{1}$ and $G_{2}$, $G_{1}\vee G_{2}$, is the graph formed from
$G_{1}\cup G_{2}$ by adding all possible edges between vertices in $G_{1}$ and
vertices in $G_{2}$, that is, $G_{1}\vee
G_{2}=\overline{(\overline{G_{1}}\cup\overline{G_{2}})}$.

We denote by $0=\mu_{1}\leqslant\mu_{2}\leqslant\ldots\leqslant\mu_{n}$ the
Laplacian eigenvalues of a graph $G$. It is easy to see from the form of the
Laplacian matrix that the Laplacian spectrum of the union of two graphs is the
union of their Laplacian spectra. The largest eigenvalue of the Laplacian
matrix, is denoted by $\rho(G)$. The second smallest eigenvalue $\mu_{2}$ of
$L(G)$ is usually known as the algebraic connectivity of $G$ denoted by
$a_{G}$. The vertex connectivity of a connected graph $G$ is the minimum
number of vertices whose removal disconnect $G$.

The following facts provide information on the Laplacian largest eigenvalue
and the Laplacian spectrum of the complement of graph.

######  Theorem 2.1 ([22]).

Let $G$ be a simple graph on $n$ vertices. Then $\rho(G)\leqslant n$.

######  Theorem 2.2 ([3, 22]).

Let $G$ be a graph with $n$ vertices with Laplacian eigenvalues

$0=\mu_{1}\leqslant\mu_{2}\leqslant\mu_{3}\leqslant\cdots\leqslant\mu_{n-1}\leqslant\mu_{n}$

Then the Laplacian eigenvalues of the complement of $G$ are the following

$0\leqslant n-\mu_{n}\leqslant n-\mu_{n-1}\leqslant\cdots\leqslant
n-\mu_{3}\leqslant n-\mu_{2}.$

The Laplacian spectra of the disjoint union and join of graphs are stated in
the following theorems.

######  Theorem 2.3 ([3]).

If $G$ is the disjoint union of graphs $G_{1},G_{2},\dots,G_{k}$, then it’s
Laplacian characteristic polynomial is

$\chi(G,\mu)=\prod_{k=1}^{n}\chi({G_{k}},\mu)$

######  Theorem 2.4 (Kelman’s).

Let $G$ and $H$ be two graphs of order $n$ and $m$, respectively. Suppose that
the Laplacian eigenvalues of $G$ and $H$ are of the form

$0=\mu_{1}\leqslant\mu_{2}\leqslant\mu_{3}\ldots\leqslant\mu_{n-1}\leqslant\mu_{n}\quad\;\;\mathrm{and}$

$0=\lambda_{1}\leqslant\lambda_{2}\leqslant\lambda_{3}\ldots\leqslant\lambda_{m-1}\leqslant\lambda_{m}\quad\;\;\mathrm{respectively}$

then the Laplacian spectrum of $G\vee H$ is of the form

(2.1)
$\\{0,m+\mu_{2},m+\mu_{3},\ldots,m+\mu_{n-1},m+\mu_{n},n+\lambda_{2},n+\lambda_{3},\ldots,n+\lambda_{m-1},n+\lambda_{m},n+m\\}.$

We cite the above theorem in the form given in [20]. Note that the eigenvalues
in (2.1) are not in increasing order, generally speaking.

The following theorem provides a necessary and sufficient condition for a
graph to have $n$ as one of its eigenvalue.

######  Theorem 2.5 ([26]).

Let $G$ be a connected graph of order $n$. Then $n$ is a Laplacian eigenvalue
of $G$ if and only if $G$ is the join of two graphs.

If the order $n$ is a double Laplacian eigenvalue, then the following theorem
holds.

######  Theorem 2.6 ([12]).

Let $G$ be a connected graph of order $n$, and let $n$ be the Laplacian
eigenvalue of $G$ of multiplicity $2$. Then $G=F\vee H$ where $F$ is a join of
two graphs, while $H$ is not a join. Moreover, the eigenvalue $1$ is not in
the Laplacian spectrum of $G$.

The next proposition provides a necessary and sufficient condition for a graph
to have $1$ as one of its Laplacian eigenvalues.

######  Proposition 2.7 ([11]).

Let a graph $G$ be a join. The number $1$ is a Laplacian eigenvalue of $G$ if
and only if $G=F\vee K_{1}$ where $F$ is a disconnected graph of order at
least $2$.

To complement to the previous result, we establish the following.

######  Theorem 2.8.

Let $G$ be a connected graph of order $n$ that is a join. Let the number $1$
be the Laplacian eigenvalue of $G$ of multiplicity $2$. Then
$G=\left(H_{1}\cup 2K_{1}\right)\vee K_{1}$ where $H_{1}$ is a connected graph
of order $n-3$. Moreover, the number $n-1$ is not in the Laplacian spectrum of
$G$.

######  _Proof_.

Let $G$ be a join that has a Laplacian eigenvalue $1$ of multiplicity $2$.
According to Theorem 2.5, $G=F\vee H$ where the graph $F$ is of order $p$
while the graph $H$ is of order $n-p$ for some $1\leqslant p\leqslant n-1$.

Let us denote the Laplacian spectra of the graphs $F$ and $H$, respectively,
as follows

$0=\mu_{1}\leqslant\mu_{2}\leqslant\mu_{3}\ldots\leqslant\mu_{p-1}\leqslant\mu_{p}\quad\text{and}\quad
0=\lambda_{1}\leqslant\lambda_{2}\leqslant\lambda_{3}\ldots\leqslant\lambda_{n-p-1}\leqslant\lambda_{n-p}.$

Then by Theorem 2.4, the Laplacian spectrum of $G$ has the form

(2.2)
$\\{0,(n-p)+\mu_{2},\ldots,(n-p)+\mu_{p},p+\lambda_{2},\ldots,p+\lambda_{n-p},n\\}.$

We remind the reader that the eigenvalues are not in the increasing order
here.

Since $G$ has exactly one multiple eigenvalue $1$ by assumption, (2.2)
provides only two possible situations.

1) If $n-p+\mu_{2}=p+\lambda_{2}=1$, then $n-p=p=1$, so both graphs $F$ and
$H$ are single isolated vertices. Thus, $G=K_{1}\vee K_{1}$ and the Laplacian
spectrum of $G$ is equal to $\\{0,2\\}$, a contradiction.

2) Let $n-p+\mu_{2}=n-p+\mu_{3}=1$ or $p+\lambda_{2}=p+\lambda_{3}=1$. Without
loss of generality, we can suppose that $n-p+\mu_{2}=n-p+\mu_{3}=1$, so
$\mu_{2}=\mu_{3}=0$ and $n-p=1$. As well, the inequality $n-p+\mu_{4}>1$ gives
us $\mu_{4}>0$. Consequently, the graph $F$ is a disconnected graph of the
form $F=H_{1}\cup 2K_{1}$, whereas the graph $H$ is an isolated vertex
$K_{1}$. Thus, $G=(H_{1}\cup 2K_{1})\vee K_{1}$ where $H_{1}$ is a connected
graph of order $n-3$.

Now to prove that $n-1$ is not in the Laplacian spectrum of $G$, it is enough
to show that $n-p+\mu_{p}\neq n-1$. Let us suppose that $n-p+\mu_{p}=n-1$.
Then $\mu_{p}=n-2$, and so the Laplacian spectrum of the graph $F$ of order
$n-1$ has the form $\sigma_{L}(F)=\\{0,0,0,\mu_{4},\ldots,n-3,n-2\\}$.
According to Theorem 2.2, the Laplacian spectrum of $\overline{F}$ is
$\sigma_{L}(\overline{F})=\\{0,1,2,\ldots,n-1,n-1\\}$. Thus, the Laplacian
spectrum of the graph $\overline{F}$ of order $n-1$ contains the eigenvalue
$1$ and the double eigenvalue $n-1$. This contradicts Theorem 2.6. Therefore,
the eigenvalue $n-1$ is not in the Laplacian spectrum of $G$. ∎

Now, we remind the reader some results on the sets $S_{i,n}$ established in
[7].

######  Theorem 2.9.

Suppose $n\geqslant 2$.

  * (i)

If $n\equiv 0\mod 4$, then for each $i=1,2,3,\dots,\dfrac{n-2}{2}$, $S_{2i,n}$
is Laplacian realizable;

  * (ii)

If $n\equiv 1\mod 4$, then for each $i=1,2,3,\dots,\dfrac{n-1}{2}$,
$S_{2i-1,n}$ is Laplacian realizable;

  * (iii)

If $n\equiv 2\mod 4$, then for each $i=1,2,3,\dots,\dfrac{n}{2}$, $S_{2i-1,n}$
is Laplacian realizable;

  * (iv)

If $n\equiv 3\mod 4$, then for $i=1,2,\dots,\dfrac{n-1}{2}$, $S_{2i,n}$ is
Laplacian realizable.

######  Proposition 2.10.

Suppose that $n\geqslant 6$ and that $G$ is a graph on $n$ vertices. Then $G$
realizes $S_{1,n}$ if and only if $G$ is formed in one of the following two
ways:

  * (i)

$G=(K_{1}\cup K_{1})\vee(K_{1}\cup G_{1})$, where $G_{1}$ is a graph on $n-3$
vertices that realizes $S_{n-4,n-3};$

  * (ii)

$G=K_{1}\vee H$, where $H$ is a graph on $n-1$ vertices that realizes
$S_{n-1,n-1}$.

In the sequel, we use also the following results established in [12].

######  Theorem 2.11 ([12]).

If $S_{\\{i,j\\}_{n}^{n-1}}$ is Laplacian realizable then the number $i$ is
either $1$ or $2$.

######  Theorem 2.12 ([12]).

Suppose that $n\geqslant 3$ and $G$ is a graph of order $n$ realizing
$S_{\\{i,j\\}_{n}^{m}}$ for $i<j$. Then

  * (i)

for $n\equiv 0\;or\;3\mod 4$, the numbers $(i+j)$ and $m$ are of the same
parities;

  * (ii)

for $n\equiv 1\;or\;2\mod 4$, the numbers $(i+j)$ and $m$ are of opposite
parities.

######  Proposition 2.13 ([12]).

The graph $G$ realizes $S_{\\{1,2\\}_{n}^{n}}$ if and only if $G$ is formed in
one of the following two ways:

  * (i)

$G=P_{3}\vee\left(K_{1}\cup H\right)$, where $H$ realizes $S_{n-5,n-4}$ and
$P_{3}$ is the path graph on $3$ vertices;

  * (ii)

$G=K_{2}\vee H$, where $H$ realizes $S_{n-2,n-2}$.

######  Theorem 2.14 ([12]).

Let $G$ be a graph of order $n$, $n\geqslant 5$.

  * (a)

The graph $G$ realizes $S_{\\{1,2\\}_{n}^{n}}$ if and only if $G$ is formed in
one of the following two ways:

    * (i)

$G=P_{3}\vee\left(K_{1}\cup H\right)$, where $H$ realizes $S_{n-5,n-4}$ and
$P_{3}$ is the path graph on $3$ vertices;

    * (ii)

$G=K_{2}\vee H$, where $H$ realizes $S_{n-2,n-2}$.

  * (b)

If $3\leqslant j\leqslant n-2$, then $G$ realizes $S_{\\{1,j\\}_{n}^{n}}$ if
and only if $G=K_{2}\vee\left(K_{1}\cup H\right)$, where the graph $H$
realizes $S_{j-2,n-3}$.

  * (c)

The graph $G$ realizes $S_{\\{1,n-1\\}_{n}^{n}}$ if and only if $G$ is formed
in one of the following two ways:

    * (i)

$G=K_{2}\vee(K_{2}\cup H)$, where $H$ realizes $S_{2,n-4}$;

    * (ii)

$G=K_{2}\vee(K_{1}\cup H)$, where $H$ realizes $S_{n-3,n-3}$.

######  Theorem 2.15 ([12]).

Let $G$ be a simple connected graph of order $n$, $n\geqslant 6$.

  * (i)

For $n\equiv 0$ or $1\mod 4$, the set $S_{\\{1,j\\}_{n}^{n-1}}$ is Laplacian
realizable if and only if $j=2$.

  * (ii)

For $n\equiv 2$ or $3\mod 4$, the set $S_{\\{1,j\\}_{n}^{n-1}}$ is Laplacian
realizable if and only if $j=3$.

######  Theorem 2.16 ([12]).

Let $G$ be a graph of order $n$, $n\geqslant 6$.

  * (a)

The graph $G$ realizes $S_{\\{1,2\\}_{n}^{n-1}}$ if and only if $n\equiv 0$ or
$1\mod 4$, and $G=(K_{1}\cup K_{2})\vee(K_{1}\cup H)$, where $H$ realizes
$S_{n-6,n-4}$;

  * (b)

The graph $G$ realizes $S_{\\{1,3\\}_{n}^{n-1}}$ if and only if $n\equiv 2$ or
$3\mod 4$, and $G$ is formed in one of the following two ways:

    * (i)

$G=\left(K_{1}\cup K_{1}\right)\vee\left(K_{1}\cup H\right)$, where the graph
$H$ realizes $S_{\\{1,n-4\\}_{n-3}^{n-3}}$;

    * (ii)

$G=K_{1}\vee F$, where the graph $F$ realizes $S_{\\{2,n-1\\}_{n-1}^{n-2}}$.

##  3\. Graphs realizing the sets $S_{\\{i,j\\}_{n}^{1}}$

In this section, we describe the graphs realizing the sets
$S_{\\{i,j\\}_{n}^{1}}$, and present an algorithm for constructing graphs
realizing $S_{\\{i,j\\}_{n}^{1}}$. As we mentioned in Introduction, in [3, p.
286–289] the authors listed the Laplacian spectra of all the graphs of order
up to $5$. Thus, it follows that for $n\leqslant 5$ the only Laplacian
realizable $S_{\\{i,j\\}_{n}^{1}}$ sets are $S_{\\{2,3\\}_{4}^{1}}$ and
$S_{\\{2,4\\}_{5}^{1}}$, see Table LABEL:Table.1 in Appendix A. So in what
follows, we consider $n\geqslant 6$.

First we present the following auxiliary fact.

######  Lemma 3.1.

If $S_{i,n}$ is Laplacian realizable, then so is
$S_{\\{i+1,n+2\\}_{n+3}^{1}}$.

Indeed, if $G$ is a connected graph of order $n$ realizing $S_{i,n}$, then the
graph $\left(G\cup 2K_{1}\right)\vee K_{1}$ realizes
$S_{\\{i+1,n+2\\}_{n+3}^{1}}$.

In the next theorem, we describe all the Laplacian realizable sets
$S_{\\{i,j\\}_{n}^{1}}$.

######  Theorem 3.2.

Suppose $n\geqslant 6$. The only Laplacian realizable sets
$S_{\\{i,j\\}_{n}^{1}}$, $i<j<n$, are the following ones.

  * (i)

If $n\equiv 0\mod 4$, then for each $k=1,2,\ldots,\dfrac{n-2}{2}$,
$S_{\\{2k,n-1\\}_{n}^{1}}$ is Laplacian realizable;

  * (ii)

If $n\equiv 1\mod 4$, then for each $k=1,2,\ldots,\dfrac{n-3}{2}$,
$S_{\\{2k,n-1\\}_{n}^{1}}$ is Laplacian realizable;

  * (iii)

If $n\equiv 2\mod 4$, then for each $k=1,2,\ldots,\dfrac{n-4}{2}$,
$S_{\\{2k+1,n-1\\}_{n}^{1}}$ is Laplacian realizable;

  * (iv)

If $n\equiv 3\mod 4$, then for each $k=1,2,\ldots,\dfrac{n-3}{2}$,
$S_{\\{2k+1,n-1\\}_{n}^{1}}$ is Laplacian realizable.

######  _Proof_.

According to Theorem 2.8, if $S_{\\{i,j\\}_{n}^{1}}$ is Laplacian realizable,
then the eigenvalue $n-1$ is not in the Laplacian spectrum of $G$, so $j=n-1$.
Consequently, the sets $S_{\\{i,j\\}_{n}^{1}}$ are not Laplacian realizable if
$j<n-1$.

  * (i)

If $n\equiv 0\mod 4$, then $n-3\equiv 1\mod 4$, so for each
$k=1,2,\ldots,\dfrac{n-4}{2}$, $S_{2k-1,n-3}$ is Laplacian realizable by
Theorem 2.9 (ii). According to Lemma 3.1, $S_{\\{2k,n-1\\}_{n}^{1}}$ is
Laplacian realizable for any $k=1,2,\ldots,\dfrac{n-4}{2}$. Moreover, since
$n$ is even and $m=1$, $S_{\\{2k+1,n-1\\}_{n}^{1}}$ is not Laplacian
realizable by Theorem 2.12 (i).

Let us now deal with the set $S_{\\{n-2,n-1\\}_{n}^{1}}$. The set $S_{2,n-4}$
is Laplacian realizable by Theorem 2.9 (i). Suppose that a graph $F_{1}$
realizes $S_{2,n-4}$. If $P_{3}$ is the path graph on 3 vertices, then
$\sigma_{L}(\overline{P_{3}})=\\{0,0,2\\}$, and
$\sigma_{L}(\overline{P_{3}}\cup F_{1})=\\{0,0,0,1,2,\ldots,n-5,n-4\\}$.
According to Theorem 2.4, the graph $K_{1}\vee(\overline{P_{3}}\cup F_{1})$
realizes $S_{\\{n-2,n-1\\}_{n}^{1}}$.

  * (ii)

If $n\equiv 1\mod 4$, then $n-3\equiv 2\mod 4$. Therefore, by Theorem 2.9
(iii), the set $S_{2k-1,n-3}$ is Laplacian realizable for
$k=1,2,\ldots,\dfrac{n-3}{2}$. By Lemma 3.1, $S_{\\{2k,n-1\\}_{n}^{1}}$ is
Laplacian realizable for any $k=~{}1,2,\ldots,\dfrac{n-3}{2}$. As $n$ is odd
and $m=1$, therefore, by Theorem 2.12 (ii), $S_{\\{2k+1,n-1\\}_{n}^{1}}$ is
not Laplacian realizable.

The case (iii) can be proved analogously.

  * (iv)

If $n\equiv 3\mod 4$, then $n-3\equiv 0\mod 4$. Thus, for
$k=1,2,\ldots,\dfrac{n-5}{2}$, the sets $S_{2k,n-3}$ is Laplacian realizable
by Theorem 2.9 (i). Now Lemma 3.1 implies that $S_{\\{2k+1,n-1\\}_{n}^{1}}$ is
Laplacian realizable for any $k=1,2,\ldots,\dfrac{n-5}{2}$, while Theorem 2.12
(i) gives us that $S_{\\{2k,n-1\\}_{n}^{1}}$ is not Laplacian realizable,
since $n$ is even and $m=1$.

Next, consider the set $S_{\\{n-2,n-1\\}_{n}^{1}}$. By Theorem 2.9 (i), the
set $S_{2,n-4}$ is Laplacian realizable. Let a graph, say, $F_{1}$ realize
$S_{2,n-4}$. Then for the path graph $P_{3}$, the graph
$K_{1}\vee(\overline{P_{3}}\cup F_{1})$ realizes $S_{\\{n-2,n-1\\}_{n}^{1}}$
by Theorem 2.4. Therefore, $S_{\\{n-2,n-1\\}_{n}^{1}}$ is Laplacian
realizable.

∎

In the following theorem, we discuss the structure of graphs realizing
$S_{\\{i,n-1\\}_{n}^{1}}$ for various possible values of $i$. We remind the
reader that the sets $S_{\\{i,j\\}_{n}^{1}}$ for $j<n-1$ are not Laplacian
realizable as we found out above.

######  Theorem 3.3.

Let $G$ be a graph of order $n$, $n\geqslant 6$.

  * (a)

If $2\leqslant i\leqslant n-3$, then $G$ realizes $S_{\\{i,n-1\\}_{n}^{1}}$ if
and only if $G=K_{1}\vee(2K_{1}\cup(K_{1}\vee\overline{H}))$, where the graph
$H$ realizes the set $S_{n-i-2,n-4}$.

  * (b)

The graph $G$ realizes $S_{\\{n-2,n-1\\}_{n}^{1}}$ if and only if $G$ is
formed in one of the following two ways:

    * (i)

$G=K_{1}\vee(\overline{P_{3}}\cup(K_{1}\vee\overline{H}))$, where the graph
$H$ of order $n-5$ realizes $S_{n-6,n-5}$;

    * (ii)

$G=K_{1}\vee(2K_{1}\cup\overline{H})$, where the graph $H$ realizes
$S_{n-3,n-3}$.

######  _Proof_.

(a) Suppose that $G$ realizes $S_{\\{i,n-1\\}_{n}^{1}}$ for $2\leqslant
i\leqslant n-3$. By Theorem 2.2, one has $\sigma_{L}(\overline{G})=\\{0\\}\cup
S_{\\{1,n-i\\}_{n-1}^{n-1}}$. Therefore, the complement of the graph $G$ has
the form $\overline{G}=K_{1}\cup\overline{F}$, where $\overline{F}$ is
connected and $\sigma_{L}(\overline{F})=S_{\\{1,n-i\\}_{n-1}^{n-1}}$.
According to Theorem 2.14 (b), $\overline{F}$ realizes
$S_{\\{1,n-i\\}_{n-1}^{n-1}}$ if and only if
$\overline{F}=K_{2}\vee\left(K_{1}\cup H\right)$, where the graph $H$ realizes
$S_{n-i-2,n-4}$. Consequently, $F=2K_{1}\cup(K_{1}\vee\overline{H})$, so
$G=K_{1}\vee(2K_{1}\cup(K_{1}\vee\overline{H}))$.

Conversely, if $G=K_{1}\vee(2K_{1}\cup(K_{1}\vee\overline{H}))$, where the
graph $H$ realizes the set $S_{n-i-2,n-4}$, then from Theorems 2.3 and 2.4, it
follows that $G$ realizes $S_{\\{i,n-1\\}_{n}^{1}}$.

(b) Let $G$ be a graph realizing $S_{\\{n-2,n-1\\}_{n}^{1}}$. Then from
Theorem 2.2, we obtain $\sigma_{L}{(\overline{G})}=\\{0\\}\cup
S_{\\{1,2\\}_{n-1}^{n-1}}$. So the complement of the graph $G$ can be
represented as follows $\overline{G}=K_{1}\cup\overline{F}$, where
$\overline{F}$ is connected and
$\sigma_{L}(\overline{F})=S_{\\{1,2\\}_{n-1}^{n-1}}$. According to Theorem
2.14 (a), the graph $\overline{F}$ must be in one of the following form:

  * (i)

$\overline{F}=P_{3}\vee\left(K_{1}\cup H\right)$, where $H$ realizes
$S_{n-6,n-5}$ and $P_{3}$ is the path graph on $3$ vertices;

  * (ii)

$\overline{F}=K_{2}\vee H$, where $H$ realizes $S_{n-3,n-3}$.

Thus, from (i) one gets
${F}=\overline{P_{3}}\cup\left(K_{1}\vee\overline{H}\right)$. According to
Theorem 2.2, one has $\sigma_{L}(\overline{H})=\\{0\\}\cup S_{1,n-6}$. So
$\overline{H}$ can be represented as follows $\overline{H}=K_{1}\cup H_{1}$,
where $H_{1}$ realizes $S_{1,n-6}$ (for the construction of $H_{1}$, see
Proposition 2.10). Thus,
$G=K_{1}\vee(\overline{P_{3}}\cup(K_{1}\vee\overline{H}))$, where the graph
$H$ of order $n-5$ realizes $S_{n-6,n-5}$.

Also from (ii), we have $\overline{F}={K_{2}\vee H}$. Therefore,
$F=2K_{1}\cup\overline{H}$, and the graph $H$ is a connected graph realizing
$S_{n-3,n-3}$. Thus, $G=K_{1}\vee(2K_{1}\cup\overline{H})$, where $H$ realizes
$S_{n-3,n-3}$.

Conversely, if $G=K_{1}\vee(\overline{P_{3}}\cup(K_{1}\vee\overline{H}))$,
where the graph $H$ of order $n-5$ realizes $S_{n-6,n-5}$. Then from Theorems
2.3 and 2.4 it follows that $G$ realizes $S_{\\{n-2,n-1\\}_{n}^{1}}$.
Similarly, if $G=K_{1}\vee(2K_{1}\cup\overline{H})$, where $H$ realizes
$S_{n-3,n-3}$, then again by Theorems 2.3 and 2.4, the graph $G$ realizes
$S_{\\{n-2,n-1\\}_{n}^{1}}$. ∎

######  Remark 3.4.

In the above theorem, the structure of the graph $G$ shows that there exist at
least two pendant vertices in $G$. As well, Theorems 3.2 and 3.3 completely
resolve the existence of graphs realizing the spectrum
$S_{\\{i,j\\}_{n}^{1}}$, where $2\leqslant i<j<n$. Furthermore, it is easily
deduced from Theorem 3.3 that if the sets $S_{n,n}$ were not realizable for
any $n$, then there is a unique graph, which realizes $S_{\\{i,j\\}_{n}^{1}}$,
for $2\leqslant i<j<n$.

For the case $j=n$, we conjectured that the set $S_{\\{i,n\\}_{n}^{m}}$,
$n\geqslant 9$, does not exist [12]. However, unless otherwise is proved, we
must include this case in our consideration.

######  Proposition 3.5.

Let $G$ realize $S_{\\{i,n\\}_{n}^{1}}$. Then the following holds:

  * (a)

$n\geqslant 9$;

  * (b)

$n$ is not a prime number;

  * (c)

$2\leqslant\min\limits_{1\leqslant i\leqslant
n}~{}d_{i}\leqslant\max\limits_{1\leqslant i\leqslant n}d_{i}\leqslant n-3$,
where $d_{i}$ is the degree of vertex $i$.

######  _Proof_.

Let $G$ realize $S_{\\{i,n\\}_{n}^{1}}$. Then Properties (a) and (b) follow
from [12, Proposition 5.2].

If we suppose, on the contrary, that $G$ has a pendant vertex, then the vertex
connectivity of $G$ equals $1$. At the same time, its algebraic connectivity
is also $1$. So, according to [19, Theorem 2.1] if the algebraic and vertex
connectivity are equal, then $G$ must be a join, a contradiction. ∎

Property (c) in the above proposition coincides with the one of the
$S_{n,n}$-conjecture proposed in [7, Observation 3.5].

The Cartesian product of the graphs $G_{1}$ and $G_{2}$ is the graph
$G_{1}\times G_{2}$ whose vertex set is the Cartesian product $V(G_{1})\times
V(G_{2})$, and for $v_{1},v_{2}\in V(G_{1})$ and $u_{1},u_{2}\in V(G_{2})$,
the vertices $(v_{1},u_{1})$ and $(v_{2},u_{2})$ are adjacent in $G_{1}\times
G_{2}$ if and only if either

  * $\bullet$

$v_{1}=v_{2}$ and $\\{u_{1},u_{2}\\}\in E(G_{1})$;

  * $\bullet$

${\\{v_{1},v_{2}\\}}\in E(G_{2})$ and $u_{1}$=$u_{2}$.

The authors of the present work established [12] that if $G=G_{1}\times G_{2}$
(i.e., $G$ is a Cartesian product of two graphs) then it does not realize the
set $S_{\\{i,n\\}_{n}^{m}}$ for $n\geqslant 9$ and any $m\neq i,n$. According
to Proposition 3.5, the set $S_{\\{i,n\\}_{n}^{1}}$ is not Laplacian
realizable if $n$ is a prime number, and so the Cartesian product does not
realizes the set $S_{\\{i,n\\}_{n}^{1}}$ for a prime number $n$. All these
facts motivated us to state the following Conjecture.

######  Conjecture 3.6.

For $n\geqslant 3$, the set $S_{\\{i,n\\}_{n}^{1}}$ is not Laplacian
realizable.

##  4\. Graphs realizing the sets $S_{\\{i,j\\}_{n}^{2}}$

This section establishes the existence of graphs realizing the sets
$S_{\\{i,j\\}_{n}^{2}}$. As we already mentioned in Section 1, for $n\leqslant
5$, the only Laplacian realizable sets of type $S_{\\{i,j\\}_{n}^{2}}$ are
$S_{\\{1,3\\}_{4}^{2}}$ and $S_{\\{1,4\\}_{5}^{2}}$, see Table LABEL:Table.2
in Appendix A. So throughout this section we consider $n\geqslant 6$. In
Sections 4.1–4.2 we study the case $1<i<j<n$, while Section 4.3 is devoted to
the sets $S_{\\{1,j\\}_{n}^{2}}$ ($i=1$) and $S_{\\{i,n\\}_{n}^{2}}$ ($j=n$).
We believe that these sets are not Laplacian realizable for large $n$. To
proceed with the main results of this section, we first establish a relation
between the numbers $i$ and $j$ to realize $S_{\\{i,j\\}_{n}^{2}}$ when $i>1$
as follows:

######  Theorem 4.1.

Let $G$ realize $S_{\\{i,j\\}_{n}^{2}}$. If $i>1$, then $j>n-3$.

######  _Proof_.

Suppose on the contrary that $S_{\\{i,j\\}_{n}^{2}}$ is Laplacian realizable
for some $j\leqslant n-3$, and let $G$ be a graph realizing this set. Clearly,
the numbers $n-2$, $n-1$ and $n$ belong to $\sigma_{L}(G)$. According to
Theorem 2.2,

(4.1)
$\sigma_{L}(\overline{G})=\\{0,0,1,2,\ldots,n-j-1,n-j+1,n-i-1,n-i+1,\ldots,n-2,n-2,n-1\\}.$

By Theorem 2.1 one of the components of $\overline{G}$, say,
$\overline{G_{2}}$ has $n-1$ vertices, so $G_{1}=K_{1}$. Now from (4.1) one
has

$\sigma_{L}(\overline{G_{2}})=\\{0,1,2,\ldots,n-j-1,n-j+1,n-i-1,n-i+1,\ldots,n-2,n-2,n-1\\}.$

This contradicts Theorem 2.11. Therefore, for $i>1$, the set
$S_{\\{i,j\\}_{n}^{2}}$ is Laplacian realizable only if $j>n-3$. ∎

The above theorem claims that for $i>1$ either $j=n-2$, $n-1$ or $n$. In the
sequel, we consider these three cases separately.

###  4.1. Graphs realizing the sets $S_{\\{i,n-2\\}_{n}^{2}}$

We start with the following fact established in [12].

######  Proposition 4.2 ([12]).

Let $n\geqslant 3$, if $S_{\\{i,j\\}_{n}^{m}}$ is Laplacian realizable, then
so is $S_{\\{i+1,j+1\\}_{n+2}^{m+1}}$.

The following theorem lists all the Laplacian realizable sets
$S_{\\{i,n-2\\}_{n}^{2}}$. We, remind that $i>1$.

######  Theorem 4.3.

Suppose $n\geqslant 6$. The only Laplacian realizable sets
$S_{\\{i,n-2\\}_{n}^{2}}$ are the following ones.

  * (i)

If $n\equiv 0\mod 4$, then for each $k=1,2,\ldots,\dfrac{n-6}{2}$,
$S_{\\{2k+2,n-2\\}_{n}^{2}}$ is Laplacian realizable;

  * (ii)

If $n\equiv 1\mod 4$, then for each $k=1,2,\ldots,\dfrac{n-5}{2}$,
$S_{\\{2k+2,n-2\\}_{n}^{2}}$ is Laplacian realizable;

  * (iii)

If $n\equiv 2\mod 4$, then for each $k=1,2,\ldots,\dfrac{n-4}{2}$,
$S_{\\{2k+1,n-2\\}_{n}^{2}}$ is Laplacian realizable;

  * (iv)

If $n\equiv 3\mod 4$, then for each $k=1,2,\ldots,\dfrac{n-5}{2}$,
$S_{\\{2k+1,n-2\\}_{n}^{2}}$ is Laplacian realizable.

######  _Proof_.

  * (i)

If $n\equiv 0\mod 4$, then $n-2\equiv 2\mod 4$, then for
$k=1,2,\ldots,\dfrac{n-6}{2}$, so the sets $S_{\\{2k+1,n-3\\}_{n-2}^{1}}$ are
Laplacian realizable by Theorem 3.2 (iii). From Proposition 4.2 it follows
that $S_{\\{2k+2,n-2\\}_{n}^{2}}$ is Laplacian realizable for each
$k=1,2,\ldots,\dfrac{n-6}{2}$. At the same time, the sets
$S_{\\{2k+1,n-2\\}_{n}^{2}}$ are not Laplacian realizable for any $k$ by
Theorem 2.12 (i), since the double eigenvalue $m=2$ is an even number in this
case.

  * (ii)

For $n\equiv 1\mod 4$, we have $n-2\equiv 3\mod 4$. Thus, for
$k=1,2,\ldots,\dfrac{n-5}{2}$, the sets $S_{\\{2k+1,n-3\\}_{n-2}^{1}}$ are
Laplacian realizable by Theorem 3.2 (iv). Now Proposition 4.2 implies that
$S_{\\{2k+2,n-2\\}_{n}^{2}}$ are Laplacian realizable for
$k=1,2,\ldots,\dfrac{n-5}{2}$. As $m=2$ is even, from Theorem 2.12 (ii) it
follows that the sets $S_{\\{2k+1,n-2\\}_{n}^{2}}$ are not Laplacian
realizable for any $k$.

The cases (iii) and (iv) can be proved analogously with the use of Theorem 3.2
and Proposition 4.2.

∎

The next theorem deals with the construction of graphs realizing the sets
$S_{\\{i,n-2\\}_{n}^{2}}$, $i>1$.

######  Theorem 4.4.

Let $n\geqslant 6$, and let $G$ be a connected graph of order $n$. Then $G$
realizes $S_{\\{i,n-2\\}_{n}^{2}}$ if and only if $G=K_{1}\vee\left(K_{1}\cup
H\right)$, where $H$ is a graph on $n-2$ vertices realizing
$S_{\\{i-1,n-3\\}_{n-2}^{1}}$.

######  _Proof_.

Let $G$ realize $S_{\\{i,n-2\\}_{n}^{2}}$. Then $G=G_{1}\vee G_{2}$ by Theorem
2.5, so $\overline{G}=\overline{G_{1}}\cup\overline{G_{2}}$. From Theorem 2.2
it follows that $\sigma_{L}(\overline{G})=\\{0\\}\cup
S_{\\{2,n-i\\}_{n-1}^{n-2}}$. Thus, by Theorem 2.1 we obtain that
$G_{1}=K_{1}$, and $G_{2}$ is of order $n-1$, so that
$\sigma_{L}(\overline{G_{2}})=S_{\\{2,n-i\\}_{n-1}^{n-2}}$. Using Theorem 2.2,
we get $\sigma_{L}(G_{2})=\\{0\\}\cup S_{\\{i-1,n-3\\}_{n-2}^{1}}$. Again
Theorem 2.1 gives us that $G_{2}=K_{1}\cup H$, where $H$ is a graph on $n-2$
vertices realizing $S_{\\{i-1,n-3\\}_{n-2}^{1}}$. Consequently,
$G=K_{1}\vee\left(K_{1}\cup H\right)$, as required.

Conversely, if $G=K_{1}\vee(K_{1}\cup H)$, where $H$ is a graph on $n-2$
vertices realizing $S_{\\{i-1,n-3\\}_{n-2}^{1}}$, then from Theorem 2.3 and
2.4 it follows that $G$ realizes $S_{\\{i,n-2\\}_{n}^{2}}$. ∎

######  Remark 4.5.

Theorems 4.3 and 4.4 completely resolve the existence of graphs realizing the
spectrum $S_{\\{i,n-2\\}_{n}^{2}}$, where $2\leqslant i\leqslant n-3$.

###  4.2. Graphs realizing the sets $S_{\\{i,n-1\\}_{n}^{2}}$

To determine all the graphs realizing the set $S_{\\{i,n-1\\}_{n}^{2}}$ for
various possible values of $i$, $i>1$, first we establish the following
auxiliary lemma.

######  Lemma 4.6.

The set $S_{\\{i,j\\}_{n}^{m}}$ is Laplacian realizable if and only if the set
$S_{\\{n-j+1,n-i+1\\}_{n+1}^{n+1-m}}$ is Laplacian realizable.

######  _Proof_.

Let $S_{\\{i,j\\}_{n}^{m}}$ be Laplacian realizable and let a graph $G$
realize $S_{\\{i,j\\}_{n}^{m}}$. Consider the graph $H=\overline{G}\vee
K_{1}$. Since the Laplacian spectrum of the graph $\overline{H}=G\cup K_{1}$
has the form $\\{0\\}\cup S_{\\{i,j\\}_{n}^{m}}$, the spectrum of $H$ is
$S_{\\{n-j+1,n-i+1\\}_{n+1}^{n+1-m}}$ by Theorem 2.2.

Conversely, suppose that $S_{\\{n-j+1,n-i+1\\}_{n+1}^{n-m+1}}$ is Laplacian
realizable, and a graph $H$ realizes it. According to Theorem 2.2, we have

(4.2) $\sigma_{L}(\overline{H})=\\{0\\}\cup S_{\\{i,j\\}_{n}^{m}}.$

Thus, $\overline{H}$ is the union of two disjoint graphs, say,
$\overline{H}=G\cup F$, and the Laplacian spectrum of $\overline{H}$ is the
union of the spectra of $G$ and $F$. Consequently, one of these graphs, say,
$G$, has $n$ as its Laplacian eigenvalue, so that its order is at least $n$ by
Theorem 2.1. Since the order of $\overline{H}$ is $n+1$, we have $F=K_{1}$.
Therefore, the graph $G$ of order $n$ realizes $S_{\\{i,j\\}_{n}^{m}}$,
according to (4.2). ∎

Now, we are in a position to describe all the Laplacian realizable sets
$S_{\\{i,n-1\\}_{n}^{2}}$. Remind that $i>1$.

######  Theorem 4.7.

Suppose $n\geqslant 6$. The only Laplacian realizable sets
$S_{\\{i,n-1\\}_{n}^{2}}$ are the following ones.

  * (i)

If $n\equiv 0\;or\;3\mod 4$, then $S_{\\{i,n-1\\}_{n}^{2}}$ is Laplacian
realizable if and only if $i=n-3$.

  * (ii)

If $n\equiv 1\;or\;2\mod 4$, then $S_{\\{i,n-1\\}_{n}^{2}}$ is Laplacian
realizable if and only if $i=n-2$.

######  _Proof_.

Let $G$ realizes $S_{\\{i,n-1\\}_{n}^{2}}$.

  * (i)

If $n\equiv 0\;or\;3\mod 4$, then $n-1\equiv 2\;or\;3\mod 4$, so by Theorem
2.15 (ii), the set $S_{\\{1,j\\}_{n-1}^{n-2}}$ is Laplacian realizable if and
only if $j=3$. Using Lemma 4.6, the set $S_{\\{n-j,n-1\\}_{n}^{2}}$ is also
Laplacian realizable if and only if $j=3$. Thus, $S_{\\{i,n-1\\}_{n}^{2}}$ is
Laplacian realizable only, if $i=n-3$.

  * (ii)

If $n\equiv 1\;or\;2\mod 4$, then $n-1\equiv 0\;or\;1\mod 4$. Therefore, by
Theorem 2.15 (i), the set $S_{\\{1,j\\}_{n-1}^{n-2}}$ is Laplacian realizable
if and only if $j=2$. Using Lemma 4.6, the set $S_{\\{n-j,n-1\\}_{n}^{2}}$ is
Laplacian realizable if and only if $j=2$. Consequently,
$S_{\\{i,n-1\\}_{n}^{2}}$ is Laplacian realizable only, if $i=n-2$.

∎

Our next result, discuss the structure of graphs realizing the sets
$S_{\\{i,n-1\\}_{n}^{2}}$, $i>1$ as follows.

######  Theorem 4.8.

Let $G$ be a graph of order $n$, $n\geqslant 6$.

  * (a)

The graph $G$ realizes $S_{\\{n-3,n-1\\}_{n}^{2}}$ if and only if $n\equiv 0$
or $3\mod 4$, and $G$ is formed in one of the following two ways:

    * (i)

$G=K_{1}\vee({K_{2}}\cup(K_{1}\vee(2K_{1}\cup H_{1})))$, where the graph
$H_{1}$ of order $n-6$ realizes $S_{1,n-6}$;

    * (ii)

$G=K_{1}\vee\left(K_{1}\cup\overline{F}\right)$, where the graph $F$ realizes
$S_{\\{2,n-2\\}_{n-2}^{n-3}}$.

  * (b)

The graph $G$ realizes $S_{\\{n-2,n-1\\}_{n}^{2}}$ if and only if $n\equiv 1$
or $2\mod 4$, and $G=K_{1}\vee\left(P_{3}\cup(K_{1}\vee\overline{H})\right)$,
where $H$ realizes $S_{n-7,n-5}$.

######  _Proof_.

(a) Let $G$ realizes $S_{\\{n-3,n-1\\}_{n}^{2}}$, and let $n\equiv 0$ or
$3\mod 4$. By Theorem 2.5, $G=G_{1}\vee G_{2}$, so
$\overline{G}=\overline{G_{1}}\cup\overline{G_{2}}$. From Theorem 2.2 it
follows that $\sigma_{L}(\overline{G})=\\{0\\}\cup S_{\\{1,3\\}_{n-1}^{n-2}}$.
Thus, by Theorem 2.1 we obtain that $G_{1}=K_{1}$, and $G_{2}$ is of order
$n-1$, so that $\sigma_{L}(\overline{G_{2}})=S_{\\{1,3\\}_{n-1}^{n-2}}$.
According to Theorem 2.16, the graph $\overline{G_{2}}$ can be formed in one
of the following two ways.

  * (i)

$\overline{G_{2}}=\left(K_{1}\cup K_{1}\right)\vee\left(K_{1}\cup H\right)$,
where the graph $H$ realizes $S_{\\{1,n-4\\}_{n-3}^{n-3}}$;

  * (ii)

$\overline{G_{2}}=K_{1}\vee F$, where the graph $F$ realizes
$S_{\\{2,n-2\\}_{n-2}^{n-3}}$.

Thus, from (i) one gets ${G_{2}}=K_{2}\cup\left(K_{1}\vee\overline{H}\right)$.
According to Theorem 2.2, one has $\sigma_{L}(\overline{H})=\\{0,0\\}\cup
S_{1,n-5}$. Thus, $\overline{H}$ can be represented as follows
$\overline{H}=2K_{1}\cup H_{1}$, where $H_{1}$ realizes $S_{1,n-5}$ (for the
construction of $H_{1}$ see Proposition 2.10). Thus,
$G=K_{1}\vee({K_{2}}\cup(K_{1}\vee(2K_{1}\cup H_{1})))$, where the graph
$H_{1}$ of order $n-6$ realizes $S_{1,n-6}$.

Also from (ii), we have ${G_{2}}={K_{1}\cup\overline{F}}$. According to
Theorem 2.2, one has $\sigma_{L}(\overline{F})=S_{\\{n-4,n-2\\}_{n-2}^{1}}$.
Thus, $G=K_{1}\vee\left(K_{1}\cup\overline{F}\right)$ where $F$ realizes
$S_{\\{2,n-2\\}_{n-2}^{n-3}}$ (for the construction of $H_{1}$ see Proposition
2.10).

Conversely, if $G=K_{1}\vee({K_{2}}\cup(K_{1}\vee(2K_{1}\cup H_{1})))$, where
the graph $H_{1}$ of order $n-6$ realizes $S_{1,n-6}$. Then, from Theorem 2.3
and 2.4, it follows that $G$ realizes $S_{\\{n-3,n-1\\}_{n}^{2}}$. Similarly,
if $G=K_{1}\vee\left(K_{1}\cup\overline{F}\right)$ where the graph $F$
realizes $S_{\\{2,n-2\\}_{n-2}^{n-3}}$, then again from Theorem 2.3 and 2.4,
the graph $G$ realizes $S_{\\{n-3,n-1\\}_{n}^{2}}$.

(b) Let $G$ realizes $S_{\\{n-2,n-1\\}_{n}^{2}}$ and let $n\equiv 1$ or $2\mod
4$. Then $G=G_{1}\vee G_{2}$ by Theorem 2.5, so
$\overline{G}=\overline{G_{1}}\cup\overline{G_{2}}$. From Theorem 2.2 it
follows that $\sigma_{L}(\overline{G})=\\{0\\}\cup S_{\\{1,2\\}_{n-1}^{n-2}}$.
Thus, by Theorem 2.1 we obtain that $G_{1}=K_{1}$, and $G_{2}$ is of order
$n-1$, so that $\sigma_{L}(\overline{G_{2}})=S_{\\{1,2\\}_{n-1}^{n-2}}$.
According to Theorem 2.16, the graph $\overline{G_{2}}$ is of the following
form. $\overline{G_{2}}=(K_{1}\cup K_{2})\vee(K_{1}\cup H)$, where $H$
realizes $S_{n-7,n-5}$. Thus, $G_{2}=P_{3}\cup(K_{1}\vee\overline{H})$.
According to Theorem 2.2, one has $\sigma_{L}(\overline{H})=\\{0\\}\cup
S_{2,n-6}$. Thus, $\overline{H}$ can be represented as follows
$\overline{H}=K_{1}\cup H_{1}$, where $H_{1}$ realizes $S_{2,n-6}$ (for the
construction of $H_{1}$ see Proposition 2.10). Consequently,
$G=K_{1}\vee\left(P_{3}\cup(K_{1}\vee\overline{H})\right)$, where $H$ realizes
$S_{n-7,n-5}$.

Conversely, if $G=K_{1}\vee\left(P_{3}\cup(K_{1}\vee\overline{H})\right)$,
where $H$ realizes $S_{n-7,n-5}$. Then, from Theorem 2.3 and 2.4 it follows
that $G$ realizes $S_{\\{n-2,n-1\\}_{n}^{2}}$. ∎

###  4.3. Graphs realizing the sets $S_{\\{1,j\\}_{n}^{2}}$ and
$S_{\\{i,n\\}_{n}^{2}}$

Now we are in a position to study graphs realizing the sets
$S_{\\{1,j\\}_{n}^{2}}$ ($i=1$) and $S_{\\{i,n\\}_{n}^{2}}$ ($j=n$). Since all
the correspondent graphs on less than 6 vertices have been listed, see
Appendix A, in what follows we consider $n\geqslant 6$. The structure of graph
realizing the set $S_{\\{1,j\\}_{n}^{2}}$ is described by the following
theorem.

######  Theorem 4.9.

Let $G$ be a graph of order $n$. Then for each admissible $j$, $1<j<n$ the
graph $G$ realizes $S_{\\{1,j\\}_{n}^{2}}$ if and only if $G=K_{1}\vee F$
where $F$ realizes $S_{\\{j-1,n-1\\}_{n-1}^{1}}$.

######  _Proof_.

Let $S_{\\{1,j\\}_{n}^{2}}$ for $1<j<n$ be Laplacian realizable by a graph
$G$. Then Theorem 2.2 implies

(4.3)
$\sigma_{L}(\overline{G})=\\{0,0,1,2,\ldots,n-j-1,n-j+1,\ldots,n-2,n-2\\}.$

Here $\overline{G}$ is a disconnected graph of the form
$\overline{G}=\overline{G_{1}}\cup\overline{G_{2}}$. By Theorem 2.1, one of
the components, say, $\overline{G_{2}}$, must be of order at least $n-2$.

If $\overline{G_{2}}$ has $n-2$ vertices, then $\overline{G_{1}}$ has two
vertices, and therefore $\sigma_{L}(\overline{G_{1}})=\\{0,2\\}$. By Theorem
2.2, we obtain $\sigma_{L}({G_{1}})=\\{0,0\\}$, so $G_{1}=2K_{1}$. Now from
(4.3), we have

$\sigma_{L}(\overline{G_{2}})=\\{0,1,\ldots,n-j-1,n-j+1\ldots,n-2,n-2\\}.$

This contradicts Theorem 2.6.

If $\overline{G_{2}}$ has $n-1$ vertices, then $\overline{G_{1}}=K_{1}$. Again
from (4.3)

$\sigma_{L}(\overline{G_{2}})=\\{0,1,2,\ldots,n-j-1,n-j+1\ldots,n-2,n-2\\},$

by Theorem 2.2,

$\sigma_{L}({G_{2}})=\\{0,1,1,2,\ldots,j-2,j\ldots,n-3,n-2\\}.$

Here the graph $G_{2}$ is of order $n-1$ realizes
$S_{\\{j-1,n-1\\}_{n-1}^{1}}$. Thus, $G=K_{1}\vee F$, where $F=G_{2}$ realizes
$S_{\\{j-1,n-1\\}_{n-1}^{1}}$.

Conversely, if $G=K_{1}\vee F$, where the graph $F$ of order $n-1$ realizes
$S_{\\{j-1,n-1\\}_{n-1}^{1}}$. Then from Theorems 2.4 it follows that $G$
realizes $S_{\\{1,j\\}_{n}^{2}}$. ∎

Theorem 4.9, guarantees that if the set $S_{\\{i,n\\}_{n}^{m}}$ is not
Laplacian realizable, then no graphs realizing $S_{\\{1,j\\}_{n}^{2}}$ exist.
From Theorem 4.9 it follows that for all admissible $j$, the sets
$S_{\\{1,j\\}_{n}^{2}}$ are Laplacian realizable only if the Conjecture 3.6 is
not true. Moreover, for $n=p+1$ where $p$ is a prime number, the set
$S_{\\{1,j\\}_{n}^{2}}$ is not Laplacian realizable according to Proposition
3.5. For instance, if $G$ is of order $n=6,8,12,14,18$ etc, then it does not
realize $S_{\\{1,j\\}_{n}^{2}}$.

Finally, we consider the case when $j=n$. Recall that for $n\leqslant 5$,
there are no graphs realizing the set $S_{\\{i,n\\}_{n}^{2}}$, see Appendix A.
As well, we conjectured in [12] that graphs realizing the set
$S_{\\{i,n\\}_{n}^{m}},n\geqslant 9$ do not exist. In that paper, it is also
shown that the set set $S_{\\{i,n\\}_{n}^{m}}$ is not Laplacian realizable for
a prime number $n$, and so the set $S_{\\{i,n\\}_{n}^{2}}$ is not Laplacian
realizable if $n$ is prime. Moreover, as we mentioned in Section 3 above, the
set $S_{\\{i,n\\}_{n}^{2}}$ is not Laplacian realizable by the Cartesian
product for $n\geqslant 9$. Additionally, for $i>1$, one can see from
Proposition 3.5 that $G$ has the minimum and maximum degree of the following
form:

$2\leqslant\min\limits_{1\leqslant i\leqslant
n}~{}d_{i}\leqslant\max\limits_{1\leqslant i\leqslant n}d_{i}\leqslant n-3,$

where $d_{i}$ is the degree of vertex $i$. So the minimum degree of graphs
realizing the sets $S_{\\{i,n\\}_{n}^{2}}$, $i>1$ and, more generally, the
sets $S_{\\{i,n\\}_{n}^{m}}$ (if any) is greater than or equal to $2$ and by
graph complement one can obtain the maximum degree $n-3$. If the minimum
degree equals $1$, then $G$ is a join, a contradiction. Note that this
property is analogous to the one of $S_{n,n}$-conjecture proposed in [7,
Section 3] the authors showed that for $n=8,9$ the set $S_{n,n}$ is not
Laplacian realizable. We believe that the same is true for sets
$S_{\\{i,n\\}_{n}^{m}}$. Thus, if $S_{n,n}$-conjecture is true, then our
$S_{\\{i,n\\}_{n}^{m}}$-conjecture will also hold true. According to these
observations, we believe that the set $S_{\\{i,n\\}_{n}^{2}}$, is not
Laplacian realizable. For more details on $S_{\\{i,n\\}_{n}^{m}}$-conjecture,
we refer the reader to [12, Section 5].

##  5\. Conclusion

In [12], we established the existence of graphs realizing the sets
$S_{\\{i,j\\}_{n}^{m}}$ for $m=n$ and $m=n-1$ and completely described them.
The present work continues our study on the realizability of sets
$S_{\\{i,j\\}_{n}^{m}}$ for cases $m=1,2$. We completely characterized the
graphs realizing those sets and developed an algorithm for constructing them
but the sets $S_{\\{1,j\\}_{n}^{2}}$ which are conjectured to be not Laplacian
realizable for large $n$.

######  Conjecture 5.1.

If $n\geqslant 3$, then the only Laplacian realizable set of kind
$S_{\\{1,j\\}_{n}^{2}}$ are $S_{\\{1,3\\}_{4}^{2}}$ and
$S_{\\{1,4\\}_{5}^{2}}$.

In addition, we believe that Lemma 4.6 and Proposition 4.2 provide a way
forward to find graphs realizing the sets $S_{\\{i,j\\}_{n}^{m}}$ for other
particular values of $m$ from already existing values of $m$. For instance,
the case $m=1$ can be obtained from the case $m=n$ using Lemma 4.6. In a
similar way, one can describe graphs realizing $S_{\\{i,j\\}_{n}^{m}}$ for
$m=2$ from those with $m=n-1$ using Lemma 4.6. As well, Proposition 4.2 can
help to find the repeated eigenvalue $m$ from previously known values of $m$.
However, it is not clear whether the use of Proposition 4.2 and Lemma 4.6 may
cover all the sets realizing $S_{\\{i,j\\}_{n}^{m}}$ for fixed $m$ and $n$.

##  Appendix A List of Laplacian integral graphs realizing
$S_{\\{i,n-1\\}_{n}^{1}}$ up to order $8$

In the paper by $K_{n}$, $P_{n}$, $K_{1,n-1}$ and $K_{p,q}~{}(p+q=n)$ we
denote the complete graph, the path graph, the star graph and the complete
bipartite graph on $n$ vertices, respectively. For the concepts and results
about graphs not presented here, see, e.g., Bondy and Murty [2], and Diestel
[6].

In [3, p. 301–304] the authors found the Laplacian spectra of all graphs up to
order $5$. Also in [4], the authors depicted all the graphs of order $6$
without calculating their Laplacian spectra. We lists all the graphs realizing
the sets $S_{\\{i,j\\}_{n}^{1}}$ and $S_{\\{i,j\\}_{n}^{2}}$ up to order $6$.
Also, we list few graphs of order $7$ and $8$ of such types. Note that we use
the notation $A_{n}$ for the anti-regular graph of order $n$, see, e.g., [23].

Table 1. Laplacian integral graphs realizing $S_{\\{i,j\\}_{n}^{1}}$ for
$n=4,5,6,7,8.$

Construction | Laplacian Spectrum | $\boldsymbol{S_{\\{i,j\\}_{n}^{m}}}$
---|---|---
$S_{4}\cong K_{3,1}$ | ${\\{0,1,1,4\\}}$ | $S_{\\{2,3\\}_{4}^{1}}$
$K_{1}\vee\overline{K_{1,1,2}}$ | ${\\{0,1,1,3,5\\}}$ | $S_{\\{2,4\\}_{5}^{1}}$
$K_{1}\vee(2K_{1}\cup P_{3})$ | ${\\{0,1,1,2,4,6\\}}$ | $S_{\\{3,5\\}_{6}^{1}}$
$K_{1}\vee(P_{3}\cup\overline{P_{3}})$ | ${\\{0,1,1,2,3,4,7\\}}$ | $S_{\\{5,6\\}_{7}^{1}}$
$K_{1}\vee[2K_{1}\cup(K_{1}\vee\overline{P_{3}})]$ | ${\\{0,1,1,2,4,5,7\\}}$ | $S_{\\{3,6\\}_{7}^{1}}$
$[(2K_{1}\vee\overline{P_{3}})\cup 2K_{1}]\vee K_{1}$ | ${\\{0,1,1,3,4,5,6,8\\}}$ | $S_{\\{2,7\\}_{8}^{1}}$
$(A_{5}\cup 2K_{1})\vee K_{1}$ | ${\\{0,1,1,2,3,5,6,8\\}}$ | $S_{\\{4,7\\}_{8}^{1}}$
$(\overline{P_{3}}\cup A_{4})\vee K_{1}$ | ${\\{0,1,1,2,3,4,5,8\\}}$ | $S_{\\{6,7\\}_{8}^{1}}$

Table 2. Laplacian integral graphs realizing $S_{\\{i,j\\}_{n}^{2}}$ for
$n=4,5,6,7,8.$

Construction | Laplacian Spectrum | $\boldsymbol{S_{\\{i,j\\}_{n}^{m}}}$
---|---|---
$C_{4}$ | ${\\{0,2,2,4\\}}$ | $S_{\\{1,3\\}_{4}^{2}}$
$K_{3,2}$ | ${\\{0,2,2,3,5\\}}$ | $S_{\\{1,4\\}_{5}^{2}}$
${(K_{3,1}\cup K_{1})\vee K_{1}}$ | ${\\{0,1,2,2,5,6\\}}$ | $S_{\\{3,4\\}_{6}^{2}}$
$(K_{3,1}\cup K_{2})\vee K_{1}$ | ${\\{0,1,2,2,3,5,7\\}}$ | $S_{\\{4,6\\}_{7}^{2}}$
$[[(K_{2}\cup 2K_{1})\vee K_{1}]\cup K_{2}]\vee K_{1}$ | ${\\{0,1,2,2,3,4,6,8\\}}$ | $S_{\\{5,7\\}_{8}^{2}}$
$K_{1}\vee[K_{1}\cup(K_{1}\vee(2K_{1}\cup P_{3}))]$ | ${\\{0,1,2,2,3,5,7,8\\}}$ | $S_{\\{4,6\\}_{8}^{2}}$

##  Appendix B Acknowledgements

The work of M. Tyaglov was partially supported by National Natural Science
Foundation of China under grant no. 11901384.

## References

  * [1] K. Balińska, D. Cvetković, Z. Radosavljević, S. Simić, and D. Stevanović, A survey on integral graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 13 (2003), 42–65.
  * [2] J.A. Bondy, U.S.R. Murty, Graph theory with applications, vol.290, North-Holland, New York, 1976.
  * [3] D. Cvetkovic, P. Rowlinson, and S. Simic, An introduction to the theory of graph spectra, Cambridge University Press Cambridge, 2010.
  * [4] D. Cvetkovic, M. Petric, A table of connected graphs on six vertices, Discrete Math. 50 (2005), no. 1, 37–49.
  * [5] L. S. de Lima, N. M. M. de Abreu, C. S. Oliveira, and M. A. A. de Freitas, Laplacian integral graphs in $S(a,b)$, Linear Algebra Appl. 423 (2007), 136–145.
  * [6] R. Diestel, Graph Theory, Graduate Texts in Mathematics, vol.173, 4th edn. Springer, Heilderberg (2010).
  * [7] S.M. Fallat, S.J. Kirkland, J.J. Molitierno, and M. Neumann, On graphs whose Laplacian matrices have distinct integer eigenvalues,J. Graph. Theory. 50 (2005), no. 2, 162–174.
  * [8] M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973), 298–305.
  * [9] A. Goldberger and M. Neumann, On a conjecture on a Laplacian matrix with distinct integral spectrum, J. Graph Theory. 72 (2013), 178–208.
  * [10] R. Grone and R. Merris, Indecomposable Laplacian integral graphs, Linear Algebra and its Applications. 428 (2008), no. 7, 1565–1570.
  * [11] A. Hameed, Z.U. Khan and M. Tyaglov, Laplacian energy and first Zagreb index of Laplacian integral graphs, Analele Stiintifice ale Universitatii Ovidius din Constanta, Math. Series. 30 (2022), no. 2, 133–160.
  * [12] A. Hameed and M. Tyaglov, Integral Laplacian graphs with a unique double Laplacian eigenvalue, I, submitted. ArXiV: 2206.00980.
  * [13] P.L. Hammer and A.K. Kelmans, Laplacian spectra and spanning trees of threshold graphs, Discrete Applied Mathematics. 65 (1996), no. 1-3, 255–273.
  * [14] F. Harary and A.J. Schwenk, Which graphs have integral spectra?, Graphs and Combinatorics. Springer-Verlag, Berlin 1974, 45–51
  * [15] S. Kirkland, Completion of Laplacian integral graphs via edge addition, Discrete mathematics. 295, no. (1-3), 2007, pp. 75–90.
  * [16] S. Kirkland, Constructably Laplacian integral graphs, Linear Algebra and its Applications. 423 (2007), no. 1, 3–21.
  * [17] S. Kirkland, Laplacian integral graphs with maximum degree 3, Electron. J. Combin. 15 (2008), no. 15, Research Paper 120.
  * [18] S. Kirkland, M. A. A. de Freitas, R. R. Del Vecchio, and N. M. M. Abreu, Split non-threshold Laplacian integral graphs, Linear Multilinear Algebra. 58 (2010), 221–233.
  * [19] S. Kirkland, J.J Molitierno, M. Neumann, and L.B. Shader, On graphs with equal algebraic and vertex connectivity, Linear Algebra and its Applications. 341 (2002), no. 1-3, 45–56.
  * [20] R. Merris, Laplacian graph eigenvectors, Discrete Appl. Math. 278 (1998), no. 1-3, 221–236.
  * [21] R. Merris, Graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization. 50 (2001), no. 2, xiv+237.
  * [22] R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197/198 (1994), 143–176.
  * [23] R. Merris, Degree maximal graphs are Laplacian integral, Linear Algebra Appl. 199 (1994), 381–389.
  * [24] R. Merris, Large families of Laplacian isospectral graphs, Linear and Multilinear Algebra. 43 (1997), 201–205.
  * [25] R. Merris, Threshold graphs, In Proceedings of the Prague Mathematical Conference 1996, Icaris, Prague, 205–210..
  * [26] J.J. Molitierno, Applications of combinatorial matrix theory to Laplacian matrices of graphs, London, UK.: Champan & Hall, 2016, 123.
  * [27] X.D. Zhang, The Laplacian eigenvalues of graphs: a survey, Linear Algebra Res.Adv. 2007, 201–228.