# On the minimum number of distinct eigenvalues of a threshold graph

Shaun Fallat, Seyed Ahmad Mojallal  Department of Mathematics and Statistics,
University of Regina, Regina, Saskatchewan, S4S0A2, Canada
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

For a graph $G$, we associate a family of real symmetric matrices, $S(G)$,
where for any $A\in S(G)$, the location of the nonzero off-diagonal entries of
$A$ are governed by the adjacency structure of $G$. Let $q(G)$ be the minimum
number of distinct eigenvalues over all matrices in $S(G)$. In this work, we
give a characterization of all connected threshold graphs $G$ with $q(G)=2$.
Moreover, we study the values of $q(G)$ for connected threshold graphs with
trace $2$, $3$, $n-2$, $n-3$, where $n$ is the order of threshold graph. The
values of $q(G)$ are determined for all connected threshold graphs with $7$
and $8$ vertices with two exceptions. Finally, a sharp upper bound for $q(G)$
over all connected threshold graph $G$ is given.

###### keywords:

Minimum number of distinct eigenvalues, Threshold graphs, Vertex-clique
incidence matrix, Strong Spectral Property, Eigenvalue of graphs.

AMS Subject Classification: 05C50, 15A29

##  1 Introduction

Let $G=(V(G),E(G))$ be a simple graph with vertex set
$V(G)=\\{1,2,\ldots,n\\}$ and edge set $E(G)$. The order the graph $G$ is
defined as $|V(G)|$. The set $S(G)$ of symmetric matrices described by $G$
consists of the set of all real symmetric $n\times n$ matrices $A=(a_{ij})$
such that for $i\neq j$, $a_{ij}\neq 0$ if and only if $ij\in E(G)$. We denote
the spectrum of $A$, i.e., the multiset of eigenvalues of $A$, by
$\mathrm{Spec}(A)$. Given a graph $G$, the spectral invariant $q(G)$ is
defined as follows:

$q(G)=\min\\{q(A)\,:\,A\in S(G)\\},$

where $q(A)$ is the number of distinct eigenvalues of $A$. The spectral
invariant $q(G)$ is called the minimum number of distinct eigenvalues of the
graph $G$.

All matrices are real and symmetric; $O$ and $I$ denote zero and identity
matrices of appropriate size, respectively. If the distinct eigenvalues of $A$
are $\lambda_{1}<\lambda_{2}<\ldots<\lambda_{q}$ and the multiplicities of
these eigenvalues are $m_{1},m_{2},\ldots,m_{q}$ respectively, then the
ordered multiplicity list of $A$ is $m(A)=(m_{1},m_{2},\ldots,m_{q})$ and,
additionally, the spectrum of $A$ is denoted by

$Spec(A)=\\{\lambda_{1}^{[m_{1}]},\,\lambda_{2}^{[m_{2}]},\,\ldots,\,\lambda_{q}^{[m_{q}]}\\}.$

Here a simple eigenvalue $\lambda_{k}^{[1]}$ is simply denoted by
$\lambda_{k}$. The maximum multiplicity of $G$ is
$M(G)=max\\{mult_{A}(\lambda):A\in S(G),\lambda\in\mathrm{Spec}(A)\\}$, and
the minimum rank of $G$ is $mr(G)=min\\{rank\,A;\,A\in S(G)\\}$. If we let
$S_{+}(G)$ be all positive semidefinite matrices belongs to $S(G)$, then the
maximum positive semidefinite nullity of $G$ is
$M_{+}(G)=max\\{mult_{A}(\lambda):A\in
S_{+}(G),\lambda\in\mathrm{Spec}(A)\\}$. A subgraph $H$ of a graph $G$ is a
graph whose vertex set and edge set are subsets of those of $G$. If $H$ is a
subgraph of $G$, then $G$ is said to be a supergraph of $H$.

The class of matrices $S(G)$ has been of interest to many researchers recently
(see [8, 9] and the references therein), and there has been considerable
development of the parameters $M(G)$ and $mr(G)$, and their positive
semidefinite counterparts, see, for example, the works [5, 7, 8]. Furthermore,
as a consequence interest has grown in connecting these parameters to various
combinatorial properties for a given graph. For example, the inverse
eigenvalue problem for graphs (see [12]) continues to receive considerable and
deserved attention, as it remains one of the most interesting unresolved
issues in combinatorial matrix theory.

Threshold graphs can be characterized in many ways. One way of obtaining a
threshold graph is through an iterative process which starts with an isolated
vertex, and where, at each step, either a new isolated vertex is added, or a
vertex adjacent to all previous vertices (dominating vertex) is added. We may
represent a threshold graph on $n$ vertices using a binary sequence
$(b_{1},\ldots,b_{n})$. Here $b_{i}$ is 0 if vertex $v_{i}$ was added as an
isolated vertex, and $b_{i}$ is 1 if $v_{i}$ was added as a dominating vertex.
This representation has been called a creation sequence [11]. For convenience,
we use 0 as the first character of the string; it represents the first vertex
of the graph. The number of characters equal to 1 in this string, called the
trace of the graph, indicates the number of dominating vertices in its
construction [15]. As we are interested in connected threshold graphs, we
insist $b_{n}=1$. In general, the trace $T$ of a graph $G$ is maximum index
$i$ such that $d_{i}\geq i$, where $d_{i}$ is $i$th largest degree of $G$.
Finally, for brevity, if $G$ is a threshold graph with creation sequence
$(b_{1},\ldots,b_{n})$, then we write $G\cong(b_{1},\ldots,b_{n})$.

For a threshold graph $G$, let $A\in S(G)$. We denote the submatrix of $A$
with rows indexed by dominating vertices and columns indexed by isolated
vertices in $G$ by $A(\bar{1},\,\bar{0})$. Obviously, $A(\bar{1},\,\bar{0})$
is an $T\times(n-T)$ matrix. The submatrix of $A$ obtained by deleting the row
and column corresponding to a vertex $i$ is denoted by $A(i)$ and the
submatrix of $A$ obtained by deleting its $i$th row is denoted by $A(i;)$. A
split graph is a graph whose vertices can be partitioned into a clique and an
independent set. In a split graph, if each vertex of the clique is adjacent to
each vertex of the independent set, the graph is called a complete split
graph.

Our main interest in this work lies in studying the value of $q(G)$ for
connected threshold graphs. It is clear that knowledge of $q(G)$ for a graph
$G$ will impact current studies of the inverse eigenvalue problem for graphs,
and, in particular, the parameters $M(G)$ and $mr(G)$.

Recently, J. Ahn et al. [2] offered a complete solution to the ordered
multiplicity inverse eigenvalue problem for graphs on six vertices. This work,
represents in part, our motivation to study the values of $q(G)$ for connected
threshold graphs with $7$ and $8$ vertices as well as several classes of
threshold graphs with arbitrary orders.

The paper is organized as follows. In Section 2, the notion of the vertex-
clique incidence matrix of a graph $G$ is introduced and an application of
this notion in the theory of minimum number of distinct eigenvalues of a graph
is explored here. In Section 3, a list of well-known results and facts are
given. In Section 4, a complete characterization of all threshold graphs with
$q(G)=2$ is given. In Section 5, the minimum number of distinct eigenvalues
for a few specified threshold graphs are determined. In Section 6, a full
characterization of $q(G)$ of all threshold graphs with trace two is given. In
the next three sections we study $q(G)$ for threshold graphs with trace equal
to $3$ and complete characterizations are provided for trace equal to $n-2$
and $n-3$. In Section 10 and 11, we calculate the values of $q(G)$ for any
connected threshold graph of order $n=7$ and for all such threshold graphs of
order 8, with two exceptions. Finally, in Section 12, we provide a sharp upper
bound for $q(G)$ of any connected threshold graph of order $n$.

##  2 Vertex-clique incidence matrix of a graph

In this section, we introduce the notion of vertex-clique incidence matrix of
a graph $G$ and its application to the issue of determining the minimum number
of distinct eigenvalues of a graph.

An edge clique cover $F$ of a simple and undirected graph $G$ is a set of
cliques of $G$, which together contain each edge of $G$ at least once. The
smallest cardinality of any edge clique cover of $G$ is called the edge clique
cover number of $G$, and is denoted by $cc(G)$. This number exists as the edge
set of $G$ forms an edge clique cover for $G$. An edge clique cover of $G$
with size $cc(G)$ is referred to as a minimum edge clique cover of $G$.

The vertex-clique incidence matrix of $G$ associated with the edge clique
cover $F$ is defined as follows: Corresponding to any clique partition
$F=\\{C_{1},C_{2},\ldots,C_{k}\\}$, we define a real matrix $M_{F}$ with rows
and columns indexed by the vertices in $V$ and the cliques in $F$,
respectively, such that the $ij$-entry of $M_{F}$ is real and nonzero if and
only if the vertex $i$ belongs to the clique $C_{j}\in F$. To ensure
$M_{F}\,M^{T}_{F}\in S(G)$, we arrange that the inner product of row $i$ and
column $j$ (when $i\neq j$) in $M_{F}$ is nonzero if and only if $ij\in E(G)$.

Recall that if $A$ and $B$ are any matrices of orders $t\times s$ and $s\times
t$, respectively, then $AB$ and $BA$ have the same nonzero eigenvalues. Thus
in order to minimize the number of distinct eigenvalues of $M_{F}\,M_{F}^{T}$,
we need to minimize the number of distinct eigenvalues of $M_{F}^{T}\,M_{F}$.
This is the key idea used to generalize the vertex-clique incidence matrix
obtained from an edge clique cover by considering any positive real entries
for $M_{F}$ or any negative real entries for $M_{F}$ but carefully preserving
the condition that $M_{F}\,M_{F}^{T}\in S(G)$.

##  3 Notations and preliminaries

In this section, we shall list some previously known results that are needed
as well as some notation used throughout the paper.

Let $\circ$ denote the Schur (also known as the Hadamard or entrywise)
product. The symmetric matrix $A$ has the Strong Spectral Property (or $A$ has
the SSP for short) if the only symmetric matrix $X$ satisfying $A\circ X=O$,
$I\circ X=O$ and $[A,\,X]=AX-XA=O$ is $X=O$.

The following result is given in [4, Thm. 10].

######  Lemma 3.1.

[4] If $A\in S(G)$ has the SSP, then every supergraph of $G$ with the same
vertex set has a realization that has the same spectrum as $A$ and has the
SSP.

The following definitions and results can be found in [14]: For a graph $G$
and a vertex $v\in V(G)$, let $N(v)$ denotes the open neighbourhood of $v$,
i.e., the set of all vertices in $G$ adjacent to $v$. Let $dup(G,v)$ be a
graph obtained by duplicating $v$, that is, augmenting $G$ with a new vertex
$w$ and extra edges joining $w$ to every vertex in $N(v)$, so that in
$dup(G,v)$ we have $N(v)=N(w)$ and $v$ and $w$ are not neighbours.
Alternatively, “joined duplicated vertex” graph $jdup(G,v)$ is equal to
$dup(G,v)$ with an extra edge joining $v$ and its duplicate vertex, $w$.

