% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all commands that change parameters such as
%    margins or page sizes.

% Packages amssymb and amsthm are already loaded. 
% We recommend these AMS packages:
\usepackage{amsmath,amssymb}
% We recommend the graphicx package for importing figures:
\usepackage{graphicx}
% Use this command to create hyperlinks (optional and recommended):
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% Theorem-like environments that are declared in the style file are:
% theorem, lemma, corollary, proposition, fact, observation, claim,
% definition, example, conjecture, open, problem, question, remark, note

%\newtheorem{question}{Question}

\newcommand{\R}{\mathbb R}
\newcommand{\G}{\overline G}
\renewcommand{\d}[1][G]{\overline{d}(#1)}
\newcommand{\lspectrum}[2][\mu]{#1_1\geq #1_2\geq\cdots\geq #1_{#2}}
\newcommand{\multipartite}[2][n]{K_{#1_1,\ldots,#1_{#2}}}


%%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Give the submission and acceptance dates in the format shown.
% The editors will insert the publication date in the third argument.
\dateline{Sep 19, 2017}{Nov 1, 2018}{TBD}

% Give one or more subject codes separated by commas.
% Codes are available from http://www.ams.org/mathscinet/freeTools.html
\MSC{05C50; 97K30; 35Pxx}

% Uncomment exactly one of the following copyright statements.  Alternatively,
% you can write your own copyright statement subject to the approval of the journal.
% See https://creativecommons.org/licenses/ for a full explanation of the 
% Creative Commons licenses.
%
% We strongly recommend CC BY-ND or CC BY. Both these licenses allow others
% to freely distribute your work while giving credit to you. The difference between
% them is that CC BY-ND only allows distribution unchanged and in whole, while
% CC BY also allows remixing, tweaking and building upon your work.  
%
%    One author:
%\Copyright{The author.}
%\Copyright{The author. Released under the CC BY license (International 4.0).}
%\Copyright{The author. Released under the CC BY-ND license (International 4.0).}
%    More than one author:
%\Copyright{The authors.}
%\Copyright{The authors. Released under the CC BY license (International 4.0).}
\Copyright{  The authors. Released under the CC BY-ND license (International 4.0).}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% If needed, include a line break (\\) at an appropriate place in the title.
%\title{An elementary proof\\ of the reconstruction conjecture}

% Input author, affiliation, address and support information as follows;
% The address should include the country, but does not have to include
%    the street address. Give at least one email address.

%\author{First Author\thanks{Supported by NASA grant ABC123.}\\
%\small Department of Inconsequential Studies\\[-0.8ex]
%\small Solatido College\\[-0.8ex] 
%\small North Kentucky, U.S.A.\\
%\small\tt first.author@dis.solatido.edu\\
%\and
%Some Second Author \qquad  Some Third Author\\
%\small School of Hard Knocks\\[-0.8ex]
%\small University of Western Nowhere\\[-0.8ex]
%\small Somewhere, Australia\\
%\small\tt \{ssa,sta\}@uwn.edu.au}

\title{Partial characterization of graphs having a single large Laplacian eigenvalue}

\author{L.~Emilio Allem \thanks{Instituto de Matem\'atica, Universidade Federal do Rio Grande do Sul, Brazil} \footnotemark[6] , 
Antonio Cafure \thanks{CONICET, Argentina} \thanks{Instituto del Desarrollo Humano, Universidad Nacional de General Sarmiento, 
Argentina. \newline ${}^{}$\hspace{0.5cm} Depto.\ de Matem{\'a}tica, CBC, Universidad de Buenos Aires, Argentina} \footnotemark[6] , 
Ezequiel Dratman \footnotemark[2] \thanks{Instituto de Ciencias, Universidad Nacional de General Sarmiento, Argentina} \footnotemark[6] ,\\
Luciano N.~Grippo \footnotemark[4] \footnotemark[6] , 
Mart\'in D.~Safe \thanks{Departamento de Matem{\'a}tica, Universidad Nacional del Sur,  Argentina. \newline  ${}^{}$\hspace{0.5cm} INMABB, Universidad Nacional 
del Sur (UNS)-CONICET, Argentina} \footnotemark[6] , 
Vilmar Trevisan \footnotemark[1] \thanks{Email addresses: \href{mailto:emilio.allem@ufrgs.br}{emilio.allem@ufrgs.br} (L.\ E.\ 
Allem), \href{mailto:acafure@ungs.edu.ar} {acafure@ungs.edu.ar} (A.\ Cafure), \newline  
${}^{}$\hspace{0.5cm} \href{mailto:edratman@ungs.edu.ar}{edratman@ungs.edu.ar} (E.\ Dratman), \href{mailto:lgrippo@ungs.edu.ar}{lgrippo@ungs.edu.ar} (L.\ N.\ 
Grippo),\newline  ${}^{}$\hspace{0.5cm} \href{mailto:msafe@uns.edu.ar}{msafe@uns.edu.ar} (M.\ D.\ Safe), \href{trevisan@mat.ufrgs.br}{trevisan@mat.ufrgs.br} 
(V.\ Trevisan)}}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract may be distributed without the rest of the
% paper so it must be entirely self-contained.  Try to include all words
% and phrases that someone might search for when looking for your paper.

\begin{abstract}
The parameter $\sigma(G)$ of a graph $G$ stands for the number of Laplacian eigenvalues greater than or equal to the average degree of $G$. In this work, we 
address the problem of characterizing those graphs $G$ having $\sigma(G)=1$. Our conjecture is that these graphs are stars plus a (possible empty) set of 
isolated vertices. We establish a link between $\sigma(G)$ and the number of anticomponents of $G$. As a by-product, we present some results which support the 
conjecture, by restricting our analysis to cographs, forests, and split graphs.
\end{abstract}

\section{Introduction}
 Let $G$ be  a graph on $n$ vertices and $m$ edges and let $d_1 \geq \cdots \geq d_n$ be its degree sequence. We denote by  $A(G)$  its adjacency matrix and by  
$D(G)$ the diagonal matrix having $d_i$ in the diagonal entry $(i,i)$, for every $1\le i\le n$,  and $0$ otherwise. The \emph{Laplacian matrix} of $G$ is the 
positive semidefinite matrix $L(G)=D(G)-A(G)$. The  eigenvalues of $L(G)$ are called \emph{Laplacian eigenvalues} of $G$;  the spectrum of $L(G)$  is the   
\emph{Laplacian spectrum} of $G$ and will be denoted by $Lspec(G)$.  Since it is  easily seen that $0$ is a Laplacian eigenvalue  and it is well-known that 
Laplacian eigenvalues are less than or equal to  $n$ it turns out that $Lspec(G) \subset [0,n]$. From now on, if $Lspec(G) =\{\mu_1,\mu_2,\ldots,\mu_n\}$, we 
will assume that $\mu_1 \geq \mu_2 \geq \cdots \geq \mu_n$, where $\mu_n=0$.

 Understanding the distribution of Laplacian eigenvalues of graphs is a problem that is both relevant and difficult. It is relevant due to the many 
applications 
related  to Laplacian matrices (see, for example, \cite{Moh91,Moh92}). It seems to be difficult because little is known about how the Laplacian eigenvalues are 
distributed in the interval $[0,n]$.

 Our main motivation is understanding the structure of graphs that have few large Laplacian eigenvalues. In particular, we would like to characterize graphs 
that have a single large Laplacian eigenvalue. What do we mean by a large Laplacian eigenvalue?  A reasonable measure is to compare this
 eigenvalue with the average of all eigenvalues. Since the average of Laplacian eigenvalues equals the average degree $\d = \frac{2m}{n}$ of $G$, we say that a 
Laplacian eigenvalue is \emph{large} if it is greater than or equal to the average degree.

 Inspired by this idea, the paper~\cite{Das16} introduces the spectral parameter $\sigma(G)$ which counts
 the number of Laplacian eigenvalues greater than or equal to $\d$. Equivalently,  $\sigma(G)$ is the largest index $i$ for which $\mu_i \geq \frac{2m}{n}$. 
Since  the greatest Laplacian eigenvalue $\mu_1$ is at least $\frac{2m}{n}$ then it follows that  $\sigma(G)\ge 1$. 

 There is evidence that $\sigma(G)$ plays an important role in defining structural properties of a graph $G$. For example, it is related to the clique number 
$\omega$ of $G$ (the number of vertices of the largest induced  complete subgraph of $G$) and it also gives insight about the Laplacian energy of a graph 
\cite{Pirzada2015,Das16}. Pirzada and Ganie~\cite{Pirzada2015} conjectured that $\sigma(G)\geq\omega-1$. Later, this conjectured was disproved 
in~\cite{Das16} by showing a counterexample within the class of threshold graphs. Moreover, several structural properties of a graph are related to  $\sigma$ 
(see, for example, \cite{Das2015,Das16}).  

 In this paper we are concerned with furthering the study of  $\sigma(G)$. In particular, we deal with a  problem posed in  \cite{Das16} which asks for 
characterizing all graphs $G$ having $\sigma(G)=1$; \emph{i.e.}, having only one large Laplacian eigenvalue. Our conjecture is that the only connected graph on 
$n$ vertices having $\sigma=1$ is the star $K_{1,n-1}$ and that the  only disconnected graph on  $n$ vertices having $\sigma=1$ is a star 
together with some isolated vertices. More precisely, 
 we conjecture that  graphs having $\sigma = 1$ are some stars plus a (possibly empty) set of isolated vertices. From now on, $K_{1,r}+sK_1$ denotes the star on 
$r+1$ vertices plus $s$ isolated vertices.

\begin{conjecture}\label{conjecture:1}
 Let $G$ be a graph. Then $\sigma(G)=1$ if and only if $G$ is isomorphic to $K_1$, $K_2+sK_1$ for some $s\geq 0$, or $K_{1,r}+sK_1$ for some $r\geq 2$ and 
$0\leq s<r-1$.
\end{conjecture}

In this work, we show that this conjecture is true if it holds for graphs which are simultaneously connected and co-connected (Conjecture~\ref{conjecture:3}) 
and prove that Conjecture~\ref{conjecture:1} is true for cographs, forests, and split graphs. The main tool for  proving our results is an 
interesting  link we have found between  $\sigma$ and the number of  anticomponents of $G$ (see Section~\ref{section:definitions}). %
The interesting feature of this result is that it relates a spectral parameter with a classical structural parameter. Studying structural properties of the 
anticomponents of $G$ may shed light on the distribution of Laplacian eigenvalues and, reciprocally, the distribution of Laplacian eigenvalues should give 
insight about the structure of the graph.

This article is organized as follows. In Section~\ref{section:definitions} we state  definitions and previous results concerning Laplacian eigenvalues. In 
Section~\ref{sec:anticomponents}, we present some new results which establish the connection between $\sigma$ and the number of nonempty anticomponents of $G$. 
In Section~\ref{section: sigma equals one}, we present some evidence on the validity of Conjecture~\ref{conjecture:1} by proving that the conjecture is true 
when $G$ is a cograph, a forest, or a split graph.

\section{Definitions}\label{section:definitions}

In this article, all graphs are finite, undirected, and without multiple edges or loops. All definitions and concepts not introduced here can be found 
in~\cite{west_introduction_2000}. We say that a graph is \emph{empty} if it has no edges. A \emph{trivial} graph is a graph with  precisely one vertex; every 
trivial graph is isomorphic to the graph which we will denote by $K_1$. A graph is \emph{nontrivial} if it has more than one vertex.

We use the standard notation $\Delta(G)$ to denote the maximum degree of a graph $G$.  

Let $G_1$ and $G_2$ be two graphs such that $V(G_1)\cap V(G_2)=\emptyset$. The \emph{disjoint union} of $G_1$ and $G_2$, denoted $G_1+G_2$, is the graph whose 
vertex set is $V(G_1)\cup V(G_2)$, and its edge set is $E(G_1)\cup E(G_2)$. We write $kG$ to represent the disjoint union $G + \cdots + G$ of $k$ copies of a 
graph $G$. 
The \emph{join} of $G_1$ and $G_2$, denoted $G_1 \vee G_2$, is the graph obtained from $G_1 + G_2$ by adding new edges from each vertex  of $G_1$ to every 
vertex of $G_2$. 

A vertex $v$ of a graph $G$ is a \emph{twin} of another vertex $w$ of $G$ if they both have the same neighbors in $V(G)\setminus\{v,w\}$. We say that a graph 
$G'$ is obtained from $G$ \emph{by adding a twin} $v^\prime$ to a vertex $v$ of $G$ if $V(G')=V(G)\cup\{v'\}$, $v'$ is a twin of $v$ in $G'$,  and $G'-v'$ is 
isomorphic to $G$. 

By $G[S]$ we denote the subgraph  of $G$ induced by a subset $S \subseteq V(G)$. 

We use $\overline G$ to denote the complement graph of a graph $G$. An \emph{anticomponent} of a graph $G$ is the subgraph of $G$ induced by the vertex set of a 
connected component of $\overline G$. More precisely, an induced subgraph $H$ of $G$ is an anticomponent if $\overline H$ is a connected component of 
$\overline{G}$. Notice that if $G_1,G_2,\ldots,G_k$ are the anticomponents of $G$, then $G=G_1\vee\cdots\vee G_k$. A graph $G$ is \emph{co-connected} if 
$\overline{G}$ is connected.

A \emph{forest} is a graph with no cycles and a \emph{tree} is a connected forest. The complete graph on $n$ vertices is denoted by $K_n$. A \emph{universal 
vertex} of a graph $G$ is a vertex $v$ adjacent to every vertex $w$ different from $v$. A \emph{star} is a graph   isomorphic to $K_1$ or to a tree with a 
universal vertex. We use $K_{1,n-1}$ to denote the star on $n$ vertices, where $K_{1,0}$ is isomorphic to $K_1$ and $K_{1,1}$ is isomorphic to $K_2$. The 
\emph{chordless path} (respectively,  \emph{cycle}) on $k$ vertices is denoted by $P_k$ (respectively, \ $C_k$). 

A \emph{stable set} of a graph is a set of pairwise nonadjacent vertices. A \emph{clique} of a graph is a set of pairwise adjacent vertices. 

Throughout this article, given  two graphs $G$ and $H$,   we write $G=H$ to point out  that $G$ and $H$ belong to the same isomorphism class.

Brouwer and Haemers~\cite{BrowerandHamers2008} provided a lower bound for the $k$-th Laplacian eigenvalue of a graph in terms of $d_k$, answering 
a conjecture raised by Guo~\cite{Guo2007}.

\begin{theorem} [\cite{BrowerandHamers2008}]\label{thm: Brouwer and Haemers}
Let $G$ be a graph on $n$ vertices. If $G$ is not isomorphic to $K_k+(n-k)K_1$, then $\mu_k(G)\ge d_k-k+2$.
\end{theorem}

Throughout this article we will use the lower bounds corresponding to the cases $k=1$~\cite{Gro90} and $k=2$~\cite{MR1813439}. 

It is easy to prove  that the Laplacian spectrum of the disjoint union $G_1 + G_2$ is the union of the Laplacian spectrums of $G_1$ and $G_2$. The next result  
allows to determine the Laplacian spectrum of the join $G_1 \vee G_2$,  from those of $G_1$ and $G_2$.

\begin{theorem}[{\cite[Theorem 2.20]{MR1275613}}]\label{theorem:laplacian spectrum  disjoint union and join}
 Let $G_1$ and $G_2$ be two graphs with Laplacian spectrums $\lspectrum{n_1}=0$ and $\lspectrum[\lambda]{n_2}=0$, respectively.
 Then the Laplacian eigenvalues of  $G_1\vee G_2$ are $n_1 + n_2$;  $n_2 + \mu_i$, for $1\leq i \leq n_1-1$; $n_1 + \lambda_{i}$, for $1\leq i \leq n_2-1$ and 
0.
\end{theorem}

\section{Relating $\sigma$ and the number of anticomponents}\label{sec:anticomponents}

This section is devoted to establish a link between $\sigma(G)$ and the number of anticomponents of $G$.

In virtue of Theorem~\ref{theorem:laplacian spectrum  disjoint union and join}, the following result immediately holds.

 \begin{lemma}\label{lemma:multjoin}
 If $G=G_1\vee\cdots\vee G_k$, with  $k \geq 1$, is a graph on $n$ vertices, then $n$ is a Laplacian  eigenvalue of $G$
 with multiplicity at least $k-1$.
\end{lemma}

 \begin{lemma}\label{lemma:anticomponents less than or equal to  sigma + 1}
 If $G$ has  $k$ anticomponents,  then $k \leq \sigma(G) + 1$.
\end{lemma}

 \begin{proof}
 Let $G=G_1\vee\cdots\vee G_k$ where $G_1,\ldots,G_k$ are the anticomponents of $G$.
 For any graph $G$ with at least one vertex we have that  $\sigma(G) \geq 1$ and thus the assertion follows when $k=1$. We may assume that $k \geq 2$. 
Lemma~\ref{lemma:multjoin}  implies that $n$ is a Laplacian  eigenvalue of $G$ with  multiplicity at least $k-1$ in $G$. Thus $\mu_{k-1}(G) =  n$ which implies 
that   $\sigma(G) \geq k-1$.
 \end{proof}

\begin{remark}
 The upper bound given by Lemma \ref{lemma:anticomponents less than or equal to  sigma + 1} is sharp  when  $\sigma(G) > 1$. 
 Indeed, for  $s\geq 2$ consider  the graph $G = 4 K_2 \vee K_1\vee \cdots \vee K_1$, where $s$ is the number of $K_1$'s. The  average degree of $G$ 
  is $s+7 - \frac{48}{s+8}$ and it has $s + 1$ anticomponents.  Since its Laplacian eigenvalues are  $s+8$, $s+2$, $s$, and $0$ with multiplicities $s$, $4$, 
$3$, and $1$, respectively, it follows that  $\sigma(G) = s$.
\end{remark}

 We use $\ell(G)$ to denote the number of nonempty anticomponents of a graph $G$. Recall that a nontrivial graph has at least two vertices. The following result 
looks further into the case where equality holds in  Lemma~\ref{lemma:anticomponents less than or equal to  sigma + 1} showing  that $\sigma(G)$ is an upper 
bound for $\ell(G)$.

\begin{theorem}\label{theorem:anticomponents}
 Let $G$ be a graph having $k = \sigma(G)+1$ anticomponents. Then $\ell(G) \leq \sigma(G)$. Moreover, if $\sigma(G)=\ell(G)$, then the remaining anticomponent 
of $G$ is empty but nontrivial.
\end{theorem}

\begin{proof}
 Write  $G=G_1\vee\cdots\vee G_k$ where $G_1,\ldots,G_k$ are the anticomponents of $G$. Since $\sigma(G)\ge 1$ then $k\ge 2$. We set the following notations  
for each $i\in\{1,\ldots,k\}$: \[
    n_i=\vert V(G_i)\vert, \quad  m_i=\vert E(G_i)\vert, \quad  \mu^{(i)}_1=\mu_1(G_i).
 \]
 Assume that $G_1, \ldots, G_\ell$ are the nonempty anticomponents. Since $k\geq 2$ and we are assuming that $\sigma(G) = k-1$ it turns out that  $\mu_k(G) < 
\overline d(G)$. Therefore, for each $i\in\{1,\ldots,k\}$ such that $n_i>1$ we have that
 \[
   n-n_i+\mu_1^{(i)}\leq\mu_k(G)< \frac{2m}n=\frac{2\sum_{j=1}^km_j+2\sum_{1\leq i<j\leq k}n_in_j}n,
 \]
 the first inequality holds by Theorem~\ref{theorem:laplacian spectrum  disjoint union and join}. Equivalently,
 \begin{equation}
 \begin{aligned}\label{eq:mu1}
  \mu_1^{(i)}&<\frac{2\sum_{j=1}^km_j-(n^2-2\sum_{1\leq i<j\leq k}n_in_j)}n+n_i\\
             &=\frac{2\sum_{j=1}^km_j-\sum_{j=1}^k n_j^2+nn_i}n.
 \end{aligned}
 \end{equation}

 As a consequence of Theorem~\ref{thm: Brouwer and Haemers}, we
 obtain  the following  lower bound for each  $i\in\{1,\ldots,\ell\}$:
 \begin{equation}\label{eq:mu2}
  \mu_1^{(i)}\geq\Delta(G_i)+1\geq\overline d(G_i)+1=\frac{2m_i}{n_i}+1.
 \end{equation}
 Combining  \eqref{eq:mu1} and \eqref{eq:mu2}, we deduce that, for each $i\in\{1,\ldots,\ell\}$,
 \begin{equation}\label{eq:mu3}
  2n_i\sum_{j=1}^k m_j-n_i\sum_{j=1}^k n_j^2+nn_i^2-2nm_i-nn_i>0.
 \end{equation}

Arguing towards a contradiction, suppose that $\ell(G) = k$. If we sum up the left-hand side of \eqref{eq:mu3} for each $i\in\{1,\ldots,k\}$, we obtain
 \[
   2n\sum_{j=1}^km_j-n\sum_{j=1}^kn_j^2+n\sum_{i=1}^kn_i^2-2n\sum_{i=1}^km_i-n^2 = -n^2
 \]
 which is not a positive quantity. This contradiction proves that $G$ has at most $k-1 = \sigma(G)$ nonempty anticomponents and our first assertion follows.

Assume now that $\ell(G)= k-1$. Suppose that $G_k$ is trivial. Hence $n_k=1$ and $m_k=0$. Summing up to the left-hand side of \eqref{eq:mu3} for each 
$i\in\{1,\ldots,k-1\}$, we obtain that
 \[
   -2\sum_{j=1}^{k-1}m_j+\sum_{j=1}^k n_j^2-n^2 = -2\sum_{j=1}^{k-1} m_j-2\sum_{1\leq i<j\leq k}n_in_j
 \]
 should be a positive number. This contradiction shows that $G_k$ must be nontrivial.
 \end{proof}

Recall that a \emph{bipartite graph} is a graph whose set of vertices can be partitioned into two (possibly empty) stable sets called \emph{partite sets} of the 
bipartite graph. A \emph{complete bipartite graph} is a bipartite graph isomorphic to $rK_1\vee sK_1$ for two positive integers $r$ and $s$.  We  denote by 
$K_{r,s}$  the complete bipartite graph isomorphic to $rK_1\vee sK_1$. The upper bound $\sigma(G)$ on $\ell(G)$ for those graphs having exactly $\sigma(G)+1$ 
anticomponents is not tight when $\sigma(G)=1$. Indeed, the following result shows that if a graph $G$ has $\sigma(G)=1$, then $G$ has no nonempty 
anticomponents.

\begin{corollary}\label{corollary:co-connected}
 If $G$ is a graph on $n$ vertices with $\sigma(G)=1$ and $\overline{G}$ is disconnected, then $G=K_{1,n-1}$.
\end{corollary}

 \begin{proof}
In virtue of Lemma~\ref{lemma:anticomponents less than or equal to  sigma + 1}, the number of anticomponents of $G$ is at most $2$. Since $\overline{G}$ is  
disconnected, we conclude that $G$ has precisely two anticomponents $G_1$ and $G_2$ and thus $G = G_1 \vee G_2$.

Suppose, for a contradiction, that $G_1$ is a  nonempty anticomponent of $G$. Because of Theorem~\ref{theorem:anticomponents}, we conclude that
$G_2$ is empty but nontrivial. Following the notation used in the proof of Theorem~\ref{theorem:anticomponents}, we have that $m_2=0$. For $i=1$,   
inequality~\eqref{eq:mu3} becomes
 \begin{equation}\label{eq:mu4}
  -2n_2m_1-n_1n_2^2+n_2n_1^2-n_1^2-n_1n_2 > 0.
 \end{equation}
Since $G_2$ is a nontrivial empty graph it follows that  $\mu_1^{(2)}=0$ and hence,  for $i=2$,  inequality~\eqref{eq:mu1}  becomes
 \begin{equation}\label{eq:mu5}
  2m_1-n_1^2 + n_1n_2 >0.
 \end{equation}
 Summing up \eqref{eq:mu4} and  $n_2$ times \eqref{eq:mu5} gives
 \[
  -n_1^2-n_1n_2>0.
 \]
This contradiction arose from supposing that $G$ has some nonempty anticomponent. Hence, both anticomponents of $G$ are empty; \emph{i.e.}, $G$ is a complete 
bipartite graph.

 Since $G=K_{n_1,n_2}$, where $n_2\geq n_1\geq 1$ and $n = n_1+n_2$, the average degree of $G$ is equal to $\frac{2n_1n_2}n$.   
  In virtue of Theorem~\ref{theorem:laplacian spectrum  disjoint union and join}, the Laplacian eigenvalues  of $K_{n_1,n_2}$ are 
  $n$, $n_2$, $n_1$ and 0, each with multiplicity $1$, $n_1-1$, $n_2-1$ and $1$, respectively.
  
  Arguing towards a contradiction, suppose that $n_1\geq 2$. Hence $\mu_2(G) = n_2$. Since  $ 2n_1\le n$, we deduce that $\overline 
d(G)=\frac{2n_1n_2}n \leq \mu_2(G)$, which contradicts the fact that  $\sigma(G)=1$. This contradiction proves that $n_1=1$ and therefore we conclude that  
$G=K_{1,n-1}$.
 \end{proof}

\section{Graphs with $\sigma = 1$}\label{section: sigma equals one}

In this section we provide some evidence in order to make plausible Conjecture~\ref{conjecture:1}. We first verify Conjecture~\ref{conjecture:1} for graphs 
having disconnected complement; namely, we prove that the only graphs having $\sigma=1$ and disconnected complement are the stars (including the trivial star 
$K_1$). Then, we prove that Conjecture~\ref{conjecture:1} can be reduced to proving that the only connected and co-connected graph with $\sigma=1$ is $K_1$. We 
then verify Conjecture~\ref{conjecture:1} for cographs, forests, and split graphs.

\subsection{Reduction to co-connected graphs}

We first obtain a result which proves the validity of Conjecture~\ref{conjecture:1} for graphs having disconnected complement.

\begin{corollary}\label{theorem:disconnected complement}
Let $G$ be a graph on $n$ vertices such that $\overline{G}$ is disconnected. Then $\sigma(G) = 1$ if and only if $G = K_{1,n-1}$.
\end{corollary}

 \begin{proof}
  Assume first that $G = K_{1,n-1}$. Then $\d=2-\frac{2}{n}$.  If $n = 2$, the Laplacian eigenvalues of $G$ are $2$ and $0$. If $n\geq 3$, the Laplacian 
eigenvalues of $G$ are $n$, $1$ and 0, each with multiplicity $1$, $n-2$ and $1$, respectively.  In any case we have that $\sigma(G) = 1$.

The `only if' part follows from Corollary~\ref{corollary:co-connected}.
\end{proof}

As a consequence of Corollary~\ref{theorem:disconnected complement}, Conjecture~\ref{conjecture:1} is equivalent to the validity of the following weaker 
conjecture.

\begin{conjecture}\label{conjecture:2}
 Let $G$ be a graph with connected complement. Then, $\sigma(G)=1$ if and only if $G$ is isomorphic to $K_1$, $K_2+sK_1$ for some $s> 0$, or $K_{1,r}+sK_1$ for 
some $r\geq 2$ and $0< s<r-1$.
\end{conjecture}

\subsection{Reduction to connected and co-connected graphs}
 We next show that the validity of Conjectures~\ref{conjecture:1} and~\ref{conjecture:2} can be reduced to the validity of the following even weaker conjecture.

\begin{conjecture}\label{conjecture:3}
 Let $G$ be a connected graph with connected complement. Then, $\sigma(G)=1$ if and only if $G$ is isomorphic to $K_1$.
\end{conjecture}

A graph class $\mathcal G$ is \emph{closed by taking components} if every connected component of every graph in $\mathcal G$ also belongs to $\mathcal G$. In 
particular, the class of all graphs is closed by taking components. Below we prove that the reduction from Conjecture~\ref{conjecture:1} to 
Conjecture~\ref{conjecture:3} holds even when restricted to any graph class closed by
taking components.

\begin{theorem}\label{theorem:+}
 Let $\mathcal G$ be a graph class closed by taking components. If Conjecture~\ref{conjecture:3} holds for $\mathcal G$, then
Conjecture~\ref{conjecture:1} also holds for $\mathcal G$.
\end{theorem}

 \begin{proof}
 Let $G$ be a graph in $\mathcal G$ with $\sigma(G)=1$. Assume first that $G$ is connected. If $G$ is co-connected, by hypothesis, $G$ is isomorphic to $K_1$. 
If $G$ is not co-connected, then $G$ is isomorphic to $K_{1,r}$ for some $r\geq 1$,  by virtue of Corollary~\ref{theorem:disconnected complement}.

Assume now that $G$ is disconnected and let $G=G_1+G_2$, where each of $G_1$ and $G_2$ has at least one vertex. We can assume, without loss of generality, that 
$G_1$ is connected and $\mu_1(G_1)\geq\mu_1(G_2)$.  If $G_1$ were empty, then $G_2$ would also be empty, contradicting $\sigma(G)=1$. Hence we can assume, 
without loss of generality, that $G_1$ is nonempty.  Let $n_i$ and $m_i$ denote the number of vertices and edges of $G_i$, respectively, for each $i\in\{1,2\}$. 
Since $\sigma(G)=1$,
  \[
  \frac{2m_2}{n_2} \le \mu_1(G_2)<\overline d(G)=\frac{2(m_1+m_2)}{n_1+n_2}.
  \]
 This implies that 
 \begin{equation}\label{eq:mu7}
  \frac{2m_2}{n_2}<\frac{2m_1+2m_2}{n_1+n_2}<\frac{2m_1}{n_1}. 
 \end{equation}
 As a consequence of  \eqref{eq:mu7} we have that 
 \[
   \mu_2(G_1)<\frac{2m_1+2m_2}{n_1+n_2} < \frac{2m_1}{n_1} =\overline d(G_1).
 \]
We conclude that  $\sigma(G_1)=1$. Since $\mathcal G$ is closed by taking components, $G_1\in\mathcal G$. Thus, if $G_1$ were co-connected, then $G_1=K_1$, 
contradicting the assumption that $G_1$ is nonempty. Hence $G_1$ is not co-connected and, by 
Corollary~\ref{theorem:disconnected complement}, we have that   $G_1=K_{1,r}$ for some $r\geq 1$. 

From \eqref{eq:mu7} we deduce that 
 \[
  \mu_1(G_2)<\frac{2m_1+2m_2}{n_1+n_2}<\frac{2m_1}{n_1}=\frac{2r}{r+1}<2,
 \]
 and hence, by virtue of Theorem~\ref{thm: Brouwer and Haemers}, we conclude that $G_2$ must be empty. Then there exists an integer  $s\geq 1$ such that 
$G_2=sK_1$ and therefore it turns out that  $G= K_{1,r} + sK_1$. The average degree of $G$ is  $\overline d(G)=\frac{2r}{r+1+s}$.  
 If $r=1$, then $\sigma(G)=1$ because the second largest Laplacian eigenvalue of $G$ is $0$. If $r\geq 2$, then,  as the second largest eigenvalue of $G$ is $1$ 
it follows that $\sigma(G)=1$ if and only if $s<r-1$.
 \end{proof}
A \emph{cograph} is a graph with no induced $P_4$. It is well-known that the only connected and co-connected cograph is $K_1$~\cite{MR0337679}. Hence, 
Conjecture~\ref{conjecture:3} holds trivially for cographs and, by Theorem~\ref{theorem:+}, Conjecture~\ref{conjecture:1} holds for cographs.
\subsection{Characterizing forests and split graphs with $\sigma=1$}

In this section, we verify Conjecture~\ref{conjecture:1} for forests and split graphs.

A graph class $\mathcal G$ is \emph{monotone} if $G\in\mathcal{G}$ implies that every subgraph of $G$ also belongs to $\mathcal G$. Notice that every monotone 
graph class is closed by taking components. It can be easily seen that the class of all forests is monotone and thus it is closed by taking components.

\begin{theorem} Conjecture~\ref{conjecture:1} holds for forests.\end{theorem}
\begin{proof} Notice that if $T$ is a connected and co-connected forest, then $T$ is either $K_1$ or a tree with diameter greater than two. By virtue of 
Theorem~\ref{theorem:+}, it suffices to show that if $T$ is a tree with diameter greater than two, then $\sigma(T)\ge 2$. %
Assume that $T$ is a tree with diameter greater than two. Hence there exists two vertices $v_1$ and $v_2$ such that $d(v_1)\ge d(v_2) \ge 2 > 2-\frac{2}{n} = 
\overline d(T)$. By Theorem~\ref{thm: Brouwer and Haemers}, $\mu_2(T) \geq d_2(T) \geq 2 > \overline d(T)$. Therefore, $\sigma(T) \geq  2$.
\end{proof}

Let $\mathcal H$ be a set of graphs. We use the term \emph{$\mathcal H$-free} for referring to the family of those graphs having no graph in $\mathcal H$ as 
induced subgraph. If $\mathcal H$ has just one element $H$, we write $H$-free for simplicity. A \emph{split graph}~\cite{MR0505860} is a graph whose vertex set 
can be partitioned into a clique $C$ and a stable set $S$, such a partition $(C,S)$ of its vertices is called a \emph{split partition}. It is well known that 
the class of split graphs coincides with the class of $\{2K_2,C_4,C_5\}$-free graphs. %

\begin{theorem}\label{theorem:sigma1split}
     Conjecture~\ref{conjecture:1} holds for split graphs.
 \end{theorem}

 \begin{proof}
 Let $(C,S)$ be a split partition of the graph on $n$ vertices $G$ such that $\vert C\vert =c$ and $\vert S\vert =n-c$. We label the vertices of $G$ so that   
$C=\{v_1,\ldots,v_c\}$ and $S=\{v_{c+1},\ldots,v_n\}$.  We can assume, without loss of generality, that $C$ is a maximal clique of $G$ under inclusion and 
$d_i\ge d_{i+1}$, 
 for each   $ i \in \{1, \ldots,  n-1\}$. 
 
 We claim  that if $G$ is a split graph with $\sigma(G)=1$, then $G$ is isomorphic to $K_{1,r-1}+(n-r)K_1$ for some $r$ such that $2\leq r\leq n$.
 
 In order to prove our claim we assume  that $G$ is nonisomorphic to $K_{1,r-1}+(n-r)K_1$,  for each  $ r \in \{2, \ldots, n\}$ and we will 
 prove that $\sigma(G) \geq 2$. 
 By virtue of Theorem~\ref{thm: Brouwer and Haemers}, it suffices to prove that $d_2 \geq \d$ or equivalently that
 \[
  \sum_{i=3}^n(d_2-d_i)\geq d_1-d_2.
 \]
We will consider two cases. 
\begin{enumerate}
\item \emph{Assume that $d_2\ge c$}. Since $C$ is a maximal clique, $d_2-d_i\ge 1$ for each $i \in \{c+1, \ldots,  n\}$. Hence
 \[
  \sum_{i=3}^n(d_2-d_i)\ge \sum_{i=c+1}^n(d_2-d_i)\ge n-c\ge d_1-d_2.
 \]

\item \emph{Assume that $d_2=c-1$}. %
      Our assumption on $G$ implies that $c > 2$. Moreover, we have that  $d_i\le 1$ for each $i \in \{c+1, \ldots, n\}$. %
      Consequently, $d_2-d_i\ge 1$ for each such $i$ and the reasoning follows as above. 	
\end{enumerate}
 Thus we have proved our claim. 
 In particular, the only connected and co-connected split graph with $\sigma=1$ is $K_1$; i.e., Conjecture~\ref{conjecture:3} holds for split graphs. Therefore, 
by virtue of Theorem~\ref{theorem:+}, Conjecture~\ref{conjecture:1} holds for split graphs.
 \end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}

Authors would like to thank the anonymous referees for generous observations and comments that we have made ample use of in the paper. A.\ Cafure and E.\ 
Dratman acknowledge partial support of CONICET PIP 112-2013-010-0598. A.\ Cafure, E.\ Dratman, L.\ N. Grippo, and M.\ D.\ Safe acknowledge partial support of 
CONICET UNGS-144-20140100027-CO. L.\ N.\ Grippo and M.\ D.\ Safe acknowledge partial support of UNS Grant PGI 24/L103. L.\ E.\ Allem, M.\ D.\ Safe and V.\ 
Trevisan acknowledge partial support of MATH-AmSud 18-MATH-01. V.\ Trevisan acknowledges partial support of CNPq grants 409746/2016-9 and 
303334/2016-9 and FAPERGS (Proj.\ PqG 17/2551-0001).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% You do not have to use the same format for your references, but 
%    include everything in this file.  Don't use natbib please.
% If you use BibTeX to create a bibliography, copy the .bbl file into here.

\begin{thebibliography}{10}
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{\texttt{#1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi
\newcommand{\enquote}[1]{``#1''}

\bibitem{BrowerandHamers2008}
Brouwer, A.~E. and Haemers, W.~H., \emph{A lower bound for the {L}aplacian eigenvalues of a graph---proof of a conjecture by {G}uo}, Linear Algebra Appl. 
\textbf{429} (2008), pp.~2131--2135.

\bibitem{Das2015}
Das, K.~C., S.~A. Mojallal and I.~Gutman, \emph{On {L}aplacian energy in terms
  of graph invariants}, Appl. Math. Comput. \textbf{268} (2015), pp.~83--92.

\bibitem{Das16}
Das, K.~C., S.~A. Mojallal and V.~Trevisan, \emph{Distribution of {L}aplacian
  eigenvalues of graphs}, Linear Algebra Appl. \textbf{508} (2016), pp.~48--61.

\bibitem{MR0505860}
F\"{o}ldes, S. and P.~L. Hammer, \emph{Split graphs}, in: \emph{Proceedings of
  the {E}ighth {S}outheastern {C}onference on {C}ombinatorics, {G}raph {T}heory
  and {C}omputing ({L}ouisiana {S}tate {U}niv., {B}aton {R}ouge, {L}a., 1977)},
  Utilitas Math., Winnipeg, Man., 1977 pp. 311--315.

\bibitem{Gro90}
Grone, R. and R.~Merris, \emph{The {L}aplacian spectrum of a
  graph II}, SIAM J. Discrete Math. \textbf{7} (1994), pp.~221--229.

\bibitem{Guo2007}
Guo, J.-M., \emph{On the third largest {L}aplacian eigenvalue of a graph},
  Linear Multilinear Algebra \textbf{55} (2007), pp.~93--102.

\bibitem{MR1813439}
Li, J.-S. and Y.-L. Pan, \emph{A note on the second largest eigenvalue of the
  {L}aplacian matrix of a graph}, Linear and Multilinear Algebra \textbf{48}
  (2000), pp.~117--121.

\bibitem{MR1275613}
Merris, R., \emph{Laplacian matrices of graphs: a survey}, Linear Algebra Appl.
  \textbf{197/198} (1994), pp.~143--176.

\bibitem{Moh91}
Mohar, B., \emph{The {L}aplacian spectrum of graphs}, in: \emph{Graph theory,
  combinatorics, and applications. {V}ol.\ 2 ({K}alamazoo, {MI}, 1988)},
  Wiley-Intersci. Publ., Wiley, New York, 1991 pp. 871--898.

\bibitem{Moh92}
Mohar, B., \emph{Laplace eigenvalues of graphs---a survey}, Discrete Math.
  \textbf{109} (1992), pp.~171--183.

\bibitem{Pirzada2015}
Pirzada, S. and H.~A. Ganie, \emph{On the {L}aplacian eigenvalues of a graph
  and {L}aplacian energy}, Linear Algebra Appl. \textbf{486} (2015),
  pp.~454--468.

\bibitem{MR0337679}
Seinsche, D., \emph{On a property of the class of {$n$}-colorable graphs}, J. Combinatorial Theory Ser. B, \textbf{16} (1974), pp.~191--193.

\bibitem{west_introduction_2000}
West, D.~B., \enquote{Introduction to Graph Theory,} Prentice Hall, 2000, 2nd
  edition.

\end{thebibliography}

\end{document}