% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P56}{20(3)}{2013}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,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}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins

\usepackage{amsfonts}
\usepackage{url}
%\usepackage{verbatim}
%\usepackage[mathlines]{lineno}




% matrix macros
\def\noi{\noindent}
\def\mtx#1{\begin{bmatrix} #1 \end{bmatrix}}
\def\Cnt#1#2{\operatorname{Circ}_{#1}\langle1,\dots,#2\rangle}
\newcommand{\range}{\operatorname{range}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\A}{\mathcal{A}} % cal A for adjacency matrix

% graph macros
\def\ord#1{| #1 |} 
\def\wh#1{\widehat{#1}} 
%\newcommand{\wh}{}


% fields
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
%\newcommand{\Rnn}{\R^{n\times n}} 
\newcommand{\Rnn}{S_{n}(\R)} 
\newcommand{\Rn}{\R^{n}} 
\newcommand{\sRn}{\R^{(n)}}
\newcommand{\Znn}{\Z^{n\times n}} 
\newcommand{\Zn}{\Z^{n}} 
\newcommand{\Fnn}{F^{n\times n}} 
\newcommand{\Fmn}{F^{m\times n}} 
\newcommand{\Fn}{F^{n}} 

% bold vectors
\newcommand{\bx}{{\bf x}}
\newcommand{\bv}{{\bf v}}
\newcommand{\bw}{{\bf w}}
\newcommand{\bu}{{\bf u}}

\newcommand{\veps}{\varepsilon}


% min rank macros
\newcommand{\G}{\mathcal{G}}
\newcommand{\SG}{\mathcal{S}(G)}
\newcommand{\SH}{\mathcal{S}(H)}
\newcommand{\SGvH}{\mathcal{S}(G \vee H)}
\newcommand{\SGh}{\mathcal{S}(\wh G)}
\newcommand{\SGp}{\mathcal{S}_+(G)}
\newcommand{\mr}{\operatorname{mr}}
\newcommand{\mrp}{\operatorname{mr}_+}
\newcommand{\M}{\operatorname{M}}
\newcommand{\Mp}{\operatorname{M}_+}
\newcommand{\mrn}{\operatorname{mr}_\nu}
\newcommand{\jmrn}{\operatorname{jmr}_\nu}
\newcommand{\jmrp}{\operatorname{jmr}_+}
\newcommand{\ZFS}{\operatorname{Z}}
\newcommand{\Zp}{\operatorname{Z}_+}
\newcommand{\Zh}{\wh{\operatorname{Z}}}
\newcommand{\Zl}{\operatorname{Z}_\ell}
\newcommand{\Zt}{\widetilde{\operatorname{Z}}}
\newcommand{\tw}{\operatorname{tw}}
\newcommand{\cc}{\operatorname{cc}}
\newcommand{\Ob}{\operatorname{Forb}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\PC}{\mathcal{P}}
%\newcommand{\mrmm}\lfloor \operatorname{mr}\rfloor}
%\newcommand{\mrpmm}{\operatorname{mr}_+\rfloor}
\newcommand{\Mmm}{\lfloor \operatorname{M}\rfloor}
\newcommand{\Mpmm}{\lfloor \operatorname{M}_+\rfloor}
\newcommand{\Zmm}{\lfloor \operatorname{Z}\rfloor}
%\newcommand{\Zpmm}{\lfloor \operatorname{Z}_+\rfloor}
\newcommand{\Zhmm}{\lfloor \Zh \rfloor}
\newcommand{\Zpmm}{\lfloor \Zp\rfloor}
\newcommand{\Zlmm}{\lfloor \Zl\rfloor}
\newcommand{\pmm}{\lfloor p\rfloor}
\newcommand{\pcmm}{\lceil p \rceil}
\newcommand{\mrmm}{\lceil \mr\rceil}
\newcommand{\dmm}{\lceil \delta\rceil}
\newcommand{\kmm}{\lceil \kappa\rceil}
\newcommand{\h}{\operatorname{h}}
\newcommand{\bnu}{b_\nu}
\newcommand{\bmu}{b_\mu}
\newcommand{\bxi}{b_\xi}
\newcommand{\bh}{b_{\h}}
\newcommand{\bd}{b_{\lceil \delta\rceil}}
\newcommand{\bk}{b_{\lceil \kappa\rceil}}
\newcommand{\GCC}{$\operatorname{GCC}$}
\newcommand{\GCCp}{$\operatorname{GCC}_+$}
\newcommand{\GCCnu}{$\operatorname{GCC}_\nu$}
\newcommand{\GCCxi}{$\operatorname{GCC}_\xi$}
\newcommand{\cprod}{\mathbin{\scriptscriptstyle\square}}
\newcommand{\Gb}{\breve{G}}
\newcommand{\Go}{\ddot{G}}
\newcommand{\Mb}{\breve{M}}
\newcommand{\jmr}{\operatorname{jmr}}
\newcommand{\jgap}{\operatorname{jgap}}
\newcommand{\gap}{\mathrm{gap}_\nu}
\newcommand{\VG}{G=\bigvee_{i=1}^r G_i}
\newcommand{\Gcb}{\breve{\overline{G}}}
\newcommand{\Gbc}{\overline{\breve{G}}}
\newcommand{\Gc}{\overline{G}}
\newcommand{\Hac}{\overline{H(a)}}
\newcommand{\Ham}{\widehat{H(a)}}
\newcommand{\Uk}{\operatorname{U}_\kappa^{\mathbin{\scriptscriptstyle NG}}}