######  Lemma 3.2.

[14] If $G$ is a non-empty graph, then

$q(jdup(G,\,v))\leq q(G).$

######  Lemma 3.3.

[14] If $v$ is a vertex of $G$ and $A\in S(G)$ with
$\lambda=a_{v,v}\in\sigma(A)$, then there is a matrix $C\in S(dup(G,v))$ with
$\lambda=c_{v,v}$ so that the spectra of $A$ and $C$ are equal as sets, with
the multiplicity of $\lambda$ in $\sigma(C)$ increased by 1, and so that $A$
is equal to $C$ with the $w$th row and column deleted, where $w$ is the
duplicate vertex of $v$ introduced to form $dup(G,v)$ from $G$.

Similar results can also be found in [2].

######  Lemma 3.4.

[2] Let $G$ be a graph with $M\in S(G)$ having multiplicity list
$(\gamma_{1},\,\ldots,\gamma_{i},\ldots,\gamma_{k})$ where the eigenvalue 0
has multiplicity $\gamma_{i}$. Then the following two cases are possible:
1\. If the diagonal entry of $M$ corresponding to $v_{j}$ is zero, then the
graph $H$ attained from $G$ by cloning $v_{j}$ without an edge has a matrix
$N\in S(H)$ that attains the multiplicity list
$(\gamma_{1}\,\ldots,\gamma_{i}+1,\,\ldots,\gamma_{k})$.
2\. If the diagonal entry of $M$ corresponding to $v_{j}$ is nonzero, then the
graph $H$ attained from $G$ by cloning $v_{j}$ with an edge has a matrix $N\in
S(H)$ that attains the multiplicity list
$(\gamma_{1}\,\ldots,\gamma_{i}+1,\,\ldots,\gamma_{k})$.

Recall that the length of a path is simply the number of edges in that path,
and that the distance between two vertices, (in the same component) is the
length of the shortest path between those two vertices. The next result
represents a basic combinatorial lower bound on $q(G)$.

######  Lemma 3.5.

[1] If there are vertices $u,\,v$ in a connected graph $G$ at distance $d$ and
the path of length $d$ from $u$ to $v$ is unique, then $q(G)\geq d+1$.

Let $G$ be the star on $n$ vertices (that is, $G=K_{1,n-1}$, the complete
bipartite graph with disjoint parts having sizes 1, n-1, respectively). Using
Lemma, 3.5, it is clear that $q(G)\geq 3$. On the other hand, the adjacency
matrix associated with $G$ has the eigenvalues $\pm\sqrt{n-1},0$. Hence
$q(G)=3$. Further observe that $G$ is a threshold graph with creation sequence
$G\cong(0,0,\ldots,0,1)$, where there are $n-1$ consecutive zeros in this
string. Hence for any threshold graph $H$ with creation sequence $(0,0,\ldots
0,1,1,\ldots 1)$, where the number of 0’s and 1’s is positive satisfies
$q(H)\leq q(G)\leq 3$, by application of Lemma 3.2.

##  4 Threshold graphs with $q(G)=2$

In this section we provide a characterization for connected threshold graphs
that satisfy $q(G)=2$.

######  Theorem 4.1.

For a threshold graph $G$, $q(G)=2$ if and only if there exists a matrix $A\in
S(G)$ such that $A(\bar{1},\,\bar{0})$ is column orthogonal.

###### Proof.

It is well-known that if $q(G)=2$ then there exists an $n\times n$ orthogonal
matrix $A\in S(G)$. This gives any $n\times k$ submatrices of $A$ must be
column orthogonal. In particular, we consider the submatrix of $A$ with rows
indexed by all vertices and columns indexed by only isolated vertices. This
gives $A(\bar{1},\,\bar{0})$ is column orthogonal.

Now, assume that there exists a matrix $A\in S(G)$ s.t. $A(\bar{1},\,\bar{0})$
is column orthogonal. This leads to a vertex-clique incidence matrix $M$ of
the form $\left(\begin{array}[]{c}A(\bar{1},\,\bar{0})\\\ X\\\
\end{array}\right),$ where $X=diag(x_{1},x_{2},\ldots,x_{k})$ and $k=n-T$. We
can choose the values of $x_{i}$ under which the size of each column is
constant $C$. This gives $M^{T}\,M=C^{2}\,I_{k}$, and then $q(MM^{T})=2$. To
complete the proof, it suffices to show that $M\,M^{T}\in S(G)$.

Assume that $v$ is a dominating vertex and $w$ an isolated vertex. We have
$vw\in E(G)$ if and only if the inner product between rows corresponding to
$v$ and $w$ in $M$ is nonzero. If both $v$ and $w$ are isolated, then the
inner product of their rows in $M$ are zero, that is,
$x_{i}e_{i}^{T}\,.\,x_{j}e_{j}^{T}=0$. Now, we show that if $v$ and $w$ are
dominating vertices in $G$, then inner product between their rows in $M$ is
always nonzero. Suppose this is not true and there exist some pairs of
dominating vertices s.t. their inner products are equal to zero. Now
considering a proper diagonal matrix $D=diag(d_{1},d_{2},\ldots,d_{k})$, we
can make a new matrix $B=A(\bar{1},\,\bar{0})\,D$ s.t. $B^{T}\,B$ is a
$k\times k$ diagonal matrix and $B\,B^{T}$ is a $T\times T$ matrix with all
nonzero entries. Hence we arrive at the new vertex-clique incidence matrix
$\overline{M}=\left(\begin{array}[]{c}B\\\ Y\\\ \end{array}\right),$ where
$Y=diag(y_{1},y_{2},\ldots,y_{k})$ s.t. $\overline{M}\,\overline{M}^{T}\in
S(G)$ and $\overline{M}^{T}\,\overline{M}=aI_{k}$, for a positive $a$. This
completes the proof of the theorem. ∎

We now apply Theorem 4.1 to certain families of threshold graphs.

######  Theorem 4.2.

Let
$G\cong(\underbrace{0,\ldots,0}_{k_{1}},\underbrace{1,\ldots,1}_{t_{1}},\underbrace{0,\ldots,0}_{k_{2}},\underbrace{1,\ldots,1}_{t_{2}},\ldots,\underbrace{0,\ldots,0}_{k_{s}},\underbrace{1,\ldots,1}_{t_{s}})$
be a connected threshold graph with $n$ vertices and let $k_{i},t_{i},s\geq
1$. If $k_{i}\geq\sum_{j=i}^{s}t_{j}$ for an integer $i\in\\{2,\ldots,s\\}$,
then $q(G)\geq 3$.

###### Proof.

Since threshold graph $G$ is connected, we have $q(G)\geq 2$. Suppose
$q(G)=2$. Then there exists $A\in S(G)$ s.t. $A^{2}=I$. Now, let $B$ is a
submatrix of $A$ of order $n\times(1+k_{i})$, with rows indexed by all
vertices and columns indexed by $1+k_{i}$ isolated vertices, the first
isolated vertex together with $k_{i}$ related isolated vertices. Obviously,
since $A$ is orthogonal, $B$ is a column orthogonal matrix and then the
$t\times(1+k_{i})$ submatrix $B^{\prime}$ of $B$, where
$t=\sum_{j=i}^{s}t_{j}$. By our assumption, we have $1+k_{i}>t$, that is, the
matrix $B^{\prime}$ is a $t\times(1+k_{i})$ with the number of columns greater
than the number of rows, a contradiction since $B^{\prime}$ is column
orthogonal. Hence $q(G)\neq 2$. That is, $q(G)\geq 3$. ∎

######  Theorem 4.3.

Let $G$ be a connected threshold graph of order $n$ and trace $T$. If
$q(G)=2$, then $T\geq\lceil\frac{n}{2}\rceil$.

###### Proof.

Since $q(G)=2$, there exists $A\in S_{+}(G)$ such that $m(A)=(a,b)$ with
$\max\\{a,\,b\\}\leq T$. This gives $n=a+b\leq 2T$, and thus
$T\geq\lceil\frac{n}{2}\rceil$. ∎

This leads to the following result:

######  Corollary 4.4.

Let $G$ be a connected threshold graph of order $n$ and trace $T$. If
$T<\lceil\frac{n}{2}\rceil$, then $q(G)\geq 3$.

##  5 On $q(G)$ for specific families of threshold graphs

In this section we determine $q(G)$ for threshold graphs of the form
$G\cong(0,1,0,1,\ldots,0,1)$,
$G\cong(0,\underbrace{1,\ldots,1}_{t_{1}},0,\underbrace{1,\ldots,1}_{t_{2}},\ldots,0,\underbrace{1,\ldots,1}_{t_{s}})$
and for the special class of complete split graphs.

######  Theorem 5.1.

Let $G\cong(0,1,0,1,\ldots,0,1)$ be a threshold graph of order $n$. Then
$q(G)=3$. Moreover, for any supergraph $H$ of $G$ on the same vertex set
satisfies $q(H)\leq 3$.

###### Proof.

We consider the set $C$ of cliques in $G$ with each clique corresponding to
each zero in (or isolated vertex in $G$) in the creation sequence for $G$.
Clearly, $C$ is a minimum edge clique cover for $G$. Now, we form the vertex-
clique incidence matrix $M_{1}$ of $G$ corresponding to $C$:

$M_{1}=\left(\begin{array}[]{ccccccc}1&0&0&\ldots&0\\\ 1&0&0&\ldots&0\\\
1&2&0&\ldots&0\\\ 1&1&3&\ldots&0\\\ \vdots&\vdots&\ddots&\ddots&\vdots\\\
1&1&\ldots&1&t\\\ 0&1&0&\ldots&0\\\ 0&0&1&\ddots&\vdots\\\
\vdots&\vdots&\ddots&\ddots&0\\\ 0&0&\ldots&0&1\\\ \end{array}\right),$

where $t=\frac{n}{2}$ is the number of zeros in the creation sequence for $G$.
It is not difficult to see that the square of the length of the last column of
$M_{1}$ is $t^{2}+1$. We can arrange that the squares of the lengths of all
other columns also equal $t^{2}+1$ by setting a new element given by $x_{i}$
given in $i$th column in $M_{2}$ for $1\leq i\leq t-1$ as follows:

$M_{2}=\left(\begin{array}[]{ccccccc}x_{1}&0&0&\ldots&0\\\ 1&0&0&\ldots&0\\\
1&2&0&\ldots&0\\\ 1&1&3&\ldots&0\\\ \vdots&\vdots&\ddots&\ddots&\vdots\\\
1&1&\ldots&1&t\\\ 0&x_{2}&0&\ldots&0\\\ 0&0&x_{3}&\ldots&0\\\
\vdots&\vdots&\ddots&\ddots&\vdots\\\ 0&0&0&\ldots&1\\\ \end{array}\right).$

