% 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
\newcommand{\lma}{\lambda_p}
\newcommand{\lmo}{\widehat{\lambda}^{(p)}}
\newcommand{\Sp}{S^{V}_p}
\newcommand{\pn}[1]{\left\lVert #1 \right \rVert_p}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\sg}[1]{\textnormal{sign}\left(#1\right)}
\newcommand{\clC}{{\cal C}}
\newcommand{\cut}{\textnormal{cut}}
\newcommand{\qinf}{q_\infty}

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

% Give the submission and acceptance dates in the format shown.
% The editors will insert the publication date in the third argument.
\dateline{Dec 16, 2016}{Mar 15, 2018}{TBD}

% Give one or more subject codes separated by commas.
% Codes are available from http://www.ams.org/mathscinet/freeTools.html
\MSC{05C50, 05C40, 15A18}

% 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{Eigenvalue bounds for the signless $p$-Laplacian}

% 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{Elizandro Max Borba\thanks{Supported by CAPES Grant PROBRAL 408/13 - Brazil.}\\
\small Instituto de Matem\'atica\\[-0.8ex]
\small Universidade Federal do Rio Grande do Sul\\[-0.8ex] 
\small CEP 91509-900, Porto Alegre, RS, Brazil\\
\small\tt elizandro.max@ufrgs.br\\
\and
Uwe Schwerdtfeger\thanks{Supported by DAAD PROBRAL Grant 56267227 - Germany.}\\
\small Fakult\"at f\"ur Mathematik\\[-0.8ex]
\small Technische Universit\"at Chemnitz\\[-0.8ex]
\small D-09107 Chemnitz, Germany\\
\small\tt uwe.schwerdtfeger@mathematik.tu-chemnitz.de}

\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}
We consider the signless $p$-Laplacian $Q_p$ of a graph, a generalisation of the quadratic form of the signless Laplacian matrix (the case $p=2$). In analogy to Rayleigh's principle the minimum and maximum of $Q_p$ on the $p$-norm unit sphere are called its smallest and largest eigenvalues, respectively. We show a Perron-Frobenius property and basic inequalites for the largest eigenvalue and provide upper and lower bounds for the smallest eigenvalue in terms of a graph parameter related to the bipartiteness. The latter result generalises bounds by Desai and Rao and, interestingly, at $p=1$ upper and lower bounds coincide.

\smallskip
\noindent
\textbf{Keywords:} signless Laplacian, signless p-Laplacian, eigenvalue bound
\end{abstract}

\section{Introduction}

We begin with some notation. All graphs are simple and undirected without loops or multiple edges. For a graph $G=(V,E)$ with vertex set $V$ the edge set $E$ consists of two-element subsets of $V$ and for each edge we write $ij$ rather than $\{i,j\}.$ For disjoint subsets $S,T\subseteq V$ define $E_G(S)$ as the edges $ij\in E$ spanned by $S,$ $E_G(S,T)$ the edges with one vertex in $S$ and the other in $T;$ we also define $n=|V|,$ $e_G(S)=|E_G(S)|,$ $e_G(S,T)=|E_G(S,T)|$ and $\cut_G(S)=|E_G(S,V\setminus S)|.$ Furthermore $d_i,i\in V$ is the degree of vertex $i$ and $\delta(G),\Delta(G)$ denote the minimum and maximum degree, respectively.  We shall drop the subscripts if $G$ is clear from the context. We find it convenient to index vectors and matrices associated with the graph by the vertex set $V$ and write therefore $x=(x_i,i\in V)\in \R^V$ rather than $x\in \R^n.$ Accordingly, we denote by $A\in\R^{V\times V}$ the adjacency matrix and by $D\in\R^{V\times V}$ the diagonal matrix 
of vertex degrees. %Similarly for $x\in \R^V$ we understand $x^\top$ as the functional $\R^V\to\R,$ $y\mapsto x^\top y=\sum_{i\in V}x_iy_i.$

The eigenvalues and eigenvectors of the Laplacian $L:=D-A$ are well studied, in particular the second smallest eigenvalue $a(G),$ the algebraic connectivity of $G.$ It is non-zero if and only if $G$ is connected and by a well-known inequality due to Mohar \cite{Mohar89} it can be upper and lower bounded in terms of the isoperimetric number of $G$
\[
 i(G):=\min\left\{\frac{\cut(S)}{|S|},\;S\subseteq V,\;0<|S|\le\frac{n}{2} \right\}.
\]
Eigenvectors for $a(G)$ are used in spectral partitioning. Following Amghibech's work \cite{Amghibech03} B\"uhler and Hein \cite{BuehlerHein09} introduced for $p>1$ a non-negative functional $L_p(x)=\sum_{ij\in E}|x_i-x_j|^p$ on $\R^V$ which for $p=2$ yields the quadratic form of $L.$ The $p$-Laplacian of $G$ is defined as the non-linear operator 
\[
\frac{1}{p}\nabla_x L_p\colon \R^V\to \R^V,\quad \frac{1}{p}\nabla_x L_p(x)_i= \sum_{j\colon ij\in E}\sg{x_i-x_j} |x_i-x_j|^{p-1}
\]
 where \[\sg{x}=\begin{cases}1 \text{ if }x>0,\\ -1\text{ if }x <0,\\ 0\text{ if }x =0.\end{cases}\]
A vector $x\neq 0$ is called an eigenvector of $L_p$ with corresponding eigenvalue $\mu\in\R$ if the eigenequations
\[
\frac{1}{p}\nabla_x L_p(x)_i=\sum_{j\colon ij\in E}\sg{x_i-x_j} |x_i-x_j|^{p-1}=\mu\sg{x_i}|x_i|^{p-1},\,i\in V,
\]
are satisfied. Observe that in this case $p^{-1}x^\top\nabla_x L_p(x)=L_p(x)=\mu \pn{x}^p$ and that the eigenequations are necessary conditions for the optimisation problems
\[
 \min\,(\text{resp. } \max) L_p(x) \text{ s.t. }\pn{x}^p=1
\]
which for $p=2$ are the Rayleigh-Ritz characterisations of the smallest (resp. largest) eigenvalue of $L.$ The minimum is always zero, attained by a non-zero multiple of the all ones vector ${\bf 1}$ and these are the only solutions if and only if $G$ is connected. Observing that ${\bf 1}^\top \nabla_x L_p(x)=0$ for any $x$ one is led to characterise the smallest non-zero eigenvalue $a_p(G)$ as
\begin{equation}\label{eq:ap}
 a_p(G)=\min L_p(x) \text{ s.t. }\pn{x}^p=1 \text{ and }\sum_{i\in V}\sg{x_i}|x_i|^{p-1}=0
\end{equation}
B\"uhler and Hein \cite{BuehlerHein09} give the following bounds 
\begin{equation}\label{eq:Cheeger}
 \left(\frac{2}{\Delta} \right)^{p-1}\left(\frac{i(G)}{p} \right)^{p}\le a_p(G) \le 2^{p-1}i(G),
\end{equation}
where $\Delta$ is the maximum degree.
Interestingly, in the limit $p\to 1$ upper and lower bounds coincide. Indeed, in \cite{Chang16} spectral properties of the 1-Laplacian are explored. The eigenequations are then a nonlinear system involving set valued functions (gradients are replaced by subdifferentials) and it is found that the smallest non-zero eigenvalue is in fact $i(G).$ 

Only recently the signless Laplacian matrix $Q=D+A$ has received greater interest from spectral graph theorists, nevertheless an early remarkable result \cite{DesRao94} dates back to 1994. The quadratic form of $Q$ is $x^\top Q x=\sum_{ij\in E}(x_i+x_j)^2$ and hence $Q$ is positive semidefinite. The smallest eigenvalue $q(G)$ is $0$ if and only if $G$ has a bipartite component, see Lemma~\ref{lem:qpeq0}. Informally speaking, the results in \cite{DesRao94} state that a small $q(G)$ indicates the existence of a nearly bipartite subgraph which is not very well connected to the rest of the graph, and vice versa. More precisely, in \cite{DesRao94} they define the graph parameter $\psi(G)$ as 
\begin{equation}\label{eq:psi}
 \psi(G):=\min\left\{\frac{2e(S)+2e(T)+\cut(S\cup T)}{|S\cup T|}\colon S,T\subseteq V,\;S\cap T=\emptyset,\;S\cup T\neq\emptyset    \right\}.
\end{equation}
and prove a lower and upper bound on $q(G)$ reminiscent of \eqref{eq:Cheeger} for $p=2,$ namely
\begin{equation}\label{eq:DesaiRao}
 \frac{\psi(G)^2}{2\Delta}\le q(G)\le 2 \psi(G).
\end{equation}
Observe that $\psi(G)=0$ if and only if $G$ has a bipartite component and, moreover, that for a minimising pair $S,T$ in \eqref{eq:psi} the number $e(S)+e(T)$ is the smallest number of edges to be removed from the induced subgraph on $S\cup T$ to make it bipartite. Thus the bounds in \eqref{eq:DesaiRao} quite well capture the informal statement.
We also remark that the definition of $\psi$ and also the bounds differ (superficially) from those in \cite{DesRao94}. We followed the exposition of \cite{FallatFan12} where bounds on $q(G)$ in terms of edge and vertex bipartiteness and a stronger lower bound in terms of $\psi(G)$ are established. Finding (near) bipartite substructures in graphs is of practical interest in the study of social networks and bioinformatics as pointed out in \cite{KirklandPaul11}, where the authors devise spectral techniques involving eigenvectors for $q(G)$ to obtain such structures.

In this article we consider for real $p\ge 1$ the non-negative convex functional 
\[
Q_p\colon \R^V\to \R,\quad Q_p(x)=\sum_{ij\in E}|x_i+x_j|^p
\] 
(i.e. $Q_2(x)=x^\top Qx$) and its extremal values on the $p$-norm unit sphere 
\[\Sp=\left\{x\in \R^V\colon \sum_{i\in V}|x_i|^p=1 \right\}
\] 
or, equivalently, extremal values of $R_p(x):=Q_p(x)/\pn{x}^p$ on $\R^V\setminus\{0\}.$ For $p=2$ this is the Rayleigh-Ritz characterisation of the smallest and largest eigenvalues.  Let 
\begin{equation}\label{eq:q}
q_p(G)= \min\left\{ Q_p(x) \colon \pn{x}^p=\sum_{i\in V}|x_i|^p=1 \right\}=\min\left\{ R_p(x) \colon x\neq 0 \right\}
\end{equation}
and in an analogous fashion define by $\lma(G)$ the maximum. We call $q_p(G)$ and $\lma(G)$ the smallest and largest eigenvalues of $Q_p,$ respectively and minimising (maximising) vectors eigenvectors. Our study of $q_p(G)$ is strongly motivated by the inequalities \eqref{eq:DesaiRao} and \eqref{eq:Cheeger} and our main result is an upper and lower bound on $q_p(G)$ in terms of the graph parameter $\psi(G).$
\begin{theorem}\label{theo:main} For $p\ge 1$ the smallest signless $p$-Laplacian eigenvalue $q_p(G)$ satisfies
\[
 \left(\frac{2}{\Delta} \right)^{p-1}\left(\frac{\psi(G)}{p} \right)^{p}\le q_p(G) \le 2^{p-1}\psi(G).
\]
In particular, we have that $q_1(G)=\psi(G).$ 
\end{theorem}
The proof of Theorem \ref{theo:main} provides actually a stronger lower bound and a method to obtain a ''good`` pair $(S,T)$ (in view of \eqref{eq:psi}) by thresholding a solution to the optimisation problem \eqref{eq:q}:
\begin{corollary}\label{coro:main}
For $x\in \R^V\setminus\{0\}$ and $t\ge 0$ define the vertex sets $S_{x}^t=\{i\in V\colon x_i>t\}$ and $T_{x}^t=\{i\in V\colon x_i<-t\}$ and define 
\begin{equation}\label{eq:psix}
\psi(G,x):=\min\left\{ \frac{2e_G\left(S_{x}^t\right)+2e_G\left(T_{x}^t\right)+\textnormal{cut}_G\left(S_{x}^t\cup T_{x}^t\right)}{\left|S_{x}^t\cup T_{x}^t\right|}\colon 0\le t< \max_{i\in V}\{|x_i|\} \right\}.
\end{equation}
If $p\ge 1$ and $x^{(p)}$ is an eigenvector for $q_p(G)$ then the bounds in Theorem~\ref{theo:main} also hold with $\psi(G)$ replaced by $\psi(G,x^{(p)}).$ In particular, $\psi(G,x^{(p)})\to\psi(G)$ as $p\to 1$ and for $p=1,$ $\psi(G)=\psi(G,x^{(1)}).$  
\end{corollary}

For practical matters as raised in \cite{KirklandPaul11} it would be interesting to know if the computation or approximamtion of $q_p(G)$ and a corresponding eigenvector can be carried out efficiently. We are currently investigating this. 

\noindent
{\bf Outline.} In the next section we provide a proof of Theorem~\ref{theo:main} and Corollary~\ref{coro:main}. In the subsequent section we discuss the case $p=\infty$ and in the final section some basic properties of the largest eigenvalue. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proof of Theorem \ref{theo:main}}

In this section we assume throughout that $p\ge 1$. First we shall see that Theorem \ref{theo:main} is trivially true for graphs with a bipartite connected component:
\begin{lemma}\label{lem:qpeq0}
 The smallest eigenvalue $q_p(G)$ is zero if and only if $G$ has a bipartite component.
\end{lemma}
\begin{proof}
 If there is a bipartite component with partition $S\cup T$ put $x_i=1,$ if $i\in S,$ $x_i=-1,$ if $i\in T$ and $x_i=0$ elsewhere. Then $Q_p(x)=0.$ Conversely, $Q_p(x)=0$ implies $x_i=-x_j$ for every $ij\in E$ and thus a connected component containing a vertex $i$ with $x_i\neq 0$ is bipartite.
\end{proof}
The next lemma (\cite{DesRao94,FallatFan12} for $p=2$) yields the upper bound in Theorem \ref{theo:main}.
\begin{lemma}\label{lem:upperbound}
Let $S,T\subseteq V,$ $S\cap T=\emptyset.$ Then we have
 \[
  q_p(G)|S\cup T|\le 2^p e(S)+ 2^p e(T) +\cut(S\cup T)
 \]
and in particular $q_p(G)\le 2^{p-1}\psi(G).$
\end{lemma}
\begin{proof}
Let $S\cup T\neq\emptyset,$ otherwise the assertion is trivial. Define $x$ by $x_i=1,$ if $i\in S,$ $x_i=-1,$ if $i\in T$ and $x_i=0$ elsewhere. Then a computation shows
\[
q_p(G)\le \frac{Q_p(x)}{\pn{x}^p}=\frac{2^p e(S)+ 2^p e(T) +\cut(S\cup T)}{|S\cup T|}.
\]
If $S,T$ are chosen as optimal sets in the definition \eqref{eq:psi} of $\psi(G)$ this last expression is $\le 2^{p-1}\psi(G)$ with equality only if $\cut(S\cup T)=0$ or $p=1.$
\end{proof}
%This section completes the proof of Theorem \ref{theo:main}.
 
For the proof of the lower bound we combine techniques from \cite{DesRao94} and \cite{BuehlerHein09}. For a graph $G^\prime=(V^\prime,E^\prime)$ fix a subset $U\subseteq V^\prime.$ % and define 
% \[
% h(U)=\min \left\{\frac{\cut(W)}{|W|}\colon W\subseteq U,\;W\neq\emptyset   \right\}.
% \]
For a vector $g\in \R^{V^\prime}$ with $g_i>0$ on $U$ and $g_i=0$ elsewhere define $C^t_g=\{ i\in U\colon g_i>t \}$ and
\begin{equation}\label{eq:defhg}
 h_g(U):=\min \left\{\frac{\cut_{G^\prime}\left(C^t_g\right)}{\left|C^t_g\right|}\colon 0\le t < \max\{g_i,i\in U\} \right\}.
\end{equation}
%Clearly, $h_g(S)\ge h(S).$ 
We have the following lemma.
\begin{lemma}\label{lem:est} With the above notation we have 
 \begin{equation}
  \left(\frac{2}{\Delta(G^\prime)} \right)^{p-1}\left(\frac{h_g(U)}{p} \right)^{p}\pn{g}^p\le\sum_{ij\in E^\prime}|g_i-g_j|^p
 \end{equation}