% theorems etc
\newtheorem{thm}{Theorem}[section]
\newtheorem{defn}[thm]{Definition}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{remark}[thm]{Remark}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{ex}[thm]{Example}
\newtheorem{quest}[thm]{Question}
\newtheorem{obs}[thm]{Observation}
\newtheorem{alg}[thm]{Algorithm}
\newtheorem{rem}[thm]{Remark}

% misc
\newcommand{\dotcup}{\dot{\cup}} % disjoint union symbol
\newcommand{\n}{\{1,\dots,n \}}
\newcommand{\x}{\times}
\newcommand{\wt}{\widetilde}
\newcommand{\sage}{{\em Sage}}
\newcommand{\bit}{\begin{itemize}}
\newcommand{\eit}{\end{itemize}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
\newcommand{\bpf}{\begin{proof}}
\newcommand{\epf}{\end{proof}\ms}
\newcommand{\ms}{\medskip}
\newcommand{\noin}{\noindent}

\title{\bf Note on Nordhaus-Gaddum problems for \\Colin de Verdi\`ere type parameters\thanks{This research began  at University of Regina.  The authors thank U. Regina and NSERC for their support.}}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Wayne Barrett\\
\small Department of Mathematics\\[-0.8ex]
\small Brigham Young University\\[-0.8ex] 
\small Provo, UT, USA\\
\small\tt wayne@math.byu.edu\\
\and
Shaun M. Fallat\thanks{Research supported in part by an
NSERC research grant.} \\
\small Department of Mathematics and Statistics\\[-0.8ex]
\small University of Regina, \\[-0.8ex]
\small Regina, SK, Canada\\
\small\tt sfallat@math.uregina.ca\\
\and
H. Tracy Hall \\
\small Department of Mathematics\\[-0.8ex]
\small Brigham Young University\\[-0.8ex] 
\small Provo, UT, USA\\
\small\tt H.Tracy@gmail.com\\
\and Leslie Hogben \\
\small Department of Mathematics\\[-0.8ex]
\small Iowa State University\\[-0.8ex] 
\small Ames, IA, USA\\
\small American Institute of Mathematics\\[-0.8ex] 
\small Palo Alto, CA, USA\\
\small\tt LHogben@iastate.edu, hogben@aimath.org
}

 % \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Jul 19, 2012}{Sep 24, 2013}{Oct 7, 2013}\\
\small Mathematics Subject Classifications: 05C50, 05C40,  05C83, 15A03, 15B57}



\begin{document}
%\linenumbers
\maketitle
%\begin{center}\today\end{center}


\begin{abstract}
We establish the bounds 
$\frac 4 3 \le b_\nu \le b_\xi\le \sqrt 2$, where $b_\nu$ and $b_\xi$ are  the Nordhaus-Gaddum sum upper bound multipliers, i.e., 
$\nu(G)+\nu(\Gc)\le b_\nu\ord G$ and $\xi(G)+\xi(\Gc)\le b_\xi\ord G$
for all graphs $G$, and $\nu$ and $\xi$ are Colin de Verdi\`ere type graph parameters.
The Nordhaus-Gaddum sum lower bound for $\nu$ and $\xi$ is conjectured to be $\ord G - 2$, and if these parameters are replaced by the maximum nullity $\M(G)$, this bound is called the Graph Complement Conjecture in the study of minimum rank/maximum nullity problems.  

  \bigskip\noindent \textbf{Keywords:} Nordhaus-Gaddum; Colin de Verdi\`ere type parameter; Graph Complement Conjecture; maximum nullity; minimum rank;  graph complement
\end{abstract}


% {\bf Keywords.}  Nordhaus-Gaddum, Colin de Verdi\`ere type parameter, Graph Complement Conjecture, maximum nullity, minimum rank,  graph complement.
%\ms

%{\bf AMS subject classifications.}  05C50, 05C40,  05C83, 15A03, 15B57





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

\section{Introduction}\label{sintro}  Nordhaus-Gaddum problems have been studied for many different graph parameters, including chromatic
number, independence number, domination number, Hadwiger number, etc. (see, for example, %\cite{AAC} or 
\cite{CN71}  and the references therein).  In this note we discuss the Nordhaus-Gaddum sum upper bounds for the Colin de Verdi\`ere type parameters $\nu$, $ \xi$, and $\mu$. The Graph Complement Conjecture in the study of minimum rank/maximum nullity problems is a conjectured lower bound for  related Nordhaus-Gaddum problems.  %These parameters are defined as the maximum nullity of matrices described by a  graph $G$ and satisfying the Strong Arnold Hypothesis and some additional conditions described below. 

All graphs in this paper are simple, undirected, and finite.  The {\em complement} of a graph $G=(V,E)$ is the 
graph $\overline{G}=(V,\overline{E})$, where $\overline{E}$
consists of all possible edges between vertices in $V$ that are not in $E$.
Let $G$  be a graph  with vertices $\{1,\dots,n\}$ and let $S_n$ denote the set of symmetric $n \times n$ real matrices.
For $A=[a_{ij}]\in S_n$, the {\em graph} of $A$, denoted by $\G(A)$, is the  
graph with vertices
$\{1,\dots,n \}$  and edges $\{ ij : a_{ij} \ne 0 \mbox{ and } i
\ne j \}$.
  The {\em set of symmetric matrices associated with} $G$ is $\SG = \{ A \in S_n: \G(A) = G \}$.   
The {\em maximum nullity of $G$} is
$\M(G)=\max\{\nul A: A\in \SG\},$
and the {\em maximum positive semidefinite nullity of $G$} is 
$\Mp(G)=\max\{\nul A: A\in \SG\mbox{ and } A \mbox{ is positive semidefinite}\}$.

 In \cite{CdVmu} and   \cite{CdVnu}, Colin de Verdi\`ere
introduced the parameters $\mu(G)$ and $\nu(G)$, defined to be the maximum nullity
among  matrices $A\in\SG$ that satisfy the Strong Arnold Hypothesis and additional conditions. In \cite{BFH3} the parameter $\xi(G)$ was defined to be the  maximum nullity
among  matrices $A\in\SG$ that satisfy the Strong Arnold Hypothesis.
A real symmetric matrix $A$ satisfies the {\em Strong Arnold
Hypothesis} provided there does {not} exist a nonzero real symmetric matrix
$X$ satisfying
$AX = 0$,
 $A\circ X = 0$, and
 $I\circ X=0$,
where $\circ$ denotes the Hadamard (entry-wise) product and $I$ is the identity matrix.
The Strong Arnold Hypothesis is equivalent to the requirement that certain manifolds intersect transversally (see \cite{HLS}). For $\nu$, the only additional condition (besides the Strong Arnold Hypothesis) is that the matrix must be positive semidefinite.  For $\mu$, the additional conditions %(besides the Strong Arnold Hypothesis) 
are that the matrix must be a generalized Laplacian (i.e., have nonpositive off-diagonal entries) and have exactly one negative eigenvalue.  Clearly $\nu(G)\le\Mp(G)\le\M(G)$, $\nu(G)\le\xi(G)\le\M(G)$, and $\mu(G)\le\xi(G)$, and each of  these inequalities can be strict (see \cite{param}).

An important property of Colin de Verdi\`ere type parameters is minor monotonicity.  The {\em contraction} of edge $e=uv$ of  $G$ is obtained by identifying the vertices $u$ and $v$, deleting any loops  that arise in this process, and replacing any multiple edges by a single edge.
 A {\em minor}
of $G$ arises by performing a  sequence of deletions of edges, deletions of isolated
vertices, and/or contractions of edges.  The notation $H\preceq G$ means that $H$ is a minor of $G$. %, and  $H\prec G$ means that $H$ is a {\em proper minor} of $G$, i.e., $H \preceq G$ and $H\ne G$.
 A graph parameter $\beta$ is {\em minor monotone} if for any minor $H$  of $G$, $\beta(H) \le \beta(G)$.  In \cite{CdVmu}, \cite{CdVnu}, and \cite{BFH3} (respectively) it is shown that $\mu$, $\nu$, and $\xi$ are  minor monotone. %, and in  it is shown that $\xi$ is minor monotone.  

 For any
graph $G$,  the {\em Hadwiger number} $\h(G)$ is the maximum order of  a clique minor of $G$. 
It was shown in \cite{CdVmu} and \cite{CdVnu} that $\mu(K_n)=n-1$ and
$\nu(K_n)=n-1$ (where $K_n$ denotes the complete graph on $n$ vertices), so by minor monotonicity $\h(G)-1\le \mu(G)$ and $\h(G)-1\le \nu(G)$.  

  Let $\kappa(G)$ denote the {\em vertex connectivity of $G$}, i.e., if $G$ is not complete, the smallest number $k$ such that there is a set of vertices $S$, with $|S|=k$, for which the graph obtained by deleting the vertices in $S$ and
all edges incident with a vertex in $S$, denoted by  $G-S$, is disconnected (by convention, $\kappa(K_n)=n-1$).  %If $\kappa(G)\ge k$, then  $G$ is {\em $k$-connected}.
It is proved in \cite{LSS89, LSS00} that $\kappa(G)\le \Mp(G)$ for every graph $G$.  It was noted in \cite{vdH08} that  the proof in \cite{LSS89} establishes $\kappa(G)\le\nu(G)$ for all $G$.  As defined in \cite{param}, the {\em minor monotone ceiling} of $\kappa$  is
$\kmm(G)=\max\{\kappa(H): H \preceq G\}.$  It follows from the definition that  $\h(G)-1\le \kmm(G)$, since the $K_{\h(G)}$ minor of $G$ implies $\kappa(K_{\h(G)})\le\kmm(G)$, and $\kmm(G)\le \nu(G)$, since $\kappa(G)\le\nu(G)$ and $\nu$ is minor monotone (see \cite{param} for more detail).


A Nordhaus-Gaddum type result is a (sharp) lower or upper bound on the
sum or product of a parameter of a graph and of its complement.
The Graph Complement Conjecture for $\nu$ \cite{GCCjoin} is a Nordhaus-Gaddum sum lower bound.

\begin{conj}   [\GCCnu] \label{gccnu}
For any graph $G$, 
\begin{equation} \label{nu-eq} \nu(G) + \nu(\Gc) \geq \ord G-2.\end{equation}
\end{conj}It is not possible to raise the lower bound $\ord G -2$ since equality is attained for any tree that includes a $P_4$: For such a tree, it is shown in \cite{AIM} that %$\mrp(\overline T)=3$, or equivalently, 
$\Mp(\overline T)=\ord T-3$.  Since $\Mp(T)=1$, $\Mp(T)+\Mp(\overline T)=\ord T -2$.  It is shown in \cite{SvdH} that \GCCnu~is true for graphs with tree-width at most 3, and thus for trees. Thus \GCCnu\ conjectures that $\ord G -2$  is a tight Nordhaus-Gaddum sum lower bound for $\nu$. %for any $\veps>0$, for $\ord G$ sufficiently large,
%\beq (1+o(\ord G))\ord G \le \nu(G)+\nu(\Gc),\eeq\label{NGlow}
This conjecture is studied in \cite{GCCjoin}, where it is established for certain graphs.  Various other forms of this conjecture have appeared, including:  \GCCp, i.e., $\Mp(G)+\Mp(\Gc)\ge \ord G -2$, \cite{GCCjoin};   \GCC, i.e., $\M(G)+\M(\Gc)\ge \ord G -2$, \cite{AIMrpt}; and \GCCxi, i.e., $\xi(G)+\xi(\Gc)\ge \ord G -2$, \cite{HLA2}.  Of course \GCCnu~implies \GCCp~implies \GCC, and \GCCnu~implies \GCCxi~implies \GCC.  The graph complement conjecture for $\mu$, i.e., $\mu(G)+\mu(\Gc)\ge \ord G -2$, appeared in \cite{KLV}.


Here we discuss  values of the multiplier $b$ for a Nordhaus-Gaddum sum upper bound for the parameter $\beta$ where $\beta$ is one of $\h, \kmm, \nu, \xi,$ or $ \mu$.
  We denote  by $b_\beta$  the least value of  $b$ making 
 \[  \beta(G)+\beta(\Gc)\le b\,\ord G \] true for every graph of order at least two, and call  $b_\beta$ the {\em NG upper multiplier for $\beta$}.  Stiebitz \cite{Stie} has shown that 
%\beq\label{eqStieg}
\[\h(G)+\h(\Gc)\le \frac 6 5 \ord G\]%\eeq
and there exist graphs  %of arbitrarily large order 
achieving $\h(G)+\h(\Gc)= \frac 6 5 (1-\varepsilon) \ord G$ for arbitrarily small $\varepsilon$, so $\bh= \frac 6 5$. We establish bounds for $\bk,  \bnu,$ and $ \bxi$.  Clearly $\bh\le\bk\le\bnu\le\bxi$, and $\bh\le \bmu\le\bxi$.
 In Section \ref{suNGlow} we construct a family of graphs  to show that $\bk\ge \frac 4 3$. In Section \ref{suNGup} we show that $\bxi\le \sqrt{2}$.  In Section \ref{scon} we summarize our conclusions. 
Note that the Nordhaus-Gaddum  sum upper bound for the  parameters $\M$ and $\Mp$ is not interesting because it is trivially $2\ord G-1$:
\[\M(K_n)+\M(\overline{K_n})=\Mp(K_n)+\Mp(\overline{K_n})=(n-1)+n=2\ord{K_n}-1.\] 





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

\section{Lower bound for  NG upper multiplier for $\kmm$}\label{suNGlow}% Colin de Verdi\`ere type paprameters}

In this section we construct a self-complementary graph $H(a)$ on $12a-4$ vertices for $a\ge 2$, and show that $H(a)$ has a minor $\Ham$ with $\delta(\Ham)=\kappa(\Ham)=8a-4$, where $\delta(G)$ denotes the minimum degree of a vertex of $G$.  It is shown that this example implies that $\bk\ge 4/3$.

\begin{ex}\label{ex:Ha}  {\rm Construct the graph $H(a)=(V,E)$ as follows (see Figure \ref{fig:Ha}):   The $12a-4$ vertices of  $H(a)$ are partitioned into four sets $V_i,i=1,2,3,4$  of $r=3a-1$ vertices each.  The sets $V_1$ and $V_2$ are the ``sparse part" of $H(a)$, with $H(a)[V_i]=\overline{K_r}, i=1,2$ (where $G[W]$ denotes the subgraph of $G$ induced by the subset $W$ of the vertices of $G$). The sets $V_3$ and $V_4$ are the ``dense part" of $H(a)$, with $H(a)[V_i]=K_r, i=3,4$.  Every  edge between a vertex in $V_1$ and a vertex in $V_3$ is in the edge set $E$, and likewise for $V_2$ and $V_4$.  There are no edges between $V_1$ and $V_4$, nor between $V_2$ and $V_3$.  Regarding the edges between $V_1$ and $V_2$, number the vertices of $V_1$ as $u_{2i-1}, i=1,\dots,r$ and the vertices of $V_2$ as $u_{2i}, i=1,\dots,r$.  Then vertex $u_s\in V_1$ is adjacent to  the $a$ vertices $u_{s+j}\in V_2,\ j=1,3,\dots, 2a-3, 2a-1$ (where for $k=6a-1,\dots, 8a-4$, $u_k$ is interpreted as $u_\ell$ with $\ell\equiv k \mod (6a-2)$ and $1\le \ell\le 2a-2$).   If $u\in V_1\cup V_2$, then $\deg_{H(a)} u=r+a=4a-1$ (where $\deg_G w$ denotes the degree of  $w$ in $G$). Regarding the edges between $V_3$ and $V_4$, number the vertices of $V_3$ as $v_{2i-1}, i=1,\dots,r$ and the vertices of $V_4$ as $v_{2i}, i=1,\dots,r$.  Then vertex $v_s\in V_3$ is adjacent to all vertices $v_p\in V_4$ except for $p=s+j, j=1,3,\dots, 2a-3, 2a-1$.  If $v\in V_3\cup V_4$, then $\deg_{H(a)} v=(r-1)+r+(r-a)=8a-4$.  It is clear from the construction that $\Hac=H(a)$. 

\begin{figure}[!h]
\begin{center}
\scalebox{.38}{\includegraphics{HaDiagram}}
\caption{Schematic diagram for the construction of  $H(a)$}\label{fig:Ha}
\end{center}
\end{figure}
\vspace{-3mm}
Construct the minor $\Ham$ by contracting the edges $u_{2i-1}u_{2i}, i=1,\dots,r$, and denote the set of these $r$ vertices by $V_{1,2}$.  If $v\in V_3\cup V_4$, then $\deg_{\Ham} v=\deg_{H(a)} v=8a-4$.
Note that each of the new vertices in $V_{1,2}$ has degree equal to $2((4a-1)-1)=8a-4$, so $\Ham$ is $(8a-4)$-regular.  Furthermore, if $w\in V_{1,2}$, $w$ is adjacent to all $2r=6a-2$ vertices in $V_3\cup V_4$ so $\Ham[V_{1,2}]$ is $(2a-2)$-regular. Since each vertex  in $V_3\cup V_4$ is adjacent to $r=3a-1$ vertices in $V_{1,2}$,  $\Ham[V_3\cup V_4]$ is $(5a-3)$-regular.
}\end{ex}

To establish that $\kappa(\Ham)=\delta(\Ham)$, we use the property that for certain circulants $C$, 
$\kappa(C)=\delta(C)$, establish a method for computing $\kappa$, and examine parts of $\Ham$ separately. %(for graphs that have this property). 
For $1\le t\le \lfloor \frac {n-1} 2\rfloor$, the {\em consecutive circulant} $\Cnt n t$ is the graph on the vertices $\{0,1,\dots,n-1\}$ with vertex $i$ adjacent to vertices $i+j$ and $i-j$ for $j=1,\dots,t$ (with arithmetic mod $n$).  We will use the fact that for a consecutive circulant the vertex connectivity is equal to the (common) degree;  Harary \cite{Har} gave the consecutive circulant as an example of a graph having maximum vertex connectivity $\frac{2m} n$ among graphs having  $n$ vertices and $m$ edges (when $\frac{2m} n$ is an integer), and this result is now well known.  %A complete analysis of which circulants $C$ have $\kappa(C)=\delta(C)$ can be found in \cite{BT}.

\begin{thm}\label{circ}{\rm \cite[Theorem 4.1.5 (Harary)]{W}} For $1\le t\le \lfloor \frac {n-1} 2\rfloor$, 
\[\kappa(\Cnt n t)=\delta(\Cnt n t)=2t.\]
\end{thm}
\vspace{-3mm}


\begin{thm}\label{kf} Let $G$ be a connected graph on $n$ vertices with $G\ne K_n$   and let $1\le t\le n-1-\delta(G)$.  Define 
\[f(t)=\max\{s\in\Z^+:K_{t,s} \mbox{ is a subgraph of }\Gc\},\] %(it is possible that $f(r)=0$). 
where $K_{s,t}$ denotes the complete bipartite graph on $s$ and $t$ vertices.  Then
%with bipartion sets of orders $s$ and $t$.  Then
\[\kappa(G)=\min\{n-(t+f(t)):1\le t\le n-1-\delta(G)\}.\]
\end{thm}
\bpf  For every $t$ such that $1\le t\le n-1-\delta(G)$, $\Gc$ contains a $K_{t,1}$ (by choosing a vertex $v$ of degree $\delta(G)$ as the partite set of 1 vertex, and $t$ of its non-neighbors as the other partite set), so $f(t)$ is defined.  

Choose $t$ such that $1\le t\le n-1-\delta(G)$.  Let $U$ be a set of $t$ vertices and let $W$ be a set of $f(t)$ vertices such that $\Gc[U\cup W]$ contains a $K_{t,f(t)}$ subgraph.  Then $G[U\cup W]$ is disconnected, so $\kappa(G)\le \ord{V\setminus (U\cup W)}=n-(t+f(t)).$
Since this is true for every $t$ such that $1\le t\le n-1-\delta(G)$, \[\kappa(G)\le\min\{n-(t+f(t)):1\le t\le n-1-\delta(G)\}.\]

Choose a set $S$ such that $\ord S =\kappa(G)$ and $G-S$ is disconnected.  Let $U$ be the set of vertices of one connected component, let $t_0=\ord U$, and let $W=V\setminus(U\cup S)$; note $\ord W=n-(t_0+\kappa(G))$.  Then $\Gc$ contains  $K_{t_0,n-(t_0+\kappa(G))}$ with bipartition $U, W$.  Thus
$f(t_0)\ge n-(t_0+\kappa(G)),$ so
\[\kappa(G)\ge n-(t_0+f(t_0))\ge \min\{n-(t+f(t)):1\le t\le n-1-\delta(G)\}. \qedhere\]
 \epf


% This sentence is FALSE: Note that for $f$ as defined in Theorem \ref{kf}, $f(1)=n-1-\delta(G)$, $f(n-1-\delta(G))=1$, and more generally, if $f(t)=s$ then $f(s)=t$.

We now return to establishing the properties  of one of the graphs constructed in Example \ref{ex:Ha}.

\begin{obs}\label{obs}  Let $G$ be a graph whose vertex set $V$ can be partitioned as $V = X \dotcup Y$ such that each vertex in $X$ is adjacent to each vertex in $Y$.  Let $G_X=G[X]$ and $G_Y=G[Y]$.  Then 

\begin{itemize}

\item $\delta(G) = \min \{ \delta(G_X) + |Y|, \, \delta(G_Y)+|X|\}$,

\item $\kappa(G) = \min \{ \kappa(G_X) + |Y|, \, \kappa(G_Y)+|X|\}$.

\end{itemize}

\end{obs}

\begin{thm}\label{thm:Ha} 
For  $\Ham$ as in Example \ref{ex:Ha},
\[\kappa(\Ham)=\delta(\Ham)=8a-4.\]
\end{thm}

\bpf  Let $X= V_{1,2}$ and $Y= V_3\cup V_4$.  Then $V(\Ham)= X \dotcup Y$ and every vertex in $X$ is adjacent to every vertex in $Y$.  By Observation \ref{obs}, if we show that $\kappa(\Ham[V_{1,2}]) = \delta(\Ham[V_{1,2}])$ and $\kappa(\Ham[V_3\cup V_4])=\delta(\Ham[V_3\cup V_4])$, it follows that $\kappa(\Ham) = \delta(\Ham)$.  

Since $\Ham[V_{1,2}]=\Cnt {r} {a-1}$, we have $\kappa(\Ham[V_{1,2}])=\delta(\Ham[V_{1,2}])$ by Theorem \ref{circ}.

Recall that in $\Ham[V_3\cup V_4]=H(a)[V_3\cup V_4]$, the vertices of $V_3$ are numbered  as $v_{2i-1}, i=1,\dots,r$  and the vertices of $V_4$ as $v_{2i}, i=1,\dots,r$, and vertex $v_s\in V_3$ is adjacent to all vertices $v_p\in V_4$ except for $p=s+j, j=1,3,\dots, 2a-3, 2a-1$ (where for $p> 6a-2, v_p$ means $v_{p-(6a-2)}$).   
Thus the vertex $v_s$ in $\overline{H(a)[V_3\cup V_4]}$ is adjacent to precisely
   the vertices $v_p, \ p=s+j, j=1,3,\dots, 2a-3, 2a-1$.  This is a bipartite regular graph with a great deal of symmetry, so in determining the shared neighborhood of two vertices,  no generality is lost by considering the 
  vertices $1$ and $1 + 2d$  (with $d\le \lceil\frac{3a-1}2\rceil$). The size of the
shared neighborhood is  $\max(a -  d,0) $. For  $1\le t\le a =2r-1-(5a-3)=\ord{\Ham[V_3\cup V_4]}-1-\delta(\Ham[V_3\cup V_4])$, the maximum neighborhood intersection
of a set of $t$  vertices happens when those vertices are consecutive in the
same bipartition set, and it follows that in this case $f(t) = a + 1 - t$.  So for all $t\in\{1,\dots,a\}$, $\ord{\Ham[V_3\cup V_4]}-(t+f(t))=5a-3$.
Thus  $\kappa(\Ham[V_3\cup V_4])=5a-3 = \delta(\Ham[V_3\cup V_4])$.  \epf


\begin{cor}\label{cor:Ha} For the graph $H(a)$ in Example \ref{ex:Ha}, \[\kmm(H(a))\ge 8a-4\] and
\[\kmm(H(a))+\kmm(\Hac)\ge \frac  4 3(1-\frac 1{6a-2})\ord{H(a)}.\] 
Thus \[\bk\ge \frac  4 3.\]
\end{cor}
\bpf By Theorem \ref{thm:Ha}, $\kmm(H(a))\ge\kappa(\Ham)= 8a-4$. % if $3a-1$ is prime.  
Since $H(a)$ is self-complementary, $\kmm(\Hac)\ge 8a-4$ also, and thus $\kmm(H(a))+\kmm(\Hac)\ge 16a -8$.  The second statement can then be established by arithmetic.  Since $\bk\ge \frac 1 {\ord{H(a)}} (\kmm(H(a))+\kmm(\Hac)),$ by taking the limit as $a\to\infty$ we see that $\bk\ge \frac  4 3$.
\epf
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Upper bound for  NG upper multiplier for $\xi$}\label{suNGup}%Colin de Verdi\`ere type parameters}
In this section we show that the NG upper multiplier $\bxi$ is at most $\sqrt 2$.
 
 \begin{thm}\label{thm:xiubd}{\rm \cite{HHMS}} Let $G=(V_G,E_G)$ be a connected graph.  Then
\beq\label{eq0}\ord{E_G} + a\ge \frac {\xi(G)(\xi(G)+1)} 2\eeq
where $a=1$ if $G$ is bipartite and every optimal matrix for $\xi(G)$ has zero diagonal, and $a=0$ otherwise.
\end{thm}

Since $\xi(G)$ is the maximum of $\xi(G_i)$ taken over the connected components $G_i$ of $G$, the hypothesis that $G$ is connected is unnecessary.
 \begin{cor}\label{cor:xiubd} Let $G=(V_G,E_G)$ be a  graph. Then
\beq\label{eq0nu}\ord{E_G}+1 \ge \frac {\xi(G)(\xi(G)+1)} 2.\eeq
\end{cor}




 \begin{cor}\label{cor:xiubd2} Let $G=(V_G,E_G)$ be a  graph with at least one edge. Then % with $\ord{E_G}\ge 2$.
\beq\label{eq1nu}\xi(G)  \le  \sqrt{2\ord {E_G}}.\eeq
\end{cor}
\bpf Algebraic manipulation of  (\ref{eq0nu}) gives $\xi(G)\le \frac 1 2 (-1+\sqrt{8\ord{E_G}+9}).$
  Further manipulation  shows that the inequality $\frac 1 2 (-1+\sqrt{8\ord{E_G}+9})\le \sqrt{2\ord{E_G}}$ is equivalent to $2\le\ord{E_G}$, so (\ref{eq1nu}) is true if $G$ has at least two edges.  If $G$ has exactly one edge then $G$ has components $K_2$ and possibly some $K_1$'s, and thus $\xi(G)=1<\sqrt 2$. 
\epf

Nordhaus-Gaddum bounds usually take one of two forms: additive or multiplicative. The form of inequality (\ref{eq1nu}) suggests a third category of Nordhaus-Gaddum bound: Pythagorean.

\begin{cor}\label{cor:pyth} Let $G = (V_G, E_G)$ be a graph of order at least two. Then
\[ \xi(G)^2 + \xi(\overline{G})^2 \le |G|^2 - |G|. \]
\end{cor}
\bpf Let $|G| = n \ge 2$. In the case where either $G$ has no edges or $\overline{G}$ has no edges, $\xi$ will take the value $1$ for one of the two graphs and the value $n-1$ for the other, in which case the result holds. In any other case inequality (\ref{eq1nu}) applies both to $G$ and to $\overline{G}$, giving us two inequalities the sum of whose squares is
\[ \xi(G)^2 + \xi(\overline{G})^2 \le 2|E_G| + 2|E_{\overline{G}}| = |G|^2 - |G|.  \qedhere\]
\epf

\begin{cor}\label{cor:xiubd3} Let $G=(V_G,E_G)$ be a  graph   of order at least two.  Then
\[\xi(G)+\xi(\Gc)  \le  \sqrt{2}\ord G,\]
and thus $b_\xi\le \sqrt 2$.\end{cor}
\bpf Let $|G| = n \ge 2$, and by Corollary 3.4 choose $x \ge \xi(G)$ and $y \ge \xi(\overline{G})$ such that $x$ and $y$ lie on the circle $x^2 + y^2 = n^2$.
The maximum value of $x + y$ on this circle is $\sqrt{2}n$. \epf


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

\section{Conclusions}\label{scon}

In summary, we have established
\[ 1.333< \frac 4 3 \le \bk \le \bnu\le\bxi\le \sqrt 2  < 1.415.\]

We have no evidence that the construction in Section \ref{suNGlow} is tight, even for $\bk$.  On the other hand, the inequality (\ref{eq0}) with $a=0$ is known to be tight for some small examples and for complete graphs (it is tight with $a=1$ for $K_{3,3}$).  For $\nu$, since a diagonal entry for a vertex of degree at least one cannot be zero, $a=0$ and the inequality (\ref{eq0}) becomes $\ord{E_G} \ge \frac {\nu(G)(\nu(G)+1)} 2$ for graphs with at least one edge; again this is tight for some small graphs and complete graphs. This leaves open the possibility that Corollaries \ref{cor:xiubd2} ---  \ref{cor:xiubd3} may be asymptotically tight.   

\begin{quest} Given $x$ and $y$ positive with $x^2 + y^2 = 1$, does there exist an increasing sequence of graphs $G_i$ on $n_i$ vertices such that $\nu(G_i)/n_i$ approaches $x$ and $\nu(\overline{G_i})/n_i$ approaches $y$?  Or such that $\xi(G_i)/n_i$ approaches $x$ and $\xi(\overline{G_i})/n_i$ approaches $y$?  
\end{quest}

The particular case of $x =y=\frac{\sqrt{2}}2$  suggests the next question.

\begin{quest} Do $b_\nu$ and $b_\xi$ take the maximum possible value of $\sqrt{2}$?
\end{quest}

On the other hand it seems more difficult to construct examples for $\bmu$, and the only bounds we know are those from $\h$ (due to Stiebitz \cite{Stie}) and $\xi$. i.e., 
\[ 1.2= \frac 6 5=\bh\le \bmu\le\bxi\le\sqrt 2< 1.415.\]
%\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{20}



\bibitem{AIM} AIM Minimum Rank -- Special Graphs Work Group (F. Barioli, W. Barrett, 
 S. Butler,   
S. M. Cioab\u{a}, D. Cvetkovi\'c, 
  S. M. Fallat,
C. Godsil,  
W. Haemers,  
 L. Hogben,  R. Mikkelson,  S. Narayan,  O. Pryporova,   I. Sciriha,  W. So,   D. Stevanovi\'c,  H. van der Holst,
K. Vander Meulen, 
A. Wangsness).  Zero forcing sets and the minimum rank  of graphs.   {\em Linear Algebra Appl.}, 428: 1628--1648, 2008.


\bibitem{param} 	F. Barioli, W. Barrett, S. Fallat, H. T. Hall, 
L. Hogben, B. Shader, P. van den Driessche, H. van der Holst.  
Parameters related to tree-width, zero forcing, and maximum 
nullity of a graph.   {\em J. Graph Theory}, 72: 146--177, 2013.

\bibitem{GCCjoin} F. Barioli, W. Barrett, S. M. Fallat,  H. T. Hall, L. Hogben,  H. van der Holst.
	On the graph complement conjecture for minimum rank.  	{\em Linear Algebra Appl.}, 436: 4373--4391, 2012.

\bibitem{BFH3}	F. Barioli, S. M. Fallat, and L. Hogben. A variant on the graph parameters of Colin de Verdi\`ere: Implications to the minimum rank of graphs. {\em Electron. J. of Linear Algebra}, 13: 387--404, 2005. 


\bibitem{AIMrpt} R. Brualdi, L. Hogben, B. Shader.
AIM Workshop on Spectra of Families of Matrices Described by Graphs, 
Digraphs and Sign
Patterns, Final report: Mathematical Results, 2007. 
\url{http://aimath.org/pastworkshops/matrixspectrumrep.pdf}.


\bibitem{CN71} G. Chartrand and J. Mitchem.  
Graphical theorems of the Nordhaus-Gaddum class.   
In {\em Recent Trends in Graph Theory}, Lecture Notes in Mathematics 186, Springer, Berlin, pp. 55--61. 1971.

\bibitem{CdVmu} 	Y. Colin de Verdi\`ere.  On a new graph invariant and a criterion for planarity. In {\em Graph Structure Theory}, Contemporary Mathematics 147, American Mathematical Society, Providence, pp. 137--147, 1993.

\bibitem{CdVnu} Y. Colin de Verdi{\`e}re, Multiplicities of eigenvalues and tree-width of graphs, \textit{J. Combin. Theory Ser. B}, 74: 121--146, 1998.


\bibitem{HLA2}	S. Fallat and L. Hogben. Minimum Rank, Maximum Nullity, and Zero Forcing Number of Graphs.  In {\em Handbook of Linear Algebra},  2nd ed., CRC Press, Boca Raton, FL, 2013. 


\bibitem{HHMS}	H. T. Hall, L. Hogben, R. Martin, B. Shader. Expected values of parameters associated with the minimum rank of a graph.   {\em Linear Algebra  Appl.}, 433: 101--117, 2010.

\bibitem{Har}	F. Harary. The maximum connectivity of a graph.   {\em Proc. National Academy Sciences}, 48: 1142--1146, 1962.

\bibitem{vdH08}	H. van der Holst. Three-connected graphs whose maximum nullity  is at most three.   {\em Linear Algebra  Appl.}, 429: 625--632, 2008.  

\bibitem{HLS} H. van der Holst, L. Lov{\'a}sz, and A. Schrijver, The Colin de Verdi{\`e}re graph parameter.  In \textit{Graph Theory and Computational Biology (Balatonlelle, 1996)}, Bolyai Soc. Math. Stud. 7, J{\'a}nos Bolyai Math. Soc., Budapest,  pp. 29--85, 1999.

\bibitem{KLV} A. Kotlov, L. Lov{\'a}sz, S. Vempala. The Colin de Verd\`ere number and sphere representations of a graph.  \textit{Combinatorica}, {17}: 483--521, 1997.

\bibitem{LSS89} L. Lov{\'a}sz, M. Saks and A. Schrijver. Orthogonal representations and connectivity of graphs.  {\em Linear Algebra  Appl.}, {114/115}: 439--454, 1989.

\bibitem{LSS00} L. Lov{\'a}sz, M. Saks and A. Schrijver. A correction: ``Orthogonal representations and connectivity of graphs.'' {\em Linear Algebra  Appl.}, {313}: 101--105, 2000.


\bibitem{SvdH}
J. Sinkovic and H. van der Holst. 
The minimum semidefinite rank of the complement of partial $k$-trees.
{\em Linear Algebra  Appl.}, 434: 1468--1474, 2011.

\bibitem{Stie}M. Stiebitz.
On Hadwiger's number -- a problem of the Nordhaus-Gaddum type.
{\em Discrete Math.}, 101: 307--317, 1992.


\bibitem{W} Douglas B. West.  {\em 
Introduction to Graph Theory}, 2nd ed.,   Prentice Hall, New Jersey, 2001.

\end{thebibliography}

\end{document}