The matrix of $M_{2}^{T}M_{2}$ is a $t\times t$ matrix with each entry on the
main diagonal equal to $t^{2}+1$ and all off-diagonal entries equal to $t$.
Thus the spectrum of $M_{2}^{T}M_{2}$ is

$\mathrm{Spec}(M_{2}^{T}M_{2})=\left\\{t^{2}-t+1^{[t-1]},\,2t^{2}-t+1\right\\}.$

Then the spectrum of $A=M_{2}M_{2}^{T}$ is equal to

$\mathrm{Spec}(A)=\left\\{t^{2}-t+1^{[t-1]},\,2t^{2}-t+1,0^{[t]}\right\\}.$

Obviously, $A\in S(G)$, and hence $q(G)\leq 3$. Now, using Lemma 3.5 by
considering the unique distance $d$ between the unique pendant vertex and any
vertex other than the unique universal vertex, we arrive at $q(G)\geq 3$. Thus
$q(G)=3$ and the first part of the proof is complete.

It is not difficult to determine (using mathematical software, for example)
that $A$ has SSP and thus by Lemma 3.1, any supergraph $H$ of $G$ on the same
vertex set has a realization with the same spectrum as $A$, which gives
$q(H)\leq 3$. ∎

######  Theorem 5.2.

Let
$G\cong(0,\underbrace{1,\ldots,1}_{t_{1}},0,\underbrace{1,\ldots,1}_{t_{2}},\ldots,0,\underbrace{1,\ldots,1}_{t_{s}})$,
where $t_{i}\geq 1$ for $i=1,2,\ldots,s$, and $s\geq 2$. If $t_{s}=1$, then
$q(G)=3$; otherwise if $t_{s}\geq 2$, then $q(G)=2$.

###### Proof.

First we assume that $t_{s}=1$. By Lemma 3.5, $q(G)\geq 3$. On the other hand,
by Lemma 3.2 and Theorem 5.1 we have $q(G)\leq q(H)=3$, where
$H\cong(0,1,0,1,\ldots,0,1)$. Hence $q(G)=3$.

Next, we assume that $t_{s}\geq 2$. Let $H\cong(0,1,0,1,\ldots,0,1,0,1,1)$. A
vertex-clique incidence matrix of $H$ is as follows:

$M=\left(\begin{array}[]{cccccc}1&0&0&\ldots&0&0\\\ 1&-s+1&0&\ddots&0&0\\\
1&1&-s+2&0&\ddots&0\\\ \vdots&\vdots&\vdots&\ddots&\ddots&0\\\
1&1&1&1&\ldots&-1\\\ 1&1&1&1&\ldots&1\\\ 1&0&0&0&\ldots&0\\\
0&1&0&\ddots&\ddots&0\\\ 0&0&1&0&\ddots&\vdots\\\
\vdots&\vdots&\vdots&\ddots&\ddots&0\\\ 0&0&0&\ldots&1&0\\\
0&0&0&\ldots&0&1\\\ \end{array}\right).$

We have $A=MM^{T}\in S(H)$ and $M^{T}M=(s^{2}-s+1)\,I_{s}$. Thus
$\mathrm{Spec}(A)=\Big{\\{}0^{s+1},\,{s^{2}-s+1}^{[s]}\Big{\\}}$. Hence, Lemma
3.2 $q(G)\leq q(H)=2$ and consequently, $q(G)=2$. ∎

In the following we obtain the minimum number of distinct eigenvalues for
complete split graphs.

######  Theorem 5.3.

Let $G\cong(\underbrace{0,\ldots,0}_{k_{1}},\underbrace{1,\ldots,1}_{t_{1}})$,
where $t_{1},k_{1}\geq 1$. If $k_{1}\leq t_{1}$, then $q(G)=2$; otherwise
$q(G)=3$.

###### Proof.

By Theorem 4.1, $q(G)=2$ if and only if there exists a matrix $A\in S(G)$ such
that $A(\bar{1},\,\bar{0})$ is column orthogonal. For the threshold graph $G$,
the matrix $A(\bar{1},\,\bar{0})$ has the following form:

$A(\bar{1},\,\bar{0})=\left(\begin{array}[]{cccccc}a_{1}&b_{1}&\ldots&c_{1}\\\
a_{2}&b_{2}&\ddots&c_{2}\\\ \vdots&\vdots&\ddots&\vdots\\\
a_{t_{1}}&b_{t_{1}}&\ldots&c_{t_{1}}\\\ \end{array}\right),$

consisting of all nonzero entries. Such a matrix $A(\bar{1},\,\bar{0})$ allows
a column orthogonal matrix if $k_{1}\leq t_{1}$. Otherwise, $q(G)\geq 3$. This
with Lemma 3.2 gives $q(G)=3$. ∎

##  6 Threshold graphs with trace $T=2$

In this section, we completely characterize $q(G)$ for all connected threshold
graphs $G$ with trace equal to two. Note that any such graph must have at
least 3 vertices. If $G$ is a threshold graph with trace equal to two and has
3 vertices, then $G=K_{3}$, and $q(G)=2$. If such a graph has 4 vertices, then
either $G\cong(0,1,0,1)$ or $G\cong(0,0,1,1)$. In the later case $G$ is
isomorphic to the complete graph on 4 vertices with one edge removed, and it
is well-known that $q(G)=2$ in this case. For the former case, it follows that
$q(G)=3$ from [1]. For most of the results in this section, we assume that
$n\geq 5$.

We begin with a series of facts by considering specific trace two threshold
graphs.

######  Theorem 6.1.

Let $G\cong(\underbrace{0,\ldots,0}_{k},1,0,1)$, where $k\geq 1$. Then
$q(G)=3$.

###### Proof.

We assume that $H\cong(0,1,0,1)$ with a vertex set as $(1,2,4,3)$ with the
presented order respecting the order in the creation sequence. We consider the
following clique-incidence matrix of $H$:

$M=\left(\begin{array}[]{cccc}\sqrt{3}&0\\\ 1&0\\\ 1&2\\\ 0&1\\\
\end{array}\right).$

Then $M\,M^{T}\in S(H)$. On the other hand, $M^{T}\,M=5\,I_{2}+2\,A(K_{2})$,
where $A(K_{2})$ is the adjacency matrix of the complete graph of order 2.
Thus $\mathrm{Spec}(M^{T}\,M)=\\{7,\,3\\}$, and consequently,
$\mathrm{Spec}(M\,M^{T})=\\{7,\,3,\,0^{[2]}\\}$. The eigenvalue $3$ is also an
entry on the main diagonal of $M\,M^{T}$ corresponding to vertex 1. Then
applying Lemma 3.3 by duplicating vertex 1, we arrive at $q(G)\leq 3$. This
combined with Lemma 3.5 completes the proof of theorem. ∎

######  Theorem 6.2.

Let $G\cong(0,1,\underbrace{0,\ldots,0}_{k},1)$, where $k\geq 1$. Then
$q(G)=3$.

###### Proof.

We assume that $H\cong(0,1,0,1)$ with a vertex set as $(1,2,4,3)$ with the
presented order respecting the order in the creation sequence. We consider the
following clique-incidence matrix of $H$:

$M=\left(\begin{array}[]{cccc}1&0\\\ 1&0\\\ 1&1\\\ 0&\sqrt{2}\\\
\end{array}\right).$

Then $M\,M^{T}\in S(H)$. On the other hand, $M^{T}\,M=3\,I_{2}+A(K_{2})$,
where $A(K_{2})$ is the adjacency matrix of the complete graph of order 2.
Thus $\mathrm{Spec}(M^{T}\,M)=\\{4,\,2\\}$, and consequently,
$\mathrm{Spec}(M\,M^{T})=\\{4,\,2,\,0^{[2]}\\}$. The eigenvalue $2$ is also an
entry on the main diagonal of $M\,M^{T}$ corresponding to the vertex 4. Then
applying Lemma 3.3 by duplicating vertex 4, we arrive at $q(G)\leq 3$. This
combined with Lemma 3.5 completes the proof of theorem. ∎

######  Theorem 6.3.

Let $G\cong(0,0,1,\underbrace{0,\ldots,0}_{k},1)$ be a threshold graph of
order $n$ with $k\geq 1$. Then $q(G)=3$.

###### Proof.

Let $H\cong(0,0,1,0,1)$ be a threshold graph on five vertices. A vertex-clique
incidence matrix $M$ of $H$ is as follows:

$M=\left(\begin{array}[]{cccc}3&0&0\\\ 1&-3&0\\\ 1&1&-2\\\ 0&1&0\\\
0&0&\sqrt{7}\\\ \end{array}\right).$

The matrix $A=MM^{T}\in S(H)$, and the spectrum of $A$ is

$\mathrm{Spec}(A)=\\{13^{[2]},\,0^{[2]},\,7\\}.$

Then $q(H)\leq 3$. This with Lemma 3.5 gives $q(H)=3$. On the main diagonal of
$A$, the entry corresponding to the unique pendant vertex $v$ is equal to $7$
and since $7\in\mathrm{Spec}(A)$. Thus any threshold graph $G$ obtained from
$H$ with duplicating the pendant vertex $v$ as often as is required, has a
realization with the same spectrum as $A$ by Lemma 3.3. Then $q(G)\leq 3$.
Again using Lemma 3.5, we conclude $q(G)=3$. ∎

######  Theorem 6.4.

Let
$G\cong(\underbrace{0,\ldots,0}_{k_{1}},\underbrace{1,\ldots,1}_{t_{1}},\underbrace{0,\ldots,0}_{k_{2}},\underbrace{1,\ldots,1}_{t_{2}})$
be a threshold graph of order $n$ with $k_{1},\,k_{2},t_{1},t_{2}\geq 1$. Then
$q(G)\leq 4$.

###### Proof.

Let $H\cong(0,1,0,0,1)$ be a threshold graph on five vertices. A vertex-clique
incidence matrix $M$ of $H$ is as follows:

$M=\left(\begin{array}[]{cccc}1&0&0\\\ 1&0&0\\\ 1&1&1\\\ 0&1&0\\\ 0&0&1\\\
\end{array}\right).$

The matrix $A=MM^{T}\in S(H)$. The spectrum of $A$ is

$\mathrm{Spec}(A)=\\{4.4142,\,1.5857,\,1,\,0^{[2]}\\}.$

Then $q(H)\leq 4$. On the main diagonal of $A$, the entries corresponding to
the first and forth vertices in $H\cong(0,1,0,0,1)$ are equal to $1$ and since
$1\in\mathrm{Spec}(A)$, any threshold graph
$G^{\prime}\cong(\underbrace{0,\ldots,0}_{k_{1}},1,\underbrace{0,\ldots,0}_{k_{2}},1)$
obtained from $H$ by duplicating these vertices as needed, has a realization
with the same spectrum as $A$ using Lemma 3.3. Then $q(G^{\prime})\leq 4$.
Finally, applying Lemma 3.2, it follows that $q(G)\leq q(G^{\prime})\leq 4$.
Hence the proof is complete. ∎