where $\Delta(G^\prime)$ is the maximum degree of $G^\prime.$ 
\end{lemma}
We postpone the proof of the lemma and first apply it to prove Theorem~\ref{theo:main}. The idea is from \cite{DesRao94}, however, at some places we must be a bit more careful to get a lower bound which, as $p\to 1,$ coincides with the upper bound. 
\begin{proof}[Proof of Theorem \ref{theo:main}, lower bound]
 Consider a connected graph $G=(V,E)$ and its signless $p$-Laplacian $Q_p.$ Let $x$ be a normalised eigenvector ($\pn{x}=1$) for the smallest eigenvalue $q_p=q_p(G)$ such that $Q_p(x)=q_p.$ Define $S=\{i\in V\colon x_i>0 \}$ and $T=\{i\in V\colon x_i<0 \}$ and a graph $G^\prime =(V^\prime,E^\prime)$ as follows. Let $V^\prime=V\dot\cup S^\prime \dot\cup T^\prime$ where $S^\prime=\{i^\prime\colon i\in S\}$ and $T^\prime=\{i^\prime\colon i\in T\}$ are disjoint copies of $S$ and $T,$ respectively, and define
\[
 E^\prime=E_G(S,T)\cup E_G(S\cup T, V\setminus (S\cup T))\cup\{i^\prime j, ij^\prime\colon ij\in E_G(S)\} \cup\{i^\prime j, ij^\prime\colon ij\in E_G(T)\}
\]
i.e. $E^\prime$ is obtained from $E$ by deleting every edge $ij$ with both endpoints in $S$ (resp. $T$) and adding two edges $ij^\prime$ and $i^\prime j.$
Define $g\in\R^{V^\prime}$ by $g_i=|x_i|$ if $i\in S\cup T$ and $g_i=0$ if $i\in V^\prime\setminus (S\cup T).$ Then we have $\pn{g}=\pn{x}=1$ and
\begin{equation}\label{eq:gx}
\sum_{ij\in E^\prime}|g_i-g_j|^p\le \sum_{ij\in E}|x_i+x_j|^p=q_p.
\end{equation}
To see this, first consider an edge $ij\in E_G(S)\cup E_G(T)$ on the right hand side. We have two corresponding edges in $i^\prime j ,ij^\prime\in E^\prime$ on the left side and 
\[
|g_{i^\prime}-g_j|^p+|g_i-g_{j^\prime}|^p=|g_j|^p+|g_i|^p\le ||x_i|+|x_j||^p=|x_i+x_j|^p
\]
because $x_i$ and $x_j$ have the same sign. The remaining summands on both sides correspond to edges $ij\in E\cap E^\prime.$ A case by case inspection yields $|g_i-g_j|^p=|x_i+x_j|^p$ and \eqref{eq:gx} follows.\footnote{Inequality \eqref{eq:gx} is sharper than the original \cite[inequality (23)]{DesRao94} where there is a factor 2 on the right hand side which can be omitted. This was also pointed out in \cite{FallatFan12}.}

%Observe that $\Delta(G^\prime)=\Delta(G)$ so it remains
Now we show $h_g(S\cup T)\ge\psi(G).$ To that end consider an optimal $t\ge 0$ in the definition \eqref{eq:defhg} of $h_g(S\cup T)$ and a corresponding cut set $C^t_g\subseteq S\cup T.$ Define $S^t=C^t_g\cap S$ and $T^t=C^t_g\cap T.$ Recall the vertex sets $S_x^t$ and $T_x^t$ of $G$ and the parameter $\psi(G,x)$ defined in Corollary~\ref{coro:main} and observe that actually $S^t=S_x^t$ and $T^t=T_x^t$ (viewed as vertex subsets of $G$) by the definitions of $g$ and $C^t_g.$ 
Therefore, in $G,$ we have a chain of inequalities
\begin{equation}\label{eq:left}
\frac{ 2e_G(S^t)+2e_G(T^t)+\cut_G(S^t\cup T^t)}{ |S^t\cup T^t|}\ge\psi(G,x)\ge\psi(G).
\end{equation}
On the other hand we observe that  
\begin{equation}\label{eq:cutpsix}
2e_G(S^t)+2e_G(T^t)+\cut_G(S^t\cup T^t)=\cut_{G^\prime}(S^t\cup T^t)
\end{equation} 
because every edge $ij\in E_G(S^t)\cup E_G(T^t)$ corresponds to two edges counted in $\cut_{G^\prime}(S^t\cup T^t),$ namely $ij^\prime$ and $i^\prime j.$ Moreover, every edge in $E_G(S^t\cup T^t,V\setminus (S^t\cup T^t))$ contributes exactly one edge counted in $\cut_{G^\prime}(S^t\cup T^t):$ for example, an edge $ij\in E$ in $G$ with $i\in S^t$ and $j\in S\setminus S^t$ is accounted for in $\cut_{G^\prime}(S^t\cup T^t)$ by the edge $ij^\prime\in E^\prime$ but not by the edge $i^\prime j\in E^\prime(V^\prime\setminus (S^t\cup T^t)).$ 

Now \eqref{eq:left}, \eqref{eq:cutpsix} and the optimality of $C^t_g=S^t\cup T^t$ for \eqref{eq:defhg} imply 
\begin{equation}\label{eq:hgpsi}
h_g(S\cup T)\ge \psi(G,x)\ge \psi(G). 
\end{equation}
Combine Lemma \ref{lem:est} (applied to $G^\prime$ with $U=S\cup T$) with \eqref{eq:gx} and \eqref{eq:hgpsi} and observe that $\Delta(G^\prime)=\Delta(G)$ to complete the proof of Corollary~\ref{coro:main} and Theorem~\ref{theo:main}.% Finally observe that $S^t,T^t$ are precisely the sets $S_x^t,T_x^t$ in Corollary \ref{coro:main} and we have actually proven a sharper lower bound with $\psi(G)$ replaced by $\psi(x).$ 
\end{proof}


We now prove Lemma~\ref{lem:est}, where we follow \cite{BuehlerHein09} up to minor modifications.
\begin{proof}[Proof of Lemma \ref{lem:est}] We first show
\begin{equation}\label{eq:sumgeh}
h_g(U)\pn{g}^p\le \sum_{ij\in E^\prime}|g_i^p-g_j^p| .
\end{equation}
To that end write
\[
\begin{split}
 \sum_{ij\in E^\prime,g_i>g_j}(g_i^p-g_j^p)=\sum_{ij\in E^\prime,g_i>g_j}p\int_{g_j}^{g_i}t^{p-1}dt=p\int_0^\infty t^{p-1}\sum_{ij\in E^\prime\colon g_i>t\ge g_j}1dt
\end{split}
 \]
and observe that $\sum_{ij\in E^\prime\colon g_i>t\ge g_j}1=|\{ij\in E^\prime\colon i\in C^t_g, j\notin C^t_g\}|=\cut(C^t_g).$ By the definition of $h_g(U)$ we have 
\[
\cut(C^t_g)\ge h_g(U) |C^t_g|=h_g(U)\sum_{i\in V^\prime\colon g_i>t}1.
\]
Hence we can give a lower bound
\[\begin{split}
 \sum_{ij\in E^\prime,g_i>g_j}(g_i^p-g_j^p)&=p\int_0^\infty t^{p-1}\sum_{ij\in E^\prime\colon g_i>t\ge g_j}1dt\\ &\ge p\int_0^\infty t^{p-1}h_g(U)\sum_{i\in V^\prime\colon g_i>t}1 dt\\ &=h_g(U)\sum_{i\in V^\prime\colon g_i>0}\int_0^{g_i}pt^{p-1}dt\\ &=h_g(U)\sum_{i\in V^\prime\colon g_i>0}g_i^p\\ &=h_g(U)\pn{g}^p
\end{split}\]
and obtain \eqref{eq:sumgeh}. Observe that this completes the proof of the lemma if $p=1.$ 