Before we state and prove our main result in this section we preface that
discussion by alerting the reader that the threshold graph shown in Figure 1
is the only threshold graph on 7 vertices which attains $q(G)=4$ (see Section
10), all other threshold graphs $H$ on 7 vertices satisfy $q(H)\leq 3$.

$G$

Fig.1. The threshold graph $G$.

In the next result we state and prove the main theorem of this section.

######  Theorem 6.5.

Let
$G\cong(\underbrace{0,\ldots,0}_{k_{1}},1,\underbrace{0,\ldots,0}_{k_{2}},1)$
be a threshold graph of order $n\geq 5$ with $k_{1}\geq 1$ and $k_{2}\geq 0$.
Then

$q(G)=\begin{cases}3~{}~{}~{}~{}\mbox{if}\,k_{1}\in\\{1,\,2\\}~{}\mbox{or}~{}k_{2}\in\\{0,\,1\\},\\\
4~{}~{}~{}~{}\mbox{otherwise}.\end{cases}$

###### Proof.

Considering the values of the parameters $k_{1}$ and $k_{2}$, we may conclude
that $q(G)=3$ whenever $k_{1}\in\\{1,\,2\\}~{}\mbox{or}~{}k_{2}\in\\{0,\,1\\}$
by applying Theorems 5.3, 6.1, 6.2 and 6.3. So we may assume that the
parameters $k_{1}$ and $k_{2}$ fall outside of these ranges. Noting, Theorem
6.4, we have that any such threshold graph $G$ satisfies $q(G)\leq 4$.

The next step in the proof involves the particular trace 2 threshold graph
$G\cong(\underbrace{0,\ldots,0}_{k-1},1,0,0,1)$, with $k\geq 4$. We will show
that $q(G)=4$. By Lemma 3.5 we have $q(G)\geq 3$. We show that the equality is
not possible. If $q(G)=3$ then since we know that largest possible positive
semidefinite nullity is 2, since the trace of $G$ is 2. Furthermore, from [16]
we know that the largest possible multiplicity is $n-4$. Thus it follows that
the only possible allowed ordered multiplicity list for $A\in S(G)$ with
$q(A)=3$ is $(2,n-4,2)$. This follows since the multiplicities of the largest
and smallest eigenvalues is at most 2, as the clique cover number of $G$ is
the trace of $G$, which equals 2. Without loss of generality we may assume
such that $A=(a_{i,j})_{1\leq i,j\leq n}\in S(G)$ has spectrum

$\mathrm{Spec}(A)=\\{-\lambda^{[2]},\,0^{[n-4]},\,1^{[2]}\\},~{}~{}~{}~{}\mbox{where}~{}0<\lambda<1.$

The main diagonal entries $a_{i,i}$ must be equal to zero for $i=2,\ldots,k$,
otherwise the nullity of zero will be changed to $n-3$ by Lemma 3.4, which is
a contradiction with the fact $M(G)=n-4$ [16]. For convenience, we write $A$
in the following form:

$A=\left(\begin{array}[]{ccccccc}d_{0}&c_{1}&\cdots&c_{k-1}&c_{k}&0&0\\\
c_{1}&0&\cdots&0&c_{k+1}&0&0\\\ \vdots&0&\ddots&0&\vdots&\vdots&\vdots\\\
c_{k-1}&0&\cdots&0&c_{2k-1}&0&0\\\
c_{k}&c_{k+1}&\cdots&c_{2k-1}&d_{k}&c_{2k}&c_{2k+1}\\\
0&0&\cdots&0&c_{2k}&d_{k+1}&0\\\ 0&0&\cdots&0&c_{2k+1}&0&d_{k+2}\\\
\end{array}\right),$

where all $c_{j}$ are necessarily non-zero, $k=n-3$, and the last 3 vertices
correspond to the last three positions in the creation sequence for $G$ in
reverse order. Since $rank(A)=4$, then either $d_{k+1}=d_{k+2}=0$ or both
$d_{k+1}$ and $d_{k+2}$ are non-zero. Consequently, we consider these two
cases separately.

Case 1) $d_{k+1}=d_{k+2}=0$. First we show that

$-\lambda=d_{0}-1,~{}~{}\mbox{and}~{}~{}~{}d_{0}=d_{k}.$

To do this, we assume that $B=A(k+1)$. The spectrum of $B$ is

$\mathrm{Spec}(B)=\left\\{\frac{1}{2}d_{0}\pm\frac{1}{2}\sqrt{4\sum_{i=1}^{k-1}c_{i}^{2}+d_{0}^{2}},\,0^{[n-4]}\right\\}.$

Applying interlacing for $A$ and $B$ we obtain

$\displaystyle\frac{1}{2}d_{0}+\frac{1}{2}\sqrt{4\sum_{i=1}^{k-1}c_{i}^{2}+d_{0}^{2}}$
$\displaystyle=1$ (1)
$\displaystyle\frac{1}{2}d_{0}-\frac{1}{2}\sqrt{4\sum_{i=1}^{k-1}c_{i}^{2}+d_{0}^{2}}$
$\displaystyle=-\lambda.$

This proves $-\lambda=d_{0}-1$ and $\sum_{i=1}^{k-1}c_{i}^{2}=1-d_{0}$.
Considering the trace of $A$ we have $d_{0}+d_{k}=2(d_{0}-1)+2$ and then
$d_{0}=d_{k}$.

Again applying interlacing for $A$ and $C=A(1)$, we arrive at

$\sum_{i=k+1}^{2k+1}c_{i}^{2}=1-d_{0}.$ (2)

Comparing the coefficients of $x^{n-2}$ in the characteristic polynomial of
$A$ and $(x-d_{0}+1)^{2}\,(x-1)^{2}\,x^{n-4}$ we conclude that

$-\sum_{i=1}^{2k+1}c_{i}^{2}+d_{0}\,d_{k}=d_{0}^{2}+2d_{0}-2.$

This equation combined with the fact $d_{0}=d_{k}$ and (2) gives

$-[2(\sum_{i=1}^{k-1}c_{i}^{2})+c_{k}^{2}]=2d_{0}-2,$

which implies $c_{k}=0$, a contradiction.

Case 2) Both $d_{k+1}$ and $d_{k+2}$ are non-zero. Following as in the
beginning of Case 1 above, we may conclude that

$\displaystyle\frac{1}{2}d_{0}+\frac{1}{2}\sqrt{4\sum_{i=1}^{k-1}c_{i}^{2}+d_{0}^{2}}$
$\displaystyle=1$ (3)
$\displaystyle\frac{1}{2}d_{0}-\frac{1}{2}\sqrt{4\sum_{i=1}^{k-1}c_{i}^{2}+d_{0}^{2}}$
$\displaystyle=-\lambda.$

This follows since if the smallest or largest eigenvalue of a symmetric matrix
coincides with a main diagonal entry, then the remainder of the row and column
containing that diagonal entry must be zero. Furthermore it now follows from
interlacing applied for $A$ and $A(k+1)$, that $d_{k+1}$ and $d_{k+2}$ have
different signs. We may assume that $d_{k+1}<0<d_{k+2}$. This proves
$-\lambda=d_{0}-1$ and $\sum_{i=1}^{k-1}c_{i}^{2}=1-d_{0}$. Furthermore, we
claim the following conditions hold for the matrix $A$: $c_{i+k}=bc_{i}$, for
some $b\neq 0$ and $i=1,2,\ldots,k-1$;
$d_{k}=\frac{c_{2k}^{2}}{d_{k+1}}+\frac{c_{2k+1}^{2}}{d_{k+2}}+2bc_{k}-b^{2}d_{0}$,
and finally $c_{k}=b(d_{0}-1)$; The first two conditions follow by applying
elementary row/column operations to $A$ and noting that the rank of $A$ is 4
and that both $d_{k+1}$ and $d_{k+2}$ are non-zero. To verify the third
condition, since $-\lambda$ and 1 are multiple eigenvalues of $A$, we have
$-\lambda$ and 1 are both eigenvalues of $A(k+1)$. Since $A(k+1)$ is a direct
sum of a matrix $C$ and a $2\times 2$ diagonal matrix consisting of main
diagonal entries $d_{k+1}$ and $d_{k+2}$, it follows that $-\lambda$ and 1 are
both eigenvalues of $C$. Applying row and column operations to the matrix
$A(k+2,k+3)-I$, we may conclude that $c_{k}=b(d_{0}-1)$.

Label the two pendant vertices in $G$ as $x$ and $y$. We let $A(x)$ (and
$A(y)$) denote the principal submatrix of $A$ obtained by deleting the row and
column corresponding to $x$ ($y$). Further, let $B=A(x,y)$. Under the
assumptions above it follows that the rank of $B$ is at most 3, and if we let
$B(v)$ denote the principal submatrix of $B$ obtained by deleting the last row
and column of $B$, then the rank of $B(v)$ is 2. Now define
$f_{x}(z)=\det(zI-A(x))$, and $f_{y}(z)=\det(zI-A(y))$. Applying basic
properties of determinants we have

$f_{x}(z)=(z-d_{k+2})f_{B}(z)-c_{2k+1}^{2}f_{B(v)}(z),\;\;\;\;f_{y}(z)=(z-d_{k+1})f_{B}(z)-c_{2k}^{2}f_{B(v)}(z),$

where $f_{B}$ and $f_{B(v)}$ are the characteristic polynomials of $B$ and
$B(v)$ respectively. Since $-\lambda$ is a multiple eigenvalue of $A$ we have
$f_{x}(-\lambda)=f_{y}(-\lambda)=0$. Similarly, since neither $d_{k+1}$ nor
$d_{k+2}$ can equal $-\lambda$ it follows that $-\lambda$ is an eigenvalue of
$B(v)$. Thus

$0=f_{x}(-\lambda)-f_{y}(-\lambda)=f_{B}(-\lambda)(d_{k+1}-d_{k+2}).$

As noted above that rank of $B$ is at most 3 and so the characteristic
polynomial of $B$ has the form:

$f_{B}(z)=z^{k+1}-(d_{0}+d_{k})z^{k}+\alpha z^{k-1}+\beta z^{k-2},$

where

$\alpha=-\sum_{i\neq
k}c_{i}^{2}+d_{0}d_{k}-c_{k}^{2},\;\;\;\beta=\sum_{i=1}^{k-1}(2c_{i}c_{k}c_{k+i}-d_{k}c_{i}^{2}-d_{0}c_{k+1}^{2}).$

Using the established conditions on the entries of $A$ above, we may simplify
both $\alpha$ and $\beta$ as follows:

$\alpha=-(1-d_{0}+b^{2}(1-d_{0}))-d_{0}d_{k}-b^{2}(d_{0}-1)^{2},\;\;\;\beta=(1-d_{0})(b^{2}(2(d_{0}-1)-d_{0})-d_{k}).$

Using these simplified equations, we may now write:

$f_{B}(-\lambda)(d_{k+1}-d_{k+2})=(d_{k+1}-d_{k+2})(d_{0}-1)^{k-1}(b)^{2}(d_{0}-2)^{2}.$

A contradiction arises since the latter expression cannot equal 0. Thus no
such $A\in S(G)$ with $q(A)=3$ exists, so $q(G)=4$.

More generally, assume that
$G\cong(\underbrace{0,\ldots,0}_{k_{1}},1,\underbrace{0,\ldots,0}_{k_{2}},1)$,
where $k_{2}>2$. Suppose there exists $A\in S(G)$ with $q(A)=3$. Then, as
before we may assume that the rank of $A$ is 4 and that the spectrum of $A$ is

$\mathrm{Spec}(A)=\\{-\lambda^{[2]},\,0^{[n-4]},\,1^{[2]}\\},~{}~{}~{}~{}\mbox{where}~{}0<\lambda<1.$

Now suppose all of the diagonal entries corresponding to the pendant vertices
of $G$ are zero in $A$. Then, as in Case 1 above, we arrive at a
contradiction. On the other hand, if at least one main diagonal entry
corresponding to a pendant vertex is nonzero, then there are at least two such
nonzero main diagonal entries. However, in this case it follows that the rank
of $A$ is at least 5 since the number of such pendant vertices is at least 3.
This completes the proof. ∎

######  Corollary 6.6.

Let
$G\cong(0,\underbrace{1,\ldots,1}_{t_{1}},\underbrace{0,\ldots,0}_{k_{2}},1)$,
where $t_{1},\,k_{2}\geq 1$ or let
$G\cong(0,1,\underbrace{0,\ldots,0}_{k_{2}},\underbrace{1,\ldots,1}_{t_{2}})$,
where $t_{t},\,k_{2}\geq 1$ Then in either case we have $q(G)=3$.

##  7 Threshold graphs with trace $T=3$

In this section, we study $q(G)$ for connected threshold graphs with trace
equal to three.

######  Theorem 7.1.

Let
$G\cong(\underbrace{0,\ldots,0}_{k_{1}},1,0,1,\underbrace{0,\ldots,0}_{k_{2}},1)$,
where $k_{1},\,k_{2}\geq 1$. Then $q(G)=3$.

###### Proof.

We assume that $H\cong(0,1,0,1,0,1)$ with a vertex set labelled as
$(1,2,5,3,6,4)$ respecting the order of vertices in its creation sequence. We
consider the following clique-incidence matrix of $H$:

$M=\left(\begin{array}[]{cccc}\sqrt{7}&0&0\\\ \sqrt{2}&0&0\\\ 1&-3&0\\\
1&1&-2\\\ 0&1&0\\\ 0&0&\sqrt{7}\\\ \end{array}\right).$

Observe that $M\,M^{T}\in S(H)$, and note that
$M^{T}\,M=11\,I_{3}-2\,A(K_{3})$, where $A(K_{3})$ is the adjacency matrix of
the complete graph of order 3. Hence
$\mathrm{Spec}(M^{T}\,M)=\\{13^{[2]},\,7\\}$, and consequently,
$\mathrm{Spec}(M\,M^{T})=\\{13^{[2]},\,7,\,0^{[3]}\\}$. The eigenvalue $7$ is
also an entry on the main diagonal of $M\,M^{T}$ corresponding to the vertices
1 and 6. Applying Lemma 3.3 by duplicating the vertices 1 and 6, we arrive at
$q(G)\leq 3$. This combined with Lemma 3.5 completes the proof of theorem. ∎

######  Theorem 7.2.

Let $G\cong(0,1,\underbrace{0,\ldots,0}_{k},1,0,1)$, where $k\geq 1$. Then
$q(G)=3$.

###### Proof.

We assume that $H\cong(0,1,0,1,0,1)$ with a vertex set labelled as
$(1,2,5,3,6,4)$ respecting the order of vertices in its creation sequence. We
consider the following clique-incidence matrix of $H$:

$M=\left(\begin{array}[]{cccc}\sqrt{2}&0&0\\\ 1&0&0\\\ 1&1&0\\\ 1&1&2\\\
0&\sqrt{3}&0\\\ 0&0&1\\\ \end{array}\right).$

The remainder of the proof is very similar to the previous proof and is
omitted. ∎

######  Theorem 7.3.

Let
$G\cong(\underbrace{0,\ldots,0}_{k_{1}},1,\underbrace{0,\ldots,0}_{k_{2}},1,\underbrace{0,\ldots,0}_{k_{3}},1)$
be a threshold graph of order $n$ with $k_{1},\,k_{2},\,k_{3}\geq 1$. Then
$q(G)\leq 4$.

###### Proof.

Let $H\cong(0,1,0,1,0,0,1)$ be a threshold graph on seven vertices. A vertex-
clique incidence matrix $M$ associated with $H$ is as follows:

$M=\left(\begin{array}[]{cccc}1&0&0&0\\\ 1&0&0&0\\\ 1&1&0&0\\\ 1&1&1&1\\\
0&\sqrt{2}&0&0\\\ 0&0&1&0\\\ 0&0&0&1\\\ \end{array}\right).$

The matrix $A=MM^{T}\in S(H)$, and the spectrum of $A$

$\mathrm{Spec}(A)=\\{7,\,2^{[2]},\,0^{[3]},\,1\\}.$

Thus $q(H)\leq 4$. On the main diagonal of $A$, the entries corresponding to
the first, sixth and seventh vertices in $H\cong(0,1,0,1,0,0,1)$ are equal to
$1$ and $2$ and since $\\{1,\,2\\}\subseteq\mathrm{Spec}(A)$, any threshold
graph $G$ obtained from $H$ by duplicating these vertices as often as needed,
has a realization with the same spectrum as $A$ by Lemma 3.3. Then $q(G)\leq
4$, which completes the proof. ∎

##  8 Threshold graphs with trace $T=|G|-2$

In this section, we calculate $q(G)$ for all threshold graphs $G$ with trace
equal to $n-2$, where $n$ is the number of vertices of $G$.

######  Theorem 8.1.

Let
$G\cong(0,\underbrace{1,\ldots,1}_{t_{1}},0,\underbrace{1,\ldots,1}_{t_{2}})$,
where $t_{1}\geq 0$ and $t_{2}\geq 1$.

  1. 1.

If $t_{1}=0$ and $t_{2}\geq 2$ then $q(G)=2$;

  2. 2.

if $t_{1}=0$ and $t_{2}=1$, then $q(G)=3$;

  3. 3.

if $t_{1}\geq 1$ and $t_{2}=1$, then $q(G)=3$; and

  4. 4.

if $t_{1}\geq 1$ and $t_{2}\geq 2$, then $q(G)=2$.

###### Proof.

The result for the case $t_{1}=0$, is directly confirmed by Theorem 5.3. Now,
suppose $t_{1}\geq 1$. First assume that $t_{2}=1$. Then by Lemma 3.5 , we
have $q(G)\geq 1+d=3$. On the other hand, by Lemma 3.2, $q(G)\leq
q(0,1,0,1)=3$, which proves the desired result in this case. Second, assume
that $t_{2}\geq 2$. Consider the graph $H\cong(0,1,0,1,1)$ with the following
vertex-clique incidence matrix:

$M=\left(\begin{array}[]{cc}1&0\\\ 2&1\\\ -2&1\\\ 1&0\\\ 0&\sqrt{8}\\\
\end{array}\right).$

Then $A=M\,M^{T}\in S(H)$ and $M^{T}\,M=10\,I_{2}$. Hence
$\mathrm{Spec}(A)=\\{0^{[3]},10^{[2]}\\}$ and consequently, $q(H)=2$. By Lemma
3.2 we conclude that $q(G)\leq q(H)=2$ and thus $q(G)=2$. ∎

##  9 Threshold graphs with trace $T=|G|-3$

In this section, we compute the values of $q(G)$ for all connected threshold
graphs $G$ with trace equal to $n-3$, where $n$ is the number of vertices of
$G$.

######  Theorem 9.1.

Let $G$ be a connected threshold graph with $n$ vertices and trace $T=n-3$.

  1. 1.

For

$G\cong(0,\underbrace{1,\ldots,1}_{t_{1}},0,\underbrace{1,\ldots,1}_{t_{2}},0,\underbrace{1,\ldots,1}_{t_{3}}),$

we have $q(G)=3$ if $t_{3}=1$ and $q(G)=2$, otherwise;

  2. 2.

for $G\cong(0,0,0,\underbrace{1,\ldots,1}_{t_{1}})$, $q(G)=2$ if $t_{1}\geq
3$, and $q(G)=3$ if $t_{1}=1,2$;

  3. 3.

for
$G\cong(0,0,\underbrace{1,\ldots,1}_{t_{1}},0,\underbrace{1,\ldots,1}_{t_{2}})$,
$q(G)=3$ if $t_{2}=1$ and $q(G)=2$, if $t_{2}\geq 2$; and

  4. 4.

for
$G\cong(0,\underbrace{1,\ldots,1}_{t_{1}},0,0,\underbrace{1,\ldots,1}_{t_{2}})$,
$q(G)=3$ if $t_{2}=1,2$ and $q(G)=2$ if $t_{2}\geq 3$.

###### Proof.

For the threshold graph
$G\cong(0,\underbrace{1,\ldots,1}_{t_{1}},0,\underbrace{1,\ldots,1}_{t_{2}},0,\underbrace{1,\ldots,1}_{t_{3}})$
with $t_{i}\geq 1$, the desired conclusions follow from Theorem 5.2.

For the threshold graph $G\cong(0,0,0,\underbrace{1,\ldots,1}_{t_{1}})$, the
conclusions follow from Theorem 5.3.

Now let
$G\cong(0,0,\underbrace{1,\ldots,1}_{t_{1}},0,\underbrace{1,\ldots,1}_{t_{2}})$
with $t_{2}=1$. By Lemma 3.5 , we have $q(G)\geq 1+d=3$. On the other hand, by
Lemma 3.2 and Theorem 6.5, $q(G)\leq q(0,0,1,0,1)=3$. This gives $q(G)=3$.
Otherwise, $t_{2}\geq 2$. Now, consider the graph $H\cong(0,0,1,0,1,1)$ with
the following vertex-clique incidence matrix:

$M=\left(\begin{array}[]{ccc}1&-2&0\\\ 1&1&-1\\\ 1&1&1\\\ 2&0&0\\\ 0&1&0\\\
0&0&\sqrt{5}\\\ \end{array}\right).$