\noindent
For $p>1$ we proceed with H\"older's inequality $\sum |x_iy_i|\le (\sum |x_i^p|)^{1/p}(\sum |y_i^q|)^{1/q}$ where $q=p/(p-1).$ 
\begin{equation}\label{eq:hoelder}
\begin{split}
 \sum_{ij\in E^\prime}|g_i^p-g_j^p|&=\sum_{ij\in E^\prime}|g_i-g_j|\frac{g_i^p-g_j^p}{g_i-g_j}\\%\le\sum_{ij\in E^\prime}\sum_{ij\in E^\prime}
&\le \left(\sum_{ij\in E^\prime}|g_i-g_j|^p\right )^{1/p} \left(\sum_{ij\in E^\prime}\left(\frac{g_i^p-g_j^p}{g_i-g_j}\right)^q\right )^{1/q}
\end{split}
\end{equation}
In order to bound the last term from above we use an inequality from \cite{Amghibech03} (an alternative proof is given at the end of this section) which states that
\begin{equation}\label{eq:amghineq}
 \left(\frac{g_i^p-g_j^p}{g_i-g_j}\right)^{q}\le p^{q}\left(\frac{g_i^p+g_j^p}{2}\right).
\end{equation}
The second factor in the last term of \eqref{eq:hoelder} can thus be bounded from above by (with $d_i^\prime$ the degree of vertex $i$ in $G^\prime$)
\begin{equation*}\begin{split}
 \left(\sum_{ij\in E^\prime}\left(\frac{g_i^p-g_j^p}{g_i-g_j}\right)^q\right )^{1/q}\le p\left(\sum_{ij\in E^\prime}\frac{g_i^p+g_j^p}{2}\right )^{1/q}
=\frac{p}{2^{1/q}}\left(\sum_{i\in V^\prime}d_i^\prime g_i^p\right )^{1/q}\\ \le \frac{p}{2^{1/q}}\left(\Delta(G^\prime)\pn{g}^p \right )^{1/q}=p\left( \frac{\Delta(G^\prime)}{2}\right)^{(p-1)/p}\pn{g}^{p-1}
\end{split}
\end{equation*}
Substitute this last term into \eqref{eq:hoelder} combine with \eqref{eq:sumgeh} and regroup terms to obtain the assertion of the Lemma.

For a self-contained exposition we show inequality \eqref{eq:amghineq}. Recall the power mean inequality: for $x_1,\ldots,x_n>0$ and $r<s$ we have $\left(\frac{1}{n}\sum_{k=1}^n x_k^r \right)^{1/r}\le\left(\frac{1}{n}\sum_{k=1}^n x_k^s \right)^{1/s}.$ Using Riemann sum approximations we obtain for $0\le a<b$ a continuous version 
\[\begin{split}
&\left(\frac{1}{b-a}\int_{a}^{b}t^{r}dt\right)^{1/r}= \lim_{n\to\infty}\left(\sum_{k=1}^n \frac{1}{n} \left(a+k\cdot \frac{b-a}{n} \right)^{r}\right)^{1/r}\\ &\le \lim_{n\to\infty}\left(\sum_{k=1}^n \frac{1}{n} \left(a+k\cdot \frac{b-a}{n} \right)^{s}\right)^{1/s}=\left(\frac{1}{b-a}\int_{a}^{b}t^{s}dt\right)^{1/s}
\end{split}
\]
An application of this to \eqref{eq:amghineq} yields (assuming $g_i>g_j$)
\[\begin{split}
 \left(\frac{g_i^p-g_j^p}{g_i-g_j}\right)^{q}&=p^{q}\left(\frac{1}{g_i-g_j}\int_{g_j}^{g_i}t^{p-1}dt\right)^{p/(p-1)}\\
&\le p^{q}\frac{1}{g_i-g_j}\int_{g_j}^{g_i}t^{p}dt\le p^{q}\left(\frac{g_i^p+g_j^p}{2}\right)
\end{split}
\]
where the last ``$\le$'' follows from the convexity of $t^p$ for $p\ge 1:$ in the interval $g_j\le t\le g_i$ we have $t^p\le s(t):=g_j^p+\frac{g_i^p-g_j^p}{g_i-g_j}(t-g_j)$ and the last inequality is obtained upon replacing $t^p$ by $s(t)$ in the integral.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The case $p=\infty$}

If we equivalently minimise $Q_p(x)^{1/p}$ in \eqref{eq:q} the case $p=\infty$ is also meaningful with
\[
\qinf(G)=\min_{\lVert x\rVert_{\infty}=1}\max_{ij\in E}|x_i+x_j|.
\]
Lemma~\ref{lem:qpeq0} holds accordingly, that is, $\qinf$ is zero if and only if $G$ has a bipartite component. 
\begin{theorem}
 For $u\in V$ let $l(u)$ be the smallest odd integer $2k+1$ ($k\in \N$) such that there exists a closed walk $ui_1,i_1i_2,\ldots,i_{2k-1}i_{2k},i_{2k}u$ in $G$ starting and ending in $u$ and let $l(u)=\infty$ if no such walk exists (i.e. $u$ lies in a bipartite component of $G$). Then we have (with the convention $1/\infty =0$) 
\[
 \qinf(G)=\frac{2}{\max_{u\in V}l(u)}.
\]
\end{theorem}
\begin{proof}
We assume that $G$ does not have a bipartite component because otherwise the assertion is true. Observe that
\[
\qinf= \min_{u\in V} p_u
\]
where $p_u$ is the optimal value of the linear program
\begin{equation*}
\min_{ \genfrac{}{}{0pt}{}{ \lVert x\rVert_{\infty}=1 }{ x_u=1 } }\max_{ij\in E}|x_i+x_j|=\textnormal{minimise }\mu \textnormal{ s.t. }\begin{cases}
                                               -\mu\le x_i+x_j\le \mu &(ij\in E),\\
-1\le x_i\le 1&(i\in V\setminus\{u\}),\\
x_u=1. &
                                              \end{cases}
\end{equation*}
Since $p_u>0$ for an optimal solution we can assume $\mu>0$ and divide the constraints by $\mu,$ introduce new variables $y_i=x_i/\mu$ and obtain an equivalent program whose optimum is $1/p_u.$
\begin{equation}\label{eq:lp}
\textnormal{maximise }y_u \textnormal{ s.t. }\begin{cases}
                                               -1\le y_i+y_j\le 1 &(ij\in E)\\
-y_u\le y_i\le y_u&(i\in V\setminus\{u\})\\
                                              \end{cases}
\end{equation}
Consider a closed walk $ui_1,i_1i_2,\ldots,i_{2k-1}i_{2k},i_{2k}u$ of odd length $2k+1$ in $G$ and sum up the corresponding inequalities in an alternating fashion to obtain
\[
 -2k-1\le y_u+y_{i_1}-y_{i_1}-y_{i_2}+y_{i_2}+y_{i_3}-\ldots -y_{i_{2k-1}}-y_{i_{2k}}+y_{i_{2k}}+y_u\le 2k+1,
\]
in particular we have $y_u\le l(u)/2.$ We show that this inequality can be attained with equality. For $v,w\in V$ let $d(v,w)$ be the usual graph distance (length of shortest $v$-$w$ path) and let $S_i=\{v\in V\colon d(u,v)=i \},$  $i\ge 0,$ be the $i$-th level in a breadth first search tree rooted at $u.$ Recall that a vertex in $S_{i+1}$ has a neighbour in $S_i$ and that any edge in $E$ has either both endpoints in the same level or connects two consecutive levels. Now $l(u)=2k_0+1$ where $k_0$ is the smallest integer such that $S_{k_0}$ contains two vertices $v\neq w$ with $vw\in E.$ We define a feasible vector $y$ by
\[
 y_v=\begin{cases}
      (-1)^i\left(k_0-i+\frac{1}{2}  \right) \textnormal{ if }v\in S_i\textnormal{ and }i\le k_0,\\
0,\textnormal{ otherwise},
     \end{cases}
\]
in particular $y_u=l(u)/2.$ This $y$ is feasible: for an edge $vw$ we have $|y_v+y_w|\in \{0,1/2,1\}$ if $v\in S_i$ and $w\in S_{i+1}$ for some $i\ge 0,$  $|y_v+y_w|=1$ if $v,w\in S_{k_0}$ and $|y_v+y_w|=0$ if $v,w\in S_{i},$ $i>k_0.$
\end{proof}

\noindent
\textbf{Remark.} 
Following the formulation of problem \eqref{eq:ap} in \cite{BuehlerHein09} one also has $p=\infty$ version which reads
\begin{equation}\label{eq:ainf}
 a_\infty(G)=\min \max_{ij\in E}|x_i-x_j| \text{ s.t. }\lVert x\rVert_\infty=1 \text{ and }\max_{i\in V} x_i+\min_{i\in V}x_i=0.
\end{equation}
The optimum value is $2/\text{diam}(G)$ where $\text{diam}(G)=\max\{d(s,t)\colon s,t\in V\}$ is the diameter of $G.$ Similarly as for $\qinf,$ one has to solve for every \emph{pair} of vertices $s\neq t$ a linear program
\begin{equation*}
\textnormal{minimise }\mu \textnormal{ s.t. }\begin{cases}
                                               -\mu\le x_i-x_j\le \mu & (ij\in E),\\
-1\le x_i\le 1 & (i\in V),\\
\left.\begin{array}{l}
  x_t=1, \\
 x_s=-1,%\hspace{2cm}
 \end{array}\right\}  \hspace{0.3cm}\Leftrightarrow  &%\hspace{0.25cm}
\left\{\begin{array}{l}
  x_t+x_s=0, \\
 x_t-x_s=2,
 \end{array}\right.                                            \end{cases}
\end{equation*}
which is equivalent to 
\[
 \textnormal{maximise }\frac{1}{2}(y_t-y_s)\textnormal{ s.t. }\begin{cases}
                                               -1\le y_i-y_j\le 1 &(ij\in E),\\
-y_t\le y_i\le y_t&(i\in V),\\
y_s+y_t=0,
                                              \end{cases}
\]
and whose optimum can be shown to be half the length of a shortest $s$-$t$ path.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Basic properties of the largest eigenvalue}

For $p>1$ a necessary condition for an $x\in \Sp$ to yield the minimum (resp. maximum) in \eqref{eq:q} is the existence of a Lagrange multiplier $\mu$ such that the \emph{eigenequations} 
\begin{equation}\label{eq:eig}
\frac{1}{p} \nabla_x Q_p(x)_i=\sum_{j\colon ij\in E}\sg{x_i+x_j} |x_i+x_j|^{p-1}=\mu \,\sg{x_i}|x_i|^{p-1},\,i\in V,
\end{equation}
are satisfied. If a pair $(x,\mu)\in (\R^V\setminus\{0\})\times \R$ satisfies \eqref{eq:eig} we call $x$ an eigenvector and $\mu$ an eigenvalue of $Q_p.$ Then \eqref{eq:eig} implies $p^{-1}x^\top\nabla_x Q_p(x)=Q_p(x)=\mu \pn{x}^p$ and hence eigenvalues are non-negative and $q_p(G)$ and $\lma(G)$ are the smallest, resp. largest eigenvalues.

We first observe that $q_p(G)$ and $\lambda_p(G)$ do not increase when passing to subgraphs.
\begin{lemma}\label{lem:subgraph}
 Let $H$ be a subgraph of $G.$ Then $q_p(H)\le q_p(G)$ and $\lambda_p(H)\le\lambda_p(G).$ 
\end{lemma}
\begin{proof}
Since adding isolated vertices does not affect $\lma(H)$ we assume that $H=(V,F)$ with $F\subseteq E.$
Let $x\in \Sp$ be a normalised eigenvector for $\lambda_p(H),$ then
\[
\lambda_p(H)=\sum_{ij\in F}|x_i+x_j|^p\le \sum_{ij\in E}|x_i+x_j|^p\le \lambda_p(G). 
\]
The proof for $q_p$ is similar, starting with an eigenvector for $q_p(G).$
\end{proof}
The standard basis of $\R^V$ yields easy bounds for $q_p(G)$ and $\lma(G)$ in terms of the maximum and minimum degrees.
\begin{lemma}\label{lem:ei}
We have for $p\ge 1$
\[
 q_p(G)\le \delta(G) \text{ and }\lma(G)\ge \Delta(G)
\]
($\delta(G),\Delta(G)$ the minimum/maximum degree). If $p>1$ equality holds in the former if and only if $G$ has an isolated vertex and equality in the latter if and only if $G$ has no edges. 

The standard basis vector $e_i$ ($i\in V$) of $\R^V$ is an eigenvector of $Q_p$ if and only if $d_i=0,$ that is $i$ is an isolated vertex.
\end{lemma}
\begin{proof}
By definition, $q_p(G)\le Q_p(e_i)=d_i\le\lma(G).$ If equality holds in either of the two then $e_i$ is an eigenvector for the eigenvalue $d_i.$ If $d_i>0$ then $i$ has a neighbour $j$ and the $j$-th eigenequation (see \eqref{eq:eig}) reads $1=d_i\cdot 0,$ and so $d_i=0.$
\end{proof}
If $G$ is a connected graph then the signless Laplacian matrix $Q$ is a non-negative, irreducible, aperiodic matrix. By the Perron-Frobenius Theorem its largest eigenvalue is simple and a corresponding eigenvector has only strictly positive or only stricly negative components. The next theorem shows that this property is shared by eigenvectors corresponding to $\lma(G).$
\begin{theorem}
 Let $p>1,$ $G$ be connected and $x\in \Sp$ be an eigenvector for $\lma(G).$ Then $x$ has only stricly positive or only strictly negative components and is unique up to sign.
\end{theorem}
\begin{proof}
Denote by $C^+, C^-$ and $C^0$ the vertex sets on which $x_i$ is $>0$, $<0$ and $=0,$ respectively, and assume without loss of generality that $C^+\neq\emptyset,$ otherwise consider $-x.$ Define $u=(|x_i|,i\in V)\in\Sp$ and
observe that $|x_i+x_j|\le ||x_i|+|x_j||=|u_i+u_j|$ with equality if and only if $x_i$ and $x_j$ have the same sign or at least one of them is $0.$
Thus $E(C^+,C^-)=\emptyset$ and $u$ is another eigenvector for $\lma$ because otherwise we had a contradiction $\lma=Q_p(x)< Q_p(u)\le\lma.$ Since $G$ is connected there is an edge $ab$ with $a\in C^+$ and $b\in C^0.$ The $b$-th eigenequation (see \eqref{eq:eig}) for the eigenpair $(u,\lma)$ then yields a contradiction
\[
0<|u_a+u_b|^{p-1} \le\sum_{j\colon bj\in E} |u_b+u_j|^{p-1}=\lma \,\sg{u_b}|u_b|^{p-1}=0.
\]
So $C^0$ must be empty. Because $G$ is connected and $E(C^+,C^-)=\emptyset$ it follows that also $C^-$ is empty and $C^+=V.$

As for the uniqueness assume that $x,y\in\Sp$ are both stricly positive eigenvectors and define $z\in \Sp$ by 
\[
 z_i=\left(\frac{x_i^p+y_i^p}{2}\right)^{1/p},\,i\in V.
\]
The triangle inequality for the $p$-norm (Minkowski's inequality) yields 
\begin{equation}\label{eq:unique}
\begin{split}
 (x_i+x_j)^p+(y_i+y_j)^p&=\pn{\left( \begin{array}{c}
				  x_i \\y_i
                               \end{array}\right )
 +\left( \begin{array}{c}
				  x_j \\y_j
                               \end{array}\right )
 }^p\\
&\le \left( \pn{\left( \begin{array}{c}
				  x_i \\y_i
                               \end{array}\right )}
 +\pn{\left( \begin{array}{c}
				  x_j \\y_j
                               \end{array}\right )
 }  \right)^p\\
&=\left(\left(x_i^p+y_i^p\right)^{1/p}+\left(x_j^p+y_j^p\right)^{1/p}\right)^p\\
&=2(z_i+z_j)^p
\end{split}
\end{equation}
and thus $2\lma=Q_p(x)+Q_p(y)\le 2Q_p(z)\le 2\lma$ and equality must hold in \eqref{eq:unique} for every edge $ij\in E.$ Since the $p$-norm for $p>1$ is strictly convex $(x_i,y_i)$ must be a positive multiple of $(x_j,y_j)$ whenever $ij\in E.$ Therefore, by connectedness of $G,$ the rank of $(x,y)$ is one and hence $x=y.$  
 \end{proof}

\noindent
\textbf{Remark:} The theorem is false for $p=1.$ The unit ball is the convex hull of $\{\pm e_i,i\in V\}$ and so by the convexity of $Q_1$ we have that $\lambda_1=\max_{i\in V}Q_1(e_i)=\Delta,$ the maximum degree of $G.$ The solution is neither strictly positive nor is it unique, unless the maximum degree vertex is unique.

\smallskip
 
With the positive eigenvector at hand we can prove upper and lower bounds on $\lma(G)$ in terms of vertex degrees.
\begin{lemma}\label{lem:degreebound}
 Let $p>1,$ $G=(V,E)$ be connected with maximum vertex degree $\Delta$ and minimum degree $\delta.$ Then
\[
 2^{p-1}\delta\le 2^{p-1}\frac{2|E|}{|V|}\le \lma(G)\le2^{p-1}\Delta
\]
with equality in either place if and only if $G$ is regular. In particular, the all ones vector is an eigenvector if and only if $G$ is regular.
\end{lemma}
\begin{proof}
The first ''$\le$`` is trivially true because the minimum degree is less than or equal to the average degree with equality only for regular graphs. For the second inequality observe that for the all ones vector $\bf{1}$ we have 
\[
 \lma(G)\ge\frac{Q_p(\bf{1})}{\pn{\bf{1}}^p}=\frac{2^p|E|}{n}
\]
with equality if and only if $\bf{1}$ is an eigenvector for $\lma(G).$ More generally, if $\bf{1}$ is an eigenvector for some eigenvalue $\mu$ then the eigenequations read $2^{p-1}d_i=\mu,i\in V$ (see \eqref{eq:eig}). Thus $G$ is regular and $\mu=2^{p-1}\Delta\le \lma.$ 

 For the last inequality let $x$ be the positive eigenvector for $\lma$ and assume w.l.o.g. $x_1\ge x_2\ge\ldots \ge x_n>0.$ The first eigenequation reads
\[
 \lma x_1^{p-1}=\sum_{j\colon 1j\in E} |x_1+x_j|^{p-1}\le 2^{p-1}x_1^{p-1} d_1\le 2^{p-1}\Delta x_1^{p-1}.
\]
If equality holds then $d_1=\Delta$ and $x_a=x_1$ for every neighbour $a$ of $1.$ Then the eigenequation for $a$ yields $2^{p-1}\Delta x_a^{p-1}\le 2^{p-1}x_a^{p-1} d_a$ and so $d_a=\Delta$ and $x_b=x_a$ for any neighbour $b$ of $a.$ Continuing in this ``breadth first search'' fashion shows that $G$ is regular and $x_1=x_2=\ldots =x_n.$ %The limit statement holds because of Lemma \ref{lem:ei}.
\end{proof}
\noindent
\textbf{Remark:} For $p=1$ the upper bound is always attained and equality holds in the lower bounds if and only if $G$ is regular. 

A better upper bound is the following (cf. \cite{Amghibech06}).
\begin{lemma}
 Let $p>1,$ $q=p/(p-1)$ and $G$ be connected. Then
\[
 \lma(G)\le 2^{p-1}\max_{ij\in E} \left(\frac{d_i^q+d_j^q}{2}   \right)^{1/q}
\] with equality if and only if $G$ is regular.
\end{lemma}
\begin{proof}
 Let $x$ be a positive eigenvector for $\lma$ and choose an edge $ij$ such that $x_i+x_j$ is maximal. The $i$-th eigenequation yields the estimate 
\begin{equation}\label{eq:lx}
 \lma x_i^{p-1}=\sum_{k\colon ik\in E}(x_i+x_k)^{p-1}\le d_i(x_i+x_j)^{p-1}.
\end{equation}
Take the $q$-th power on both sides and use the convexity of $t\mapsto t^p$ to obtain
\begin{equation}\label{eq:lqxp}
 \lma^q x_i^{p}\le d_i^q(x_i+x_j)^{p}\le 2^{p-1}d_i^q(x_i^p+x_j^p).
\end{equation}
The same computation for $i$ replaced by $j$ yields $\lma^q x_j^{p}\le 2^{p-1}d_j^q(x_i^p+x_j^p)$ and adding up the two yields
\[
 \lma^q (x_i^p+x_j^{p})\le 2^{p}\frac{d_i^q+d_j^q}{2}(x_i^p+x_j^p)
\]
and hence the bound. If the bound and thus \eqref{eq:lqxp} hold with equality then $x_i=x_j$ by the strict convexity of $t\mapsto t^p$ and therefore $d_i=d_j.$ From \eqref{eq:lx} we get $x_k=x_j=x_i$ for every $k$ with $ik\in E$ and we can argue similarly as in the proof of Lemma~\ref{lem:degreebound} that $G$ is regular.
\end{proof}


Before we generalise some more known inequalities involving the chromatic number we make some remarks on odd cycles and complete graphs.
\begin{lemma}\label{lem:Cn}
 Let $C_n=(V=\{1,\ldots,n\}, E=\{12,23,\ldots,(n-1) n,n1\})$ be the cycle on $n$ vertices. The largest eigenvalue is $\lma(C_n)=2^p.$ For the smallest eigenvalue we have $q_p(C_n)<1$ if $n\ge 4,$ and $q_p(C_3)\le 1$ with equality if and only if $p=2.$
\end{lemma}
\begin{proof}
By the regularity of $C_n$ Lemma~\ref{lem:degreebound} implies $\lma(C_n)=2^p.$ The assertion on $q_p$ is trivially true for even $n$ because then $C_n$ is bipartite and thus $q_p=0$ by Lemma~\ref{lem:qpeq0}. Therefore assume that $n$ is odd. Lemma~\ref{lem:upperbound} with $S=\{1,3,\ldots,n-2\}$ and $T=\{2,4,\ldots,n-1\}$ yields $q_p(C_n)\le 2/(n-1)$ which is $<1$ if $n\ge 5.$ For $n=3$ consider the vector $x=(2,-1,-1).$ We have $Q_p(x)/\pn{x}=1.$ If $q_p=1$ then the pair $(x,1)$ must satisfy the eigenequations \eqref{eq:eig}; the one for the vertex 2 reads $(2-1)^{p-1}-|-1-1|^{p-1}=-1.$ This is satisfied if and only if $p=2.$
\end{proof}


\begin{lemma}\label{lem:Kn}
 Let $n\ge 2$ and $K_n$ be the complete graph on the vertex set $\{1,\ldots,n\}.$  
\begin{enumerate}
 \item $\lma(K_n)=2^{p-1}(n-1).$
 \item With $\psi(G)$ defined as in \eqref{eq:psi} we have $\psi(K_n)=\begin{cases}
                   \frac{n-2}{2},\textnormal{ if } n \textnormal{ is even,}\\
\frac{n-1}{2},\textnormal{ if } n \textnormal{ is odd.}\\
                  \end{cases}$
\item The number $\nu_p(n):= \begin{cases}
                   2^{p-2}(n-2),\textnormal{ if } n \textnormal{ is even,}\\
2^{p-2}(n-3)+1,\textnormal{ if } n \textnormal{ is odd}\\
                  \end{cases}$ is an eigenvalue, in particular we have $q_p(K_n)\le \nu_p(n).$ 

\item For the smallest eigenvalue $q_p(K_n)$ we have the upper bound \begin{equation}\label{eq:Kn}
q_p(K_n)\le \mu_p(n):=(n-2)\frac{(n-2)^{p-1}+2^{p-1}}{(n-1)^{p-1}+1}.
\end{equation}
Equality holds for $n=2.$ If $p=2$ equality holds for any $n\ge 3.$ If $p<2$ the inequality is strict for every $n\ge 3.$ If $p>2$ the inequality is strict for $n\in\{3,4\}$ and $n\ge 7.$ If $n\in \{5,6\}$ there is at most one $p=p(n)>2$ for which equality can hold ($p(5)\approx 3.3618,$ $p(6) \approx 2.3490$).  
\item $q_p(K_n)\le n-2$ with equality if and only if $p=2.$
\end{enumerate}
\end{lemma}
\begin{proof}
1. This is Lemma~\ref{lem:degreebound} because $K_n$ is regular.

\noindent
2 and 3. Let the vertex set of $K_n$ be denoted by $\{1,\ldots,n\}$ and let $k=\lfloor n/2\rfloor.$ Observe that if $|S\cup T|$ in \eqref{eq:psi} is fixed then $2e(S)+2e(T)=|S|(|S|-1)+|T|(|T|-1)$ is minimum for pairs $(S,T)$ with $||S|-|T||\le 1.$ Checking all pairs $(S,T),$ $S\cap T=\emptyset,$ with $|S|=m$ and $|T|\in \{m,m+1\}$ and $m\le k$ it turns out that all pairs with $|S|=k=|T|$ are optimal. For assertion 3 consider such a pair $(S,T),$ and the vector $x\in \R^V$ with $x_i=1$ if $i\in S,$ $x_i=-1$ if $i\in T,$ and $x_i=0$ otherwise and observe that the pair $(x,\nu_p(n))$ satisfies the eigenequations \eqref{eq:eig} for $K_n.$

\noindent
4. First observe that $e_i-e_j,i\ne j,$ is an eigenvector of $Q_p$ with eigenvalue $\mu=n-2,$ regardless of the value of $p,$ and for $p=2$ we see by a dimension argument that the only eigenvalues are $q_2(K_n)=n-2$ and $\lambda_2(K_n)=2n-2,$ the latter afforded by ${\bf 1}.$  

By evaluating $\frac{Q_p(x)}{\pn{x}^p}$ at the vector $x=(n-1,-1,\ldots,-1)^\top$ we find that $\mu_p(n)=\frac{Q_p(x)}{\pn{x}^p}\ge q_p(K_n)$ and hence the bound \eqref{eq:Kn}. Equality holds for $p=2$ because $\mu_2(n)=n-2,$ and also for $n=2$ because $K_2$ is bipartite and therefore $q_p(K_n)=0=\mu_p(2).$ For $n=3$ we have $\mu_p(3)=1>q_p(C_3)=q_p(K_3)$ unless $p=2$ by Lemma~\ref{lem:Cn}.
So from now on we can assume that $n\ge 4.$ For equality to hold in \eqref{eq:Kn} it is necessary that the eigenequations \eqref{eq:eig} are satisfied for $x$ and $\lambda=\mu_p(n)=q_p(K_n).$ They read in this case
\begin{equation}\label{eq:eigKn}
 \begin{split}
  (n-1)(n-2)^{p-1}&=\lambda (n-1)^{p-1},\\
(n-2)^{p-1}-(n-2)2^{p-1}&=-\lambda.
 \end{split}
\end{equation}
From the first equation it follows that 
\begin{equation}\label{eq:lambda}
\lambda=(n-2)\left(\frac{n-2}{n-1}\right)^{p-2}.
\end{equation}
If $p<2$ it follows on the one hand that $q_p(K_n)=\lambda>n-2.$ On the other hand $\nu_p(n)$ from item~3 is an eigenvalue with $\nu_p(n)<n-2$ if $n\ge 4$ which is a contradiction. So $\mu_p(n)=q_p(K_n)$ cannot hold for $p<2.$ 

For $p>2$ we substitute \eqref{eq:lambda} into the second equation of \eqref{eq:eigKn} to obtain the equation
\[
 0=1+\left(\frac{1}{n-1}\right)^{p-2}-2\left(\frac{2}{n-2}\right)^{p-2}=:f(p).
\]
If $f(p)\neq 0$ then the eigenequations cannot hold and consequently \eqref{eq:Kn} is strict.
Clearly, $f(2)=0.$ For $n=4$ we see directly that $f(p)<0$ if $p>2.$ So let $n\ge 5$ and observe that $\lim_{p\to\infty}f(p)=1.$ The derivative of $f$ with respect to $p$ is
\[
 f^\prime(p)=\log\left(\frac{(n-2)^2}{4} \right)\left(\frac{2}{n-2}\right)^{p-2}-\log(n-1)\left(\frac{1}{n-1}\right)^{p-2}.
\]
If $n\ge 7$ then $2/(n-2)>1/(n-1)$ and $(n-2)^2/4>n-1$ and therefore we have $f^\prime(p)>0$ on the intervall $[2,\infty)$ and $f(p)>0$ on $(2,\infty).$ If $n\in\{5,6\}$ observe that $f^\prime(2)<0$ and that there is a unique $r>2$ such that $f^\prime(r)=0.$ Consequently, $f(r)<0$ and there is a unique $s=s(n)>r$ with $f(s)=0.$ In this case $x$ is an eigenvector of $Q_s$ and the equality $q_s(K_n)=\mu_s(n)$ could possibly hold.        

\noindent
5. We have already seen that the assertion is true if $n=3$ and that for $n\ge 4$ we have $\nu_p(n)<n-2$ if $p<2.$ It remains to show that $q_p(K_n)<n-2$ if $p>2.$ We show that $\mu_p(n)<n-2$ or, equivalently,  
\begin{equation}\label{eq:convineq}
  \frac{(n-2)^{p-1}+2^{p-1}}{(n-1)^{p-1}+1}<1
\end{equation}
To that end observe that the function $t\mapsto f(t)=|t|^{p-1}$ is strictly convex if $p>2$ and that
we can write $2=(1-\lambda)1+\lambda\frac{n}{2}$ and $n-2=(1-\lambda)(n-1)+\lambda\frac{n}{2}$ with $\lambda=2/(n-2).$ 
More generally let $f$ be strictly convex, $a<b$ and $c=(1-\lambda) a+\lambda \frac{a+b}{2}$ and $d=(1-\lambda) b+\lambda \frac{a+b}{2}$ with $0<\lambda\le 1.$ Then we have $f(c)+f(d) \le (1-\lambda)(f(a)+f(b))+2\lambda f\left( \frac{a+b}{2}\right)$ and hence
\[
\frac{f(c)+f(d)}{f(a)+f(b)} \le(1-\lambda)+ \lambda \frac{2f\left( \frac{a+b}{2}\right)}{f(a)+f(b)} <(1-\lambda)+\lambda =1.
\]
This yields \eqref{eq:convineq}.
\end{proof}

The following eigenvalue inequalities are simple generalisations of known ones in the case $p=2.$ The proofs carry over almost verbatim and we refer to the original sources. Wilf's bound is originally for the adjacency matrix $A$ and true for $Q$ by the relation $\lambda_2(G)\ge 2\mu$ where $\mu$ denotes the largest eigenvalue of $A$. The proof is not long so we decided to include it here.
\begin{proposition}
 Let $G=(V,E)$ be connected, $n=|V|,$ $m=|E|$ and $\chi=\chi(G)$ be the chromatic number.
\begin{enumerate}
 \item $2^{p-1}(\chi-1)\le \lma(G)$ with equality if and only if $G$ is complete or an odd cycle (Wilf's bound \cite{Wilf67}).
\item $q_p(G)\le \frac{2m}{n}\cdot \frac{\chi-2}{\chi-1} \cdot \frac{(\chi-2)^{p-1}+2^{p-1}}{(\chi-1)^{p-1}+1}.$ If $p=2$ and $G$ is complete then equality holds \cite[Theorem 2.11]{LOAN11}. 
\item $\lma(G)-q_p(G)\ge 2^{p-1}(\chi-1)-(\chi-2)\frac{(\chi-2)^{p-1}+2^{p-1}}{(\chi-1)^{p-1}+1}.$ If $p=2$ and $G=K_\chi$ equality holds. Conversely, if equality holds for some $p>1$ then $G=K_\chi$ is a complete graph. If $p<2$ equality is impossible; likewise if $p>2$ and $\chi\notin \{5,6\}.$ If $\chi \in \{5,6\}$ equality can hold for at most one $p>2.$  \cite[Corollary 2.12]{LOAN11}.
\item Denote by $\nu(G)$ the vertex bipartiteness of $G,$ i.e. the minimum cardinality of a set $W\subseteq V$ such that $G[V\setminus W]$ is bipartite. Then $q_p(G)\le \nu(G).$ \cite[Theorem 2.1]{FallatFan12}
\end{enumerate}
\end{proposition}
\begin{proof}
 1. Remove vertices from $G$ to obtain a $\chi-$critical subgraph $H=(V(H),E(H))$ (i.e. $\chi(H)=\chi$ and $H-i$ is $\chi-1$-colourable for every $i\in V(H)$). Then $H$ is connected and the minimum degree $\delta(H)$ is at least $\chi-1.$ So by Lemmas \ref{lem:degreebound} and \ref{lem:subgraph} we have the desired bound:
\[
 2^{p-1}(\chi-1)\le 2^{p-1}\delta(H)\le \lma(H)\le \lma(G).
\]
If equality holds in item 1 then $\lma(H)=\lma(G)$ and, again by Lemma \ref{lem:degreebound}, $H$ is $(\chi-1)$-regular and the all ones vector ${\bf 1}\in\R^{V(H)}$ is an eigenvector for $\lma(H).$ We show that $V(H)=V.$ Define $x\in\R^V$ by $x_i=1$ if $i\in V(H)$ and $x_i=0$ otherwise. Then, in $G$ we get
\[
\lma(G)\ge\frac{Q_p(x)}{\pn{x}^p}=\frac{2^p|E(H)|+\cut_G(V(H))}{|V(H)|}=\lma(H)+\frac{\cut_G(V(H))}{|V(H)|}\ge \lma(G)
\]
and so $\cut_G(V(H))=0.$ Connectedness of $G$ implies $V=V(H)$ and thus $G$ is a $\chi$-chromatic, $\chi-1$-regular graph. So $G$ is a complete graph or an odd cycle by the theorem of Brooks \cite{Brooks41} which states that $\chi(G)\le \Delta(G)$ unless $G$ is complete or an odd cycle.  

\noindent
2. The second assertion is \eqref{eq:Kn} with $p=2.$ The bound is shown as in \cite[Theorem 2.11]{LOAN11}. Let $V_1,\ldots,V_\chi$ be the colour classes. For each class $V_k$ define a vector $x^{(k)}$ as 
\[
x^{(k)}_i=\begin{cases}\chi-1,\textnormal{ if }i\in V_k\\ -1\textnormal{ otherwise,}\end{cases}\quad k=1,\ldots,\chi.
\]
Evaluate both sides of the inequality $q_p\pn{x^{(k)}}^p\le Q_p(x^{(k)})$ to get
\[\begin{split}
 q_p ((\chi-1)^p|V_k|+n-|V_k|)&\le e(V_k,V\setminus V_k)(\chi-2)^p+e(V\setminus V_k)2^p\\&= e(V_k,V\setminus V_k)((\chi-2)^p-2^p)+2^pm
\end{split}
\]
where for the second equality we used that $V_k$ is an independent set, i.e. $e(V_k)=0.$
Summation of these inequalities over $k=1,\ldots,\chi$ gives
\[
 q_p ((\chi-1)^pn+\chi n-n)\le 2m ((\chi-2)^p-2^p)+2^p\chi m
\]
and thus item 2 after some rearrangements.

\noindent
3. Here we slightly deviate from \cite{LOAN11} but get the same result for $p=2.$ With item~2 we have
\[\begin{split}
 \lma-q_p&\stackrel{\textnormal{item 2}}{\ge} \lma -\frac{2m}{n}\cdot \frac{\chi-2}{\chi-1} \cdot \frac{(\chi-2)^{p-1}+2^{p-1}}{(\chi-1)^{p-1}+1}\\
&\stackrel{\textnormal{Lem. }\ref{lem:degreebound}}{\ge} \lma-\frac{\lma}{2^{p-1}}\cdot \frac{\chi-2}{\chi-1} \cdot \frac{(\chi-2)^{p-1}+2^{p-1}}{(\chi-1)^{p-1}+1}\\
&\stackrel{\textnormal{item 1}}{\ge}2^{p-1}(\chi-1)-(\chi-2)\frac{(\chi-2)^{p-1}+2^{p-1}}{(\chi-1)^{p-1}+1}.
\end{split}
\]
If equality holds in the last step then $G$ is the complete graph $K_n$ or an odd cycle $C_n$ by item~1. If $G=C_n,$ $n\ge 5,$ then the first inequality is strict because the bound in item~2 for an odd cycle reads $q_p(C_n)\le 1$ and actually $q_p(C_n)< 1$ by Lemma~\ref{lem:Cn}. Therefore $G=K_\chi$ and item~2 yields precisely the bound \eqref{eq:Kn} in Lemma~\ref{lem:Kn}. This shows the remaining statements.

\noindent
4. Let $W$ be a vertex set with $|W|=\nu(G)$ such that $G[V\setminus W]$ is bipartite and let $S\cup T=V\setminus W$ be a corresponding bipartition. The assertion follows from Lemma~\ref{lem:upperbound} because $e(S)=e(T)=0$ and therefore
\[
 q_p\le\frac{\cut(S\cup T)}{|S\cup T|}=\frac{\cut(V\setminus W)}{|V\setminus W||W|}|W|\le |W|=\nu(G).
\]
\end{proof}

\noindent
\textbf{Remark:} In the limit $p\to 1$ item 1 becomes Brooks' Theorem. With $\psi=\psi(G)$ defined in \eqref{eq:psi} items 2--4 become  $\psi\le \frac{2m}{n}\cdot \frac{\chi-2}{\chi-1},$ $\psi\le \Delta -1$ and $\psi\le \nu,$ respectively.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
This work was partially supported by CAPES Grant PROBRAL 408/13 - Brazil
and DAAD PROBRAL Grant 56267227 - Germany. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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}{99}

\bibitem{Amghibech03}
S. Amghibech,\newblock Eigenvalues of the discrete $p$-Laplacian for graphs, \newblock \emph{Ars Combinatoria} \textbf{67} (2003), 283--302.

\bibitem{Amghibech06}
S. Amghibech,\newblock Bounds for the largest $p$-Laplacian eigenvalue for graphs,\newblock \emph{Discrete Mathematics} \textbf{306} (2006), 2762--2771.
 
\bibitem{Brooks41}
R. L. Brooks,\newblock On coloring the nodes of a network,\newblock \emph{Proc. Cambridge Phil. Soc.} \textbf{37} (1941), 194--197.

\bibitem{BuehlerHein09}
T. B\"uhler, M. Hein,\newblock Spectral Clustering based on the graph $p$-Laplacian,\newblock in L. Bottou and M. Littman (editors) \emph{Proceedings of the 26th International Conference on Machine Learning (ICML 2009)}, Omnipress (2009), 81--88.

\bibitem{Chang16}
K.C. Chang,\newblock Spectrum of the 1-Laplacian and Cheeger's Constant on Graphs,\newblock\emph{Journal of Graph Theory} \textbf{81} (2) (2016), 167--207.


\bibitem{DesRao94}
M. Desai, V. Rao,\newblock A characterization of the smallest eigenvalue of a graph,\newblock \emph{Journal of Graph Theory} \textbf{18} (1994), 181--194.

\bibitem{FallatFan12} 
S. Fallat, Y. Fan,\newblock Bipartiteness and the least eigenvalue of signless Laplacian
of graphs,\newblock \emph{Linear Algebra and its Applications} \textbf{436} (2012), 3254--3267.

\bibitem{KirklandPaul11} 
S. Kirkland, D. Paul,\newblock Bipartite subgraphs and the signless Laplacian matrix,\newblock \emph{Applicable Analysis and Discrete Mathematics} \textbf{5} (2011), 1--13.

\bibitem{LOAN11}
L.S. de Lima, C.S. Oliveira, N.M.M. de Abreu, V. Nikiforov,\newblock The smallest eigenvalue of the signless Laplacian,\newblock \emph{Linear Algebra and its Applications} \textbf{435} (2011), 2570--2584.

\bibitem{Mohar89}
B. Mohar,\newblock Isoperimetric number of graphs,\newblock \emph{Journal of Combinatorial Theory Ser. B.} \textbf{47} (1989), 274--291.

\bibitem{Wilf67}
H.S. Wilf,\newblock The eigenvalues of a graph and its chromatic number,\newblock \emph{J. London Math. Soc.} \textbf{42} (1967) 330--332.


\end{thebibliography}

\end{document}