Then $A=M\,M^{T}\in S(H)$ and $M^{T}\,M=7\,I_{3}$. Hence
$\mathrm{Spec}(A)=\\{0^{[3]},7^{[3]}\\}$ and consequently, $q(H)=2$. Now, by
Lemma 3.2 we conclude that $q(G)\leq q(H)=2$ or $q(G)=2$.

Finally, let
$G\cong(0,\underbrace{1,\ldots,1}_{t_{1}},0,0,\underbrace{1,\ldots,1}_{t_{2}}).$
If $t_{2}=1$, then by Lemma 3.5 , we have $q(G)\geq 3$. On the other hand, by
Lemma 3.2 and Theorem 6.5, $q(G)\leq q(0,1,0,0,1)=3$. This gives $q(G)=3$. If
$t_{2}=2$, then by Theorem 4.1, $q(G)=2$ if and only if there exists a matrix
$A\in S(G)$ such that $A(\bar{1},\,\bar{0})$ is column orthogonal. For the
threshold graph $G$, the matrix $A(\bar{1},\,\bar{0})$ has the following form:

$A(\bar{1},\,\bar{0})=\left(\begin{array}[]{cccccc}a_{1}&0&0\\\
\vdots&\vdots&\vdots\\\ a_{t_{1}}&0&0\\\ a_{t_{1}+1}&b_{1}&c_{1}\\\
a_{t_{1}+2}&b_{2}&c_{2}\\\ \end{array}\right),$

where all variables above are required to be nonzero. Obviously,
$A(\bar{1},\,\bar{0})$ allows a column orthogonal matrix if and only if
$\left(\begin{array}[]{cccccc}a_{t_{1}+1}&b_{1}&c_{1}\\\
a_{t_{1}+2}&b_{2}&c_{2}\\\ \end{array}\right)$ is column orthogonal, which is
impossible as all entries are required to be nonzero. Then $q(G)\geq 3$. This
with Lemma 3.5 and Theorem 6.5 gives $q(G)=3$.

If $t_{2}\geq 3$, we consider the graph $H\cong(0,1,0,0,1,1,1)$. Again
$q(H)=2$ if and only if there exists a matrix $A\in S(H)$ such that
$A(\bar{1},\,\bar{0})$ is column orthogonal.

For the threshold graph $H$, the matrix $A(\bar{1},\,\bar{0})$ has the
following form:

$A(\bar{1},\,\bar{0})=\left(\begin{array}[]{cccccc}a_{1}&0&0\\\
a_{2}&b_{2}&c_{2}\\\ a_{3}&b_{3}&c_{3}\\\ a_{4}&b_{4}&c_{4}\\\
\end{array}\right),$

where all variables above are required to be nonzero. It is easy to check that
$A(\bar{1},\,\bar{0})$ allows a column orthogonal matrix if and only if
$\left(\begin{array}[]{ccc}a_{2}&b_{2}&c_{2}\\\ a_{3}&b_{3}&c_{3}\\\
a_{4}&b_{4}&c_{4}\\\ \end{array}\right)$ is column orthogonal which is
possible. Then $q(H)=2$. This with Lemma 3.2 gives $q(G)\leq q(H)=2$, that is,
$q(G)=2$. ∎

##  10 Threshold graphs with $7$ vertices

In this section, we determine the values of $q(G)$ for all connected threshold
graphs $G$ with $7$ vertices.

The list of all connected threshold graphs $G$ of order $7$ along with their
value $q(G)$ is given below.
Index Creation Sequence $q(G)$ Explanations 1 (0, 0, 0, 0, 0, 0, 1) 3 Star
graph 2 (0, 1, 0, 0, 0, 0, 1) 3 Thm 6.5 3 (0, 0, 1, 0, 0, 0, 1) 3 Thm 6.5 4
(0, 0, 0, 1, 0, 0, 1) 4 Thm 6.5 5 (0, 0, 0, 0, 1, 0, 1) 3 Thm 6.5 6 (0, 0, 0,
0, 0, 1, 1) 3 Thm 6.5 7 (0, 1, 1, 0, 0, 0, 1) 3 Corollary 6.6 8 (0, 1, 0, 1,
0, 0, 1) 3 Thm 7.1 9 (0, 1, 0, 0, 1, 0, 1) 3 Thm 7.2 10 (0, 1, 0, 0, 0, 1, 1)
3 Lemma 3.2 & Corollaries 4.4 & 4.4 11 (0, 0, 1, 1, 0, 0, 1) 3 Thm 6.5 &
Lemmas 3.5 & 3.2 12 (0, 0, 1, 0, 1, 0, 1) 3 Thm 7.1 13 (0, 0, 1, 0, 0, 1, 1) 3
Lemma 3.2 & Corollary 4.4 14 (0, 0, 0, 1, 1, 0, 1) 3 Thm 6.5 & Lemmas 3.5 &
3.2 15 (0, 0, 0, 1, 0, 1, 1) 3 Thm 6.5 & Lemma 3.2 & Corollary 4.4 16 (0, 0,
0, 0, 1, 1, 1) 3 Lemma 3.2 & Corollary 4.4 17 (0, 1, 1, 1, 0, 0, 1) 3 Thm 6.5
& Lemma 3.2 18 (0, 1, 1, 0, 1, 0, 1) 3 Thm 5.1 & Lemma 3.2 19 (0, 1, 1, 0, 0,
1, 1) 3 Thm 9.1 20 (0, 1, 0, 1, 1, 0, 1) 3 Thm 5.1 & Lemma 3.2 21 (0, 1, 0, 1,
0, 1, 1) 2 Thm 9.1 22 (0, 1, 0, 0, 1, 1, 1) 2 Thm 9.1 23 (0, 0, 1, 1, 1, 0, 1)
3 Thm 6.5 & Lemma 3.2 24 (0, 0, 1, 1, 0, 1, 1) 2 Thm 9.1 25 (0, 0, 1, 0, 1, 1,
1) 2 Thm 9.1 26 (0, 0, 0, 1, 1, 1, 1) 2 Thm 5.3 27 (0, 1, 0, 1, 1, 1, 1) 2 Thm
8.1 28 (0, 1, 1, 0, 1, 1, 1) 2 Thm 8.1 29 (0, 1, 1, 1, 0, 1, 1) 2 Thm 8.1 30
(0, 1, 1, 1, 1, 0, 1) 3 Lemmas 3.5 & 3.2 31 (0, 1, 1, 1, 1, 1, 1) 2 Complete
graph

##  11 Threshold graphs with $8$ vertices

In this section, we determine the values of $q(G)$ for all connected threshold
graphs $G$ on $8$ vertices with two exceptions. For this, we need the
following additional results.

######  Proposition 11.1.

Let $G_{1}\cong(0,\,0,\,1,\,0,\,0,\,1,\,0,\,1)$ and
$G_{2}\cong(0,\,0,\,0,\,1,\,0,\,0,\,1,\,1)$. Then $q(G_{1})=q(G_{2})=3$.

###### Proof.

Suppose that $H$ is the graph with the following vertex-clique incidence
matrix:

$M=\left(\begin{array}[]{ccccc}\sqrt{8}&0&0&0&0\\\ 1&-\sqrt{2}&0&0&0\\\
\sqrt{2}&1&0&0&0\\\ 0&1&1&1&0\\\ 0&0&\sqrt{3}&0&0\\\ 0&0&0&\sqrt{3}&0\\\
0&1&1&1&2\\\ 0&0&0&0&1\\\ \end{array}\right).$

Then $A=M\,M^{T}\in S(H)$. The matrix $A$ has SSP with the spectrum of
$\mathrm{Spec}(A)=\\{0^{[3]},\,3^{[3]},\,11^{[2]}\\}$ and consequently,
$q(H)=3$. The threshold graphs $G_{1}$ and $G_{2}$ are supergraphs of $H$ with
the same vertex set, which implies $q(G_{i})\leq 3$ for $i=1,2$, by Lemma 3.1.
This with Corollary 4.4 gives the required result. ∎

######  Proposition 11.2.

Let $G\cong(0,\,1,\,0,\,0,\,1,\,0,\,1,\,1)$. Then $q(G)=3$.

###### Proof.

Let $A\in S(G)$ and $A(\bar{1},\,\bar{0})$ be the submatrix of $A$ with rows
and columns corresponding to dominating and isolated vertices in $G$,
respectively. Then this submatrix has the following form:

$A(\bar{1},\,\bar{0})=\left(\begin{array}[]{cccc}c_{1}&0&0&0\\\
c_{2}&c_{3}&c_{4}&0\\\ c_{5}&c_{6}&c_{7}&c_{8}\\\
c_{9}&c_{10}&c_{11}&c_{12}\\\ \end{array}\right)$

with all nonzero entries $c_{j}$. It can be easily deduced that
$A(\bar{1},\,\bar{0})$ does not allow a column orthogonal matrix, so $q(G)\geq
3$ by Theorem 4.1. Now apply Theorem 7.2 and Lemma 3.2, the desired result is
obtained. ∎

######  Proposition 11.3.

Let $G\cong(0,\,0,\,1,\,0,\,1,\,0,\,1,\,1)$. Then $q(G)=2$.

###### Proof.

Let $A\in S(G)$ and $A(\bar{1},\,\bar{0})$ be the submatrix of $A$ with rows
and columns corresponding to dominating and isolated vertices in $G$,
respectively. Consider

$A(\bar{1},\,\bar{0})=\left(\begin{array}[]{cccc}1&-3&0&0\\\ 1&1&-2&0\\\
1&1&1&-1\\\ 1&1&1&1\\\ \end{array}\right).$

Since $A(\bar{1},\,\bar{0})$ is column orthogonal, by Theorem 4.1, $q(G)=2$. ∎

######  Proposition 11.4.

Let $G\cong(0,\,0,\,1,\,0,\,0,\,1,\,1,\,1)$. Then $q(G)=2$.

###### Proof.

Let $A\in S(G)$ and $A(\bar{1},\,\bar{0})$ be the submatrix of $A$ with rows
and columns corresponding to dominating and isolated vertices in $G$,
respectively. Then this submatrix must have the following form:

$B=A(\bar{1},\,\bar{0})=\left(\begin{array}[]{cccc}c_{0}&c_{1}&0&0\\\
c_{2}&c_{3}&c_{4}&c_{5}\\\ c_{6}&c_{7}&c_{8}&c_{9}\\\
c_{10}&c_{11}&c_{12}&c_{13}\\\ \end{array}\right),$

where all $c_{i}$ are required to be nonzero. It can be easily determined that
the $3\times 4$ submatrix $B(1;)$ obtained from $B$ with removal of its first
row, allows a column orthogonal matrix. Then considering appropriate values
for $c_{0}$ and $c_{1}$ under which
$c_{0}\,c_{1}=-(c_{2}c_{3}+c_{6}c_{7}+c_{10}c_{11})$ we arrive at the column
orthogonal matrix $B$. This with Theorem 4.1 gives $q(G)=2$. ∎

######  Proposition 11.5.

Let $G\cong(0,\,0,\,0,\,1,\,1,\,0,\,1,\,1)$. Then $q(G)=2$.

###### Proof.

Let $A\in S(G)$ and $A(\bar{1},\,\bar{0})$ be the submatrix of $A$ with rows
and columns corresponding to dominating and isolated vertices in $G$,
respectively. Then consider

$A(\bar{1},\,\bar{0})=\left(\begin{array}[]{cccc}1&3/2&9/2&0\\\
2&1/2&-7/2&0\\\ 1/2&-1&1&2\\\ -1&2&-2&1\\\ \end{array}\right).$

Since $A(\bar{1},\,\bar{0})$ is column orthogonal, by Theorem 4.1, it follows
that $q(G)=2$. ∎

######  Proposition 11.6.

Let $G\cong(0,\,0,\,0,\,1,\,0,\,1,\,1,\,1)$. Then $q(G)=2$.

###### Proof.

Suppose that $H$ is the graph given in Proposition 11.5. Using
$A(\bar{1},\,\bar{0})$ used in the proof of Proposition 11.5, we can create
the following vertex-clique incidence matrix for $H$:

$M=\left(\begin{array}[]{ccccc}1&3/2&9/2&0\\\ 2&1/2&-7/2&0\\\ 1/2&-1&1&2\\\
-1&2&-2&1\\\ 1/2\sqrt{129}&0&0&0\\\ 0&\sqrt{31}&0&0\\\ 0&0&1&0\\\
0&0&0&\sqrt{67/2}\\\ \end{array}\right).$

Then $A=M\,M^{T}\in S(H)$. The matrix $A$ has SSP with the spectrum of
$\mathrm{Spec}(A)=\\{{\frac{77}{2}}^{[4]},\,0^{[4]}\\}$ and consequently,
$q(H)=2$. The threshold graph $G$ is a supergraph of $H$ and then $q(G)\leq
2$, by Lemma 3.1. This with the fact that for any connected graph $G$,
$q(G)\geq 2$ gives the required result. ∎

The list of connected threshold graphs of order $8$ with associated values of
$q(G)$ are listed below with two exceptions.
Index Creation Sequence $q(G)$ Explanations 1 (0, 0, 0, 0, 0, 0, 0, 1) 3 Star
graph 2 (0, 1, 0, 0, 0, 0, 0, 1) 3 Corollary 6.6 3 (0, 0, 1, 0, 0, 0, 0, 1) 3
Thm 6.5 4 (0, 0, 0, 1, 0, 0, 0, 1) 4 Thm 6.5 5 (0, 0, 0, 0, 1, 0, 0, 1) 4 Thm
6.5 6 (0, 0, 0, 0, 0, 1, 0, 1) 3 Thm 6.5 7 (0, 0, 0, 0, 0, 0, 1, 1) 3 Lemma
3.2 & Corollary 4.4 8 (0, 1, 1, 0, 0, 0, 0, 1) 3 Corollary 6.6 9 (0, 1, 0, 1,
0, 0, 0, 1) 3 Thm 7.1 10 (0, 1, 0, 0, 1, 0, 0, 1) 3 or 4 Corollary 4.4 & Thm
7.3 11 (0, 1, 0, 0, 0, 1, 0, 1) 3 Thm 7.2 12 (0, 1, 0, 0, 0, 0, 1, 1) 3
Corollaries 6.6 & 4.4 & Lemma 3.2 13 (0, 0, 1, 1, 0, 0, 0, 1) 3 Lemma 3.5 &
Corollary 4.4 & Thm 6.5 14 (0, 0, 1, 0, 1, 0, 0, 1) 3 Thm 7.1 15 (0, 0, 1, 0,
0, 1, 0, 1) 3 Prop 11.1 16 (0, 0, 1, 0, 0, 0, 1, 1) 3 Lemma 3.2 & Corollary
4.4 & Thm 6.5 17 (0, 0, 0, 1, 1, 0, 0, 1) 3 or 4 Corollary 4.4 & Thm 7.3 18
(0, 0, 0, 1, 0, 1, 0, 1) 3 Thm 7.1 19 (0, 0, 0, 1, 0, 0, 1, 1) 3 Prop 11.1 20
(0, 0, 0, 0, 1, 1, 0, 1) 3 Corollary 4.4 & Thm 6.5 21 (0, 0, 0, 0, 1, 0, 1, 1)
3 Corollary 4.4 & Thm 6.5 22 (0, 0, 0, 0, 0, 1, 1, 1) 3 Lemma 3.2 & Corollary
4.4 23 (0, 1, 1, 1, 0, 0, 0, 1) 3 Lemmas 3.5 & 3.2 & Thm 6.5 24 (0, 1, 1, 0,
1, 0, 0, 1) 3 Lemmas 3.5 & 3.2 & Thm 7.1 25 (0, 1, 1, 0, 0, 1, 0, 1) 3 Lemmas
3.5 & 3.2 & Thm 7.2 26 (0, 1, 1, 0, 0, 0, 1, 1) 3 Lemma 3.2 & Thms 6.5 & 4.2
27 (0, 1, 0, 1, 1, 0, 0, 1) 3 Lemmas 3.5 & 3.2 & Thm 7.1 28 (0, 1, 0, 1, 0, 1,
0, 1) 3 Thm 5.1 29 (0, 1, 0, 1, 0, 0, 1, 1) 3 Lemma 3.5 & Thms 7.1 & 4.2 30
(0, 1, 0, 0, 1, 1, 0, 1) 3 Lemmas 3.5 & 3.2 & Thm 7.2 31 (0, 1, 0, 0, 1, 0, 1,
1) 3 Prop 11.2 32 (0, 1, 0, 0, 0, 1, 1, 1) 3 Lemma 3.2 & Thms 6.5 & 4.2 33 (0,
0, 1, 1, 1, 0, 0, 1) 3 Lemmas 3.5 & 3.2 & Thm 6.5 34 (0, 0, 1, 1, 0, 1, 0, 1)
3 Lemmas 3.5 & 3.2 & Thm 7.1 35 (0, 0, 1, 1, 0, 0, 1, 1) 3 Lemma 3.2 & Thms
6.5 & 4.2 36 (0, 0, 1, 0, 1, 1, 0, 1) 3 Lemma 3.5 & Thm 7.1 37 (0, 0, 1, 0, 1,
0, 1, 1) 2 Prop 11.3 38 (0, 0, 1, 0, 0, 1, 1, 1) 2 Prop 11.4 39 (0, 0, 0, 1,
1, 1, 0, 1) 3 Lemmas 3.5 & 3.2 & Thm 6.5 40 (0, 0, 0, 1, 1, 0, 1, 1) 2 Prop
11.5 41 (0, 0, 0, 1, 0, 1, 1, 1) 2 Prop 11.6 42 (0, 0, 0, 0, 1, 1, 1, 1) 3 Thm
5.3 43 (0, 1, 1, 1, 1, 0, 0, 1) 3 Thm 9.1 44 (0, 1, 1, 1, 0, 1, 0, 1) 3 Thm
9.1 45 (0, 1, 1, 1, 0, 0, 1, 1) 3 Thm 9.1 46 (0, 1, 1, 0, 1, 1, 0, 1) 3 Thm
9.1 47 (0, 1, 1, 0, 1, 0, 1, 1) 2 Thm 9.1 48 (0, 1, 1, 0, 0, 1, 1, 1) 2 Thm
9.1 49 (0, 1, 0, 1, 1, 1, 0, 1) 3 Thm 9.1 50 (0, 1, 0, 1, 1, 0, 1, 1) 2 Thm
9.1 51 (0, 1, 0, 1, 0, 1, 1, 1) 2 Thm 9.1 52 (0, 1, 0, 0, 1, 1, 1, 1) 2 Thm
9.1 53 (0, 0, 1, 1, 1, 1, 0, 1) 3 Thm 9.1 54 (0, 0, 1, 1, 1, 0, 1, 1) 2 Thm
9.1 55 (0, 0, 1, 1, 0, 1, 1, 1) 2 Thm 9.1 56 (0, 0, 1, 0, 1, 1, 1, 1) 2 Thm
9.1 57 (0, 0, 0, 1, 1, 1, 1, 1) 2 Thm 9.1 58 (0, 1, 1, 1, 1, 1, 0, 1) 3 Thm
8.1 59 (0, 1, 1, 1, 1, 0, 1, 1) 2 Thm 8.1 60 (0, 1, 1, 1, 0, 1, 1, 1) 2 Thm
8.1 61 (0, 1, 1, 0, 1, 1, 1, 1) 2 Thm 8.1 62 (0, 1, 0, 1, 1, 1, 1, 1) 2 Thm
8.1 63 (0, 0, 1, 1, 1, 1, 1, 1) 2 Thm 8.1 64 (0, 1, 1, 1, 1, 1, 1, 1) 2
Complete graph

##  12 An upper bound for $q(G)$ of threshold graphs

In this section, we provide a general upper bound for any connected threshold
graph of order $n$.

######  Theorem 12.1.

Let
$G\cong(\underbrace{0,\ldots,0}_{k_{1}},\underbrace{1,\ldots,1}_{t_{1}},\underbrace{0,\ldots,0}_{k_{2}},\underbrace{1,\ldots,1}_{t_{2}},\ldots,\underbrace{0,\ldots,0}_{k_{s}},\underbrace{1,\ldots,1}_{t_{s}})$
with $k_{i},t_{i},s\geq 1$ be a connected threshold graph with $n$ vertices.
Then

$q(G)\leq\left\lfloor\frac{s+9}{2}\right\rfloor,$

which implies

$q(G)\leq\frac{n}{4}+C$

for some constant $C$ independent of $n$.

###### Proof.

From Lemma 3.2, we have $q(G)\leq q(H)$, where
$H\cong(\underbrace{0,\ldots,0}_{k_{1}},1,\underbrace{0,\ldots,0}_{k_{2}},1,\ldots,\underbrace{0,\ldots,0}_{k_{s}},1)$.
For the graph $H$, if for any $i\in[s]$, $k_{i}=1$ then by Lemma 5.1

$q(H)=3\leq\left\lfloor\frac{s+9}{2}\right\rfloor.$

Otherwise, there is at least one index $i\in[s]$ with $k_{i}>1$. Consider the
related threshold graph
$H_{0}=(\underbrace{0,1,\ldots,0,1}_{2p_{1}},0,0,1,\underbrace{0,1,\ldots,0,1}_{2p_{2}})$,
where $p_{1}+p_{2}+1=s$. We have the following three cases:

$Case\,1)\,$ Both $p_{1}$ and $p_{2}$ are even. Let $p_{1}=2s_{1}$, and
$p_{2}=2s_{2}$. In this case, consider the following vertex-clique incidence
matrix $M$:

$M=\left(\begin{array}[]{ccccccccccccccc}1&0&0&0&0&0&\ldots&&0&0\\\
1&2&0&0&0&0&\ldots&&0&0\\\ 1&1&1&0&0&0&\ldots&&0&0\\\
1&1&1&2&0&0&\ldots&&0&0\\\ 1&1&1&1&1&1&\ldots&&0&0\\\
1&1&1&1&1&1&\ldots&&0&0\\\ 1&1&\vdots&\vdots&\vdots&\vdots&\ldots&&0&0\\\
\vdots&\vdots&1&1&&&\ldots&&0&0\\\ 1&1&1&1&1&1&\ldots&&1&0\\\
1&1&1&1&1&1&\ldots&&1&2\\\ \sqrt{3}&0&0&0&0&0&\ldots&&0&0\\\
0&1&0&0&0&0&\ldots&&0&0\\\ 0&0&\sqrt{3}&0&0&0&\ddots&&0&0\\\
0&0&0&1&0&0&&&0&0\\\ \vdots&\vdots&\vdots&\ddots&1&0&\ddots&&0&0\\\
0&0&0&\ldots&0&1&&&0&0\\\ 0&0&0&\ldots&0&0&\ddots&&0&0\\\
0&0&0&\ldots&0&0&&&\sqrt{3}&0\\\ 0&0&0&\ldots&0&0&\ldots&&0&1\\\
\end{array}\right).$

Then

$B=M^{T}\,M=\left(\begin{array}[]{ccccccc}B_{11}&B_{12}&&&\ldots&&B_{1(s_{1}+s_{2}+1)}\\\
B_{12}^{T}&\ddots&&\ddots&&&\\\ &&B_{s_{1}s_{1}}&&&&\\\
&&&B_{(s_{1}+1)(s_{1}+1)}&&&\vdots\\\
\vdots&&\ddots&&B_{(s_{1}+2)(s_{1}+2)}&&\\\ &&&&&\ddots&\\\
B_{1(s_{1}+s_{2}+1)}^{T}&&&\ldots&&&B_{(s_{1}+s_{2}+1)(s_{1}+s_{2}+1)}\\\
\end{array}\right),$

where $B_{11}=\left(\begin{array}[]{cc}T+3&T\\\ T&T+3\\\ \end{array}\right)$,
$B_{s_{1}s_{1}}=\left(\begin{array}[]{cc}p_{2}+6&p_{2}+3\\\ p_{2}+3&p_{2}+6\\\
\end{array}\right)$,
$B_{(s_{1}+1)(s_{1}+1)}=\left(\begin{array}[]{cc}p_{2}+2&p_{2}+1\\\
p_{2}+1&p_{2}+2\\\ \end{array}\right)$,
$B_{(s_{1}+2)(s_{1}+2)}=\left(\begin{array}[]{cc}p_{2}+1&p_{2}-2\\\
p_{2}-2&p_{2}+1\\\ \end{array}\right)$,
$B_{(s_{1}+s_{2}+1)(s_{1}+s_{2}+1)}=\left(\begin{array}[]{cc}5&2\\\ 2&5\\\
\end{array}\right)$ and $B_{ij}$ is a $2\times 2$ matrix with all entries
equal if $i\neq j$. We have
$\\{3^{[{\frac{s-1}{2}}]},\,1\\}\subseteq\mathrm{Spec}(B),$ and then
$\\{0^{[s]},\,3^{[{\frac{s-1}{2}}]},\,1\\}\subseteq\mathrm{Spec}(A)$, where
$A=M\,M^{T}$. The total number of eigenvalues of $A$ is $2s+1$, so the number
of remaining unaccounted for eigenvalues is $(s+1)/2$. Thus

$q(A)\leq\frac{s+1}{2}+3=\frac{s+7}{2}.$

Obviously $A=M\,M^{T}\in S(H_{0})$ and the eigenvalues of $A$ (which are also
eigenvalues of $B$) equal to $3$ and $1$ appear on the main diagonal of $A$.
Then applying Lemma 3.3 we may duplicate vertices corresponding to the
isolated vertices in $H_{0}$ and not increase the total number of eigenvalues.
This gives the threshold graph $H$ has a realization with the same set of
eigenvalues as $H_{0}$. Hence,

$q(G)\leq q(H)\leq\frac{s+7}{2}.$

$Case\,2)\,$ Both $p_{1}$ and $p_{2}$ are odd. Applying a similar method as
above, we can show $q(G)\leq\frac{s+9}{2}$.

$Case\,3)\,$ $p_{1}$ and $p_{2}$ have different parity. Using similar
techniques, it follows that $q(G)\leq\frac{s+8}{2}$.

Hence the first part of the proof is done. We have $n\geq 2s$, i.e.,
$s\leq\frac{n}{2}$. This gives

$q(G)\leq\frac{s+9}{2}\leq\frac{n+18}{4}=\frac{n}{4}+\frac{18}{4},$

which completes the proof of the theorem. ∎

######  Theorem 12.2.

Let $G$ be a graph of order $n$ with a cycle of length four and all other
vertices adjacent to a vertex of the cycle. Then $q(G)=3$.

###### Proof.

Let $M$ be a vertex-clique incidence matrix of $G$ as follows:

$M=\left(\begin{array}[]{cccccc}\sqrt{n-3}&0&0&0&\ldots&0\\\
-1&1&0&0&\ldots&0\\\ 1&1&0&0&\ldots&0\\\ 0&1&1&1&\ldots&1\\\
0&0&\sqrt{2}&0&\ldots&0\\\ 0&0&0&\sqrt{2}&&\vdots\\\
\vdots&\vdots&\vdots&\ddots&\ddots&0\\\ 0&0&0&\ldots&0&\sqrt{2}\\\
\end{array}\right).$

We have $A=MM^{T}\in S(G)$. To find its spectrum, we determine the eigenvalues
of the $(n-2)\times(n-2)$ matrix

$M^{T}M=\left(\begin{array}[]{cccccc}n-1&0&0&\ldots&0\\\ 0&3&1&\ldots&1\\\
0&1&3&\ddots&\vdots\\\ \vdots&\vdots&\ddots&\ddots&1\\\ 0&1&\dots&1&3\\\
\end{array}\right),$

which are as follows:

$\mathrm{Spec}(M^{T}M)=\\{n-1^{[2]},\,2^{[n-4]}\\}.$

Then the spectrum of $A$ is

$\mathrm{Spec}(A)=\\{n-1^{[2]},\,2^{[n-4]},\,0^{2}\\}.$

This with Lemma 3.5 gives $q(G)=3$. ∎

##  13 Conclusions

This paper has laid some groundwork for studies on the spectral parameter
$q(G)$ for certain structured families of graphs. The specific family
considered here was threshold graphs, where we established numerous results
concerning $q(G)$, including: threshold graphs on $n$ vertices with specific
values of the trace; a general upper bound on $q$ for all threshold graphs; a
workable constraint for threshold graphs with $q$ equal to two; and a complete
list of $q(G)$ for threshold graphs of order 7 and 8 (for the latter there are
just two exceptions).

Looking ahead there are plenty of unresolved issues on this topic including:

  1. 1.

Consider $q(G)$ for general threshold graphs with fixed trace $T$ with
$T\in\\{3,4,\ldots,n-4\\}$;

  2. 2.

Characterize the threshold graphs $G$ that satisfy $q(G)=3$ or $q(G)=4$, etc.;

  3. 3.

Determine the maximum value of $q(G)$ for fixed $n$ and trace; and

  4. 4.

Expand this study beyond the family of threshold graphs to include perhaps
split graphs or cographs.

## Acknowledgements

Dr. Fallat’s research was supported in part by an NSERC Discovery Research
Grant, Application No.: RGPIN-2019-03934. The work of the PIMS Postdoctoral
Fellow Dr. S. A. Mojallal leading to this publication was supported in part by
PIMS.

## References

  * [1] B. Ahmadi, F. Alinaghipour, M.S. Cavers, S. M. Fallat, K. Meagher, and S. Nasserasr, Minimum number of distinct eigenvalues of graphs, Elec. J. Lin. Alg. 26 (2013) 673–691.
  * [2] J. Ahn, C. Alar, B. Bjorkman, S. Butler, J. Carlson, A. Goodnight, H. Knox, C. Monroe, M.C. Wigal, Ordered multiplicity inverse eigenvalue problem for graphs on six vertices, Elec. J. Lin. Alg. 37 (2021) 316–358.
  * [3] R. B. Bapat, On the adjacency matrix of a threshold graph, Linear Algebra Appl. 439 (2013) 3008–3015.
  * [4] W. Barrett, S. Fallat, H.T. Hall, L. Hogben, J.C.-H. Lin, B.L. Shader, Generalizations of the strong Arnold property and the minimum number of distinct eigenvalues of a graph, Electron. J. Combin. 24(2) (2017) 1–28.
  * [5] M. Booth, P. Hackney, B. Harris, C. R. Johnson, M. Lay, L. H. Mitchell, S. K. Narayan, A. Pascoe, K. Steinmetz, B. D. Sutton, W. Wang, On the minimum rank among positive semidefinite matrices with a given graph, SIAM Matrix Anal. Appl. 30 (2008) 731–740.
  * [6] D. Cvetković, P. Rowlinson, S. Simić, An introduction to the theory of graph spectra, Cambridge University Press, Cambridge, 2012.
  * [7] S. Fallat, L. Hogben, The minimum rank of symmetric matrices described by a graph: A survey, Linear Algebra Appl. 426 (2007) 558–582.
  * [8] S. Fallat, L. Hogben, Variants on the minimum rank problem: A survey II, Preprint, arXiv:1102-5142v1, 2011.
  * [9] W. E. Ferguson, The construction of Jacobi and periodic Jacobi matrices with prescribed spectra, Math. Comp. 35 (1980) 1203–1220.
  * [10] C. Godsil, G. Royle, Algebraic Graph Theory, Springer, 2001.
  * [11] A. Hagberg, P. J. Swart, D. A. Schult, Designing threshold networks with given structural and dynamical properties, Phys. Rev. E 74 (2006) 056116-1–056116-10.
  * [12] L. Hogben, Spectral graph theory and the inverse eigenvalue problem of a graph, Electron. J. Linear Algebra, 14 (2005) 12–31.
  * [13] R. Horn, C. Johnson, Matrix Analysis, Cambridge Univ. Press, Cambridge, 1989.
  * [14] R. H. Levene, P. Oblak, H. Šmigoc, A Nordhaus–Gaddum conjecture for the minimum number of distinct eigenvalues of a graph, Linear Algebra Appl. 564 (2019) 236–263.
  * [15] R. Merris, Degree maximal graphs are Laplacian integral, Linear Algebra Appl. 199 (1994) 381–389.
  * [16] Shuchao Li, Wanting Sun, On the zero forcing number of a graph involving some classical parameters, Journal of Combinatorial Optimization 39 (2020) 365–384.