# On the Spectrum of Threshold Graphs

Authors: Irene Sciriha; Stephanie Farrugia
Journal: ISRN Discrete Mathematics
 (2011)

---

## Abstract

The antiregular connected graph onr vertices is defined as the connected graph whose vertex degrees take the values of r−1 distinct positive integers. We explore the spectrum of its adjacency matrix and show common properties with those of connected threshold graphs, having an equitable partition with a minimal number r of parts. Structural and combinatorial properties can be deduced for related classes of graphs and in particular for the minimal configurations in the class of singular graphs.


---

## Body

## 1. Introduction

A graphG=G(𝒱,ℰ) of ordern has a labelled vertex set 𝒱={1,2,…,n} containing n vertices and a set ℰ of m edges consisting of unordered pairs of the vertices. When a subset 𝒱1 of 𝒱 is deleted, the edges incident to 𝒱1 are also deleted. The subgraph G-𝒱1 of G is said to be an induced subgraph of G. The subgraph of G obtained by deleting a particular vertex v is simply denoted by G-v. The cycle and the complete graph on n vertices are denoted by Cn and Kn, respectively.The graphs we consider aresimple, that is, without loops or multiple edges. We use bold face, say G, to denote the 0-1-adjacency matrix of the graph bearing the same name G, where the ijth entry of the symmetric matrix G is 1 if {i,j}∈ℰ and 0 otherwise. We note that the graph G is determined, up to isomorphism, by G. The adjacency matrix GC of the complement GC of G is J-I-G, where each entry of J is one and I is the identity matrix. The degree of a vertex i is the number of nonzero entries in the ith row of G.The disconnected graph with two componentsG1 and G2 is their disjoint union, denoted by G1∪̇G2. For r≥2, the graph rG is the disconnected graph with r components, where each component is isomorphic to G. The joinG1∇G2 of G1 and G2 is (G1C∪̇G2C)C.For the linear transformationG, the n real numbers {λ}satisfying Gx=λx for some nonzero vector x∈ℝn are said to be eigenvalues of G and form the spectrum of G. They are the solutions of the characteristic polynomialϕ(G,λ) of G, defined as the polynomial det(λI-G) in λ. The subspace kerG of Rn that maps to zero under G is said to be the nullspace of G. A graph G is said to be singular of nullityη if the dimension of ker(G) is η. The nonzero vectors, x∈ℝn, in the nullspace, termed kernel eigenvectors of G, satisfy Gx=0. We note that the multiplicity of the eigenvalue zero is η. If there exists a kernel eigenvector of G with no zero entries, then G is said to be a core graph. The cycle C4 on four vertices is a core graph of nullity two with a kernel eigenvector (1,1,-1,-1)t for the usual labelling of the vertices round the cycle. A core graph of nullity one is said to be a nut graph [1]. A minimal configuration for a particular core, to be defined formally in Section 6, is intuitively a graph of nullity one with a minimal number of vertices and edges for that core.The distinct eigenvaluesμ1,μ2,…,μp,1≤p≤n, which have an associated eigenvector not orthogonal to j (the vector with each entry equal to one) are said to be main. We denote the remaining distinct eigenvalues by μp+1,…,μs,s≤n, and refer to them as nonmain. By the Perron-Frobenius theorem [2, page 6] the maximum eigenvalue of the adjacency matrix of a connected graph has an associated eigenvector (termed the Perron vector) with all its entries positive. Therefore, at least one eigenvalue of a graph is main.Acograph, or complement-reducible graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. Threshold graphsare a subclass of cographs. They were first introduced in 1977 by Chvátal and Hammer in connection with the equivalence between set packing and knapsack problems [3] and independently, in the same year, by Henderson and Zalcstein for parallel systems in computer programming [4]. It is surprising that they kept being rediscovered in different contexts leading to several equivalent definitions. The most useful for our purposes are two, given below: one in terms of their forbidden induced subgraphs and the other in terms of their degree sequence [5, 6]. For the latter definition, the graph partitionΠ of 2m into parts equal to the vertex degrees {ρ1,ρ2,…,ρn} is needed. The array of boxes F(Π), known as a Ferrers/Young diagram for the monotonic nonincreasing sequence Π={ρ1,ρ2,…,ρn} consists of n rows of ρi boxes as i runs successively from 1 to n. Threshold graphs are characterized by a particular shape of the Ferrers/Young diagram (see Figure 4), which will be described in Section 3.4.Definition 1.1.
(i) Athreshold graph is a graph with no induced subgraphs isomorphic to any of the following subgraphs on four vertices: the path P4, the cycle C4 and the two copies 2K2 of the complete graph K2 on two vertices. It is said to be P4-, C4-, and 2K2-free.
Equivalently, (ii) if the monotonic nonincreasing degree sequence,Π={ρ1,ρ2,…,ρn}, of a graph G is represented by the rows of a Ferrers/Young diagram F(Π), where the length of the principal square of F(Π) is f(Π) and the lengths {πk*:1≤k≤f(Π)} of the columns of F(Π) satisfy πk*=ρk+1, then G is said to be a threshold graph [7, Lemma 7.23].If the parts of a threshold graph partition of2m are all equal, then the graph is regular and corresponds to the complete graph. If, on the other hand, there are as many distinct sizes of the parts of a threshold graph partition of 2m as possible, then the graph is said to be antiregular. Recall that at least two vertices in a graph have the same degree.Definition 1.2.
Anantiregular graph on r vertices is defined as a threshold graph whose vertex degrees take as many different values as possible, that is, r-1 distinct nonnegative integral values.Definition 1.3.
The partition𝒱1∪̇𝒱2∪̇⋯∪̇𝒱r of the vertex set 𝒱 of a graph G is said to be an equitable partition if, for all i,j∈{1,2,…,r}, the number of neighbours in 𝒱j of a vertex in 𝒱i depends only on the choice of i and j.The overall aim of this paper is to explore the spectrum of its adjacency matrix and show common properties with those of connected threshold graphs, having an equitable partition with a minimal numberr of parts.The paper is organised as follows. In Section2, cographs are reviewed and made use of in Section 3 to determine a particular representation of a threshold graph that has earned it the name of nested split graph. We also present various other representations that are used selectively to simplify our proofs. In Section 4, a procedure that transforms the Ferrers/Young diagram into the adjacency matrix of the threshold graph for a particular vertex labelling is given. The structures of the graph and of its underlying antiregular graph are also compared.Our main results are as follows.(i)
In Section5, the Ferrers/Young diagram comes in use to explore the nullspace of a threshold graph.(ii)
In Section6, we show that all minimal configurations on at least five vertices have the subgraph P4 induced.(iii)
We show in Section7 that the spectrum of a connected threshold graph G and its underlying antiregular graph show common characteristics. All the eigenvalues other than 0 and −1 are main and each main eigenvalue contributes to the number of walks. Moreover, the spectrum of its quotient graph G/Π consists precisely of the main eigenvalues of G. The characteristic polynomial of G/Π is reducible over the integers (i.e., it has polynomial factors) for certain threshold graphs G.(iv)
We end with a discussion, in Section8, on the variation in the sign pattern of the spectrum as vertices are added to a threshold graph to produce another threshold graph.


## 2. Cographs

A cograph is the union or the join of subgraphs of the form(⋯((r1K1)C∪̇(r2K1))C∪̇⋯∪̇(rsK1)C), where ri∈ℤ+∪{0}, for all i. Therefore, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union. It is well known that no cograph on at least four vertices has P4 as an induced subgraph [8]. In fact cographs can also be characterized as P4-free graphs.Cographs have received much attention since the 1970s. They were discovered independently by many authors including Jung [9] in 1978, Lerchs [10] in 1971 and, Seinsche [11] and Sumner [12], both in 1974. For a more detailed treatment of cographs, see [8].Connected graphs, which are2K2-, P4-, and C4-free, necessarily have a dominating vertex, that is, a vertex adjacent to all the other vertices of the graph. Thus, all connected threshold graphs have a dominating vertex.By construction, a connected cograph also has a dominating vertex. Therefore, its complement has at least one isolated vertex. A necessary condition for a connected graph to have a connected complement is that it hasP4 as an induced subgraph [7, Theorem 1.19]. The set of cographs and the class of graphs with a connected complement are disjoint as sets. However, if the graph H is P4∪̇K1, then both H and HC have P4-induced. Thus there exist connected graphs that are neither P4 free nor have a connected complement.Recall thatG1∇G2=(G1C∪̇G2C)C. Hence, cographs are also characterized as the smallest class of graphs that includes K1 and is closed under join and disjoint union. On this definition of cographs, the proofs in [13], of the result that cographs are polynomial reconstructible from the deck of characteristic polynomials of the one-vertex deleted subgraphs, are based.A cograph can be represented uniquely by acotree, as explained in [14] and later in [13]. Figure 1 shows the cotree TG of the cograph G. The vertices ⊕, ⊗, and • of a cotree represent the disjoint union, the join, and the vertices of the cograph, respectively. For simplicity we say that the terminal vertices of TG are vertices of G. The cotree TG is a rooted tree and only the terminal vertices represent the cograph vertices. An interior vertex ⊕ or ⊗ of TG represents the subgraph of G induced by its terminal successors. The immediate successors of ⊕ can be cograph vertices • or ⊗. Similarly the immediate successors of ⊗ can be cograph vertices • or ⊕. Therefore, the interior vertices of TG on a (oriented) path descending from the root to a terminal vertex of TG are a sequence of alternating ⊗ and ⊕.CotreeTG for the cograph G.
(a)(b)


## 3. Representations of Threshold Graphs

In this section we present some of the various representations of threshold graphs. Collectively, they provide a wealth of information that determine combinatorial properties of these graphs. We start with the cotree representation as in the previous section. There are certain restrictions on the structure of a cotree in the case when a cograph is a threshold graph.We give a proof to the following result quoted in [13].Lemma 3.1.
If a cographG is also a threshold graph, then each interior vertex of TG has at most one interior vertex as an immediate successor.Proof.
A threshold graphG is P4-free and therefore is a cograph which can be represented by a cotree TG. Note that P4 cannot be represented as a cotree. In a threshold graph, there are no induced subgraphs isomorphic to C4 or to 2K2. Therefore, the configurations in Figure 2(a) representing C4 and 2(b) representing 2K2 as cotrees are not allowed in the cotree TG corresponding to a threshold graph G. We deduce that the number of interior vertices which are immediate successors of an interior vertex is less than two, as required.Representations ofC4 and 2K2 in a cotree.
(a)(b)We now present various other representations of threshold graphs that are used in the proofs that follow.


### 3.1. Cotrees of Nested Split Graphs

Acaterpillar is a tree in which the removal of all terminal vertices (i.e., those of degree 1) gives a path. The following result follows immediately from Lemma 3.1.Corollary 3.2.
The cotree of a threshold graph is a caterpillar.The vertex set of asplit graph is partitioned into two subsets, one of which is a clique (inducing a complete subgraph) and the other a coclique or an independent set (inducing the empty graph with no edges). Because of its structure, a threshold graph is also referred to as a nested split graph.The first vertex labelling (which we will refer to as Lab1) of a threshold graph is according to its construction. Starting fromK1 (vertex 1a), the graph in Figure 3 is (((((((((K1∪̇K1)∇K1)∇K1)∪̇K1)∇K1)∇K1)∪̇K1)∇K1)∇K1) coded as ((((((K1∪̇K1)∇2K1)∪̇K1)∇2K1)∪̇K1)∇2K1) to avoid repetitions of successive joins or unions. Therefore, according to the vertex labelling in Figure 3, G is (((((((((1a∪̇1b)∇2a)∇2b)∪̇3a)∇4a)∇4b)∪̇5a)∇6a)∇6b). The cotree TG represents the threshold graph G drawn next to it in a way so as to emphasise the nested split graph structure of G, where the circumscribed vertices labelled 1 represent the subgraph induced by the vertices 1a and 1b, and similarly for the other circumscribed subsets of vertices.CotreeTG and the nested structure of the threshold graph G.
(a)(b)The Ferrers/Young diagram for a threshold graph.
(a)(b)(c)InTG, the terminal vertices {•} which are immediate successors of a vertex ⊗ form a clique (inducing a complete subgraph) whereas those immediately succeeding a vertex ⊕ form a coclique (inducing a subgraph without edges). A line in G joining R and S, which are circumscribed cliques or cocliques, means that each vertex of R is adjacent to each vertex of S.


### 3.2. Minimal Equitable Partition of the Vertex Set

Our labelling of ther parts in the equitable partition of the vertices of a connected threshold graph C(a1,a2,…,ar) follows the addition of the vertices in the construction in order, namely, ((⋯(∪̇a1K1∇a2K1)∪̇a3K1)∇⋯arK1) according to the coded representation of the graph in Figure 3. Then, the nested structure of the threshold graph becomes clear. The parts are cliques or cocliques of size ai for 1≤i≤r. For a minimal value of r, Π is said to be a nondegenerate equitable partition for the nondegenerate representation C(a1,a2,…,ar). All other equitable partitions of the vertex set are refinements of Π with a larger number of parts, when an equitable partition and the corresponding representation C(a1,a2,…,ar) are said to be degenerate. Unless otherwise stated we will assume that equitable vertex partitions and representations are nondegenerate. In particular a1≠1.According to our labelling convention (Lab1) forC(a1,a2,…,ar) as in Figure 3, a threshold graph G whose cotree TG has root ⊗ is connected. If r is even, then a1 is associated with a coclique, whereas, for r odd, a1 is associated with a clique. It follows that the monotonic nonincreasing vertex degree sequence of G will be associated with ar,ar-2,…,a2,a1,a3,…,ar-1 in that order if r is even and ar,ar-2,…,a1,a2,a4,…,ar-1 in that order if r is odd. By convention therefore, for a nondegenerate equitable partition, ai≥1 for 2≤i≤r-1 and a1≥2. According to this representation, the graph of Figure 3 has the nondegenerate representation C(2,2,1,2,1,2).


### 3.3. The Binary Code of a Threshold Graph

For the purposes of inputting ann-vertex-threshold graph to be processed in a computer program, the graph is encoded as a string of n-1 bits. The graph is represented as a sequence of 0 and 1 entries where 0 represents the addition of an isolated vertex and 1 represents the addition of a dominating vertex in the construction of the graph, staring from K1, as described above.The graph of Figure3 is encoded as (011011011).


### 3.4. Degree Sequence

The last representation of a threshold graph that we now give is constructed from the degree sequence. Following Definition1.1(ii), let F(Π) be the Ferrers/Young diagram (Figure 4) for the nonincreasing degree sequence giving a vertex partition Π={ρ1,ρ2,…,ρn} of 2m for an n-vertex graph. The largest principal square of boxes in F(Π) is termed the Durfee square and f(Π) denotes the size of the Durfee square (i.e., the length of a side of the Durfee square). A graph is graphical if and only if πi*≥ρi+1 for 1≤i≤f(Π) [15].It is well known that there exist nonisomorphic graphs with the same degree sequence. A graph determined, up to isomorphism, by its degree sequence is said to be aunigraph.Lemma 3.3 (see [7, Theorem 7.30]).
A threshold graph is a unigraph.The degree sequenceΠ of a threshold graph also produces a particular structure of the Ferrers/Young diagram F(Π), shown in Figure 4.Lemma 3.4 (see [7]).
For a threshold graph,F(Π) consists of four blocks P, Q, R, and its transpose Rt, where P is the Durfee square, Q is the (f(Π)+1)th row of F(Π) of length f(Π), and R is the array of boxes left after removing the Durfee square from the first f(Π) rows of F(Π).


## 3.1. Cotrees of Nested Split Graphs

Acaterpillar is a tree in which the removal of all terminal vertices (i.e., those of degree 1) gives a path. The following result follows immediately from Lemma 3.1.Corollary 3.2.
The cotree of a threshold graph is a caterpillar.The vertex set of asplit graph is partitioned into two subsets, one of which is a clique (inducing a complete subgraph) and the other a coclique or an independent set (inducing the empty graph with no edges). Because of its structure, a threshold graph is also referred to as a nested split graph.The first vertex labelling (which we will refer to as Lab1) of a threshold graph is according to its construction. Starting fromK1 (vertex 1a), the graph in Figure 3 is (((((((((K1∪̇K1)∇K1)∇K1)∪̇K1)∇K1)∇K1)∪̇K1)∇K1)∇K1) coded as ((((((K1∪̇K1)∇2K1)∪̇K1)∇2K1)∪̇K1)∇2K1) to avoid repetitions of successive joins or unions. Therefore, according to the vertex labelling in Figure 3, G is (((((((((1a∪̇1b)∇2a)∇2b)∪̇3a)∇4a)∇4b)∪̇5a)∇6a)∇6b). The cotree TG represents the threshold graph G drawn next to it in a way so as to emphasise the nested split graph structure of G, where the circumscribed vertices labelled 1 represent the subgraph induced by the vertices 1a and 1b, and similarly for the other circumscribed subsets of vertices.CotreeTG and the nested structure of the threshold graph G.
(a)(b)The Ferrers/Young diagram for a threshold graph.
(a)(b)(c)InTG, the terminal vertices {•} which are immediate successors of a vertex ⊗ form a clique (inducing a complete subgraph) whereas those immediately succeeding a vertex ⊕ form a coclique (inducing a subgraph without edges). A line in G joining R and S, which are circumscribed cliques or cocliques, means that each vertex of R is adjacent to each vertex of S.


## 3.2. Minimal Equitable Partition of the Vertex Set

Our labelling of ther parts in the equitable partition of the vertices of a connected threshold graph C(a1,a2,…,ar) follows the addition of the vertices in the construction in order, namely, ((⋯(∪̇a1K1∇a2K1)∪̇a3K1)∇⋯arK1) according to the coded representation of the graph in Figure 3. Then, the nested structure of the threshold graph becomes clear. The parts are cliques or cocliques of size ai for 1≤i≤r. For a minimal value of r, Π is said to be a nondegenerate equitable partition for the nondegenerate representation C(a1,a2,…,ar). All other equitable partitions of the vertex set are refinements of Π with a larger number of parts, when an equitable partition and the corresponding representation C(a1,a2,…,ar) are said to be degenerate. Unless otherwise stated we will assume that equitable vertex partitions and representations are nondegenerate. In particular a1≠1.According to our labelling convention (Lab1) forC(a1,a2,…,ar) as in Figure 3, a threshold graph G whose cotree TG has root ⊗ is connected. If r is even, then a1 is associated with a coclique, whereas, for r odd, a1 is associated with a clique. It follows that the monotonic nonincreasing vertex degree sequence of G will be associated with ar,ar-2,…,a2,a1,a3,…,ar-1 in that order if r is even and ar,ar-2,…,a1,a2,a4,…,ar-1 in that order if r is odd. By convention therefore, for a nondegenerate equitable partition, ai≥1 for 2≤i≤r-1 and a1≥2. According to this representation, the graph of Figure 3 has the nondegenerate representation C(2,2,1,2,1,2).


## 3.3. The Binary Code of a Threshold Graph

For the purposes of inputting ann-vertex-threshold graph to be processed in a computer program, the graph is encoded as a string of n-1 bits. The graph is represented as a sequence of 0 and 1 entries where 0 represents the addition of an isolated vertex and 1 represents the addition of a dominating vertex in the construction of the graph, staring from K1, as described above.The graph of Figure3 is encoded as (011011011).


## 3.4. Degree Sequence

The last representation of a threshold graph that we now give is constructed from the degree sequence. Following Definition1.1(ii), let F(Π) be the Ferrers/Young diagram (Figure 4) for the nonincreasing degree sequence giving a vertex partition Π={ρ1,ρ2,…,ρn} of 2m for an n-vertex graph. The largest principal square of boxes in F(Π) is termed the Durfee square and f(Π) denotes the size of the Durfee square (i.e., the length of a side of the Durfee square). A graph is graphical if and only if πi*≥ρi+1 for 1≤i≤f(Π) [15].It is well known that there exist nonisomorphic graphs with the same degree sequence. A graph determined, up to isomorphism, by its degree sequence is said to be aunigraph.Lemma 3.3 (see [7, Theorem 7.30]).
A threshold graph is a unigraph.The degree sequenceΠ of a threshold graph also produces a particular structure of the Ferrers/Young diagram F(Π), shown in Figure 4.Lemma 3.4 (see [7]).
For a threshold graph,F(Π) consists of four blocks P, Q, R, and its transpose Rt, where P is the Durfee square, Q is the (f(Π)+1)th row of F(Π) of length f(Π), and R is the array of boxes left after removing the Durfee square from the first f(Π) rows of F(Π).


## 4. The Structure of Threshold Graphs

An interesting algorithm was presented in [15] to construct a threshold graph. The adjacency list adjList of the graph, that is the list of neighbours of each vertex, is in fact obtained by filling in the boxes of the ith row in F(Π) with consecutive integers starting from 1, but skipping i. By Lemma 3.3, F(Π) gives a unique threshold graph, up to isomorphism and therefore provides a canonical vertex labelling. We now present a procedure to produce the adjacency matrix of the labelled threshold graph corresponding to adjList from F(Π). We note that this gives us the second labelling, Lab2, in order of the nonincreasing degree sequence and therefore different from Lab1 used for C(a1,a2,…,ar).Theorem 4.1.
Then×n adjacency matrix G of a threshold graph G is obtained from its Ferrers/Young diagram F(Π), representing the degree sequence of a n-vertex graph, as follows. The ith box is inserted in each ith row and filled with a zero entry. The rest of the existing boxes are filled with the entry 1. Boxes are now inserted so that a n×n array of boxes is obtained. Each of the remaining empty boxes is filled with zero. The n×n array of 0-1-numbers obtained is the adjacency matrix G.The rows and columns of the adjacency matrix constructed in Theorem4.1 are indexed according to the nonincreasing degree sequence. If, for a threshold graph, each of the boxes of the ith row in F(Π) is filled with i to obtain H(Π), then the adjacency list adjList of the graph is just a rearrangement of the entries of H(Π) since, by Definition 1.1, πk*=ρk+1. Due to the shape of the nonzero part, the adjacency matrix is said to have “a stepwise” form [16, 17].


### 4.1. The Antiregular Graph

The antiregular graphAr may be considered to be the smallest threshold graph for an equitable vertex partition having a given number (r-1) of parts.Definition 4.2.
Anantiregular graphAr on r vertices is a graph whose vertex degrees take the values of r-1 distinct (nonnegative) integers.We shall use ther-vertex connected antiregular graph Ar with the largest number (r-1) of parts in its equitable partition, having degenerate representation C(1,1,…,1) using Lab1. Any part can be expanded to produce a threshold graph C(a1,a2,…,ar), taking care to preserve the nested split structure. The connected antiregular graph Ar with degenerate equitable partition into r parts is adopted as the underlying graph of a connected threshold graph for an equitable vertex partition with r parts.Lemma 4.3.
An induced subgraphH of G=C(a1,a2,…,ar) is C(b1,b2,…,br), where 0≤bi≤ai for 1≤i≤s.Proof.
Whenai≠bi for at least one value of i, to produce H, vertices are deleted from the part of size ai in the equitable partition of 𝒱G. This procedure produces an induced subgraph at each stage and it is repeated until bi is reached for each i.The threshold graphC(1,1,…,1) having r parts, where each part is of size 1, is the degenerate form of Ar. Its nondegenerate form, consistent with the cotree representations of threshold graphs, is C(2,1,…,1,1) having r-1 parts, with only the first part of size 2. As an immediate consequence of Lemma 4.3 we have the following.Corollary 4.4.
The connected antiregular graphC(2,1,1,…,1), having r-1 parts, with degenerate representation C(1,1,1,…,1), having r parts, is an induced subgraph of C(a1,a2,…,ar) where 1≤ai for 2≤i≤r and a1≥2.On taking the complement ofC(a1,a2,…,ar) or on deleting a dominating vertex when ar=1, a disconnected graph is obtained (see Figures 5 and 6).The threshold graphG=C(a1,a2,…,a7), GC and G-v for a7=1.
(a)(b)(c)The threshold graphG=C(a1,a2,…,a8), GC and G-v for a8=1 (Lab1).
(a)(b)(c)Proposition 4.5.
Letv be the dominating vertex of Ar. Then, (i)Ar-v is K1∪̇Ar-2 and (ii)ArC=K1∪̇Ar-1.Figures5 and 6, respectively, show the threshold graphs with underlying A7 and A8, their complements, and the v-deleted subgraphs when v is the only dominating vertex. The corresponding representations of A7 and A8 are C(2,1,1,1,1,1) and C(2,1,1,1,1,1,1), respectively.Proposition 4.6.
The binary codes for the connected antiregular graphsA2k and A2k+1 are, respectively, the (2k-1)-string (1010⋯1) and the 2k-string (010⋯1) with alternating 0 and 1 entries.Since the binary code follows the construction ofAr algorithmically, we have the following.Corollary 4.7.
The construction of connected antiregular graphs is as follows: fork∈ℤ+:A2k=(⋯(K1∇K1)∪̇K1)∇⋯)∇K1,A2k+1=(⋯(K1∪̇K1)∇K1)∪̇⋯)∇K1.


### 4.2. The Complement of a Threshold Graph

The complement of a connected threshold graphC(a1,a2,…,ar) is disconnected and is denoted by D(a1,a2,…,ar) (see Figure 3). The following result is deduced from the construction of the complement.Proposition 4.8 (see [18]).
The cotreeTGC of the complement GC=D(a1,a2,…,ar) of G=C(a1,a2,…,ar) is obtained from TG by changing the interior vertices from ⊗ to ⊕ and viceversa.Corollary 4.9.
The complementGC of the connected threshold graph C(a1,a2,a3,…,ar), is the disconnected threshold graph D(a1,a2,…,ar) isomorphic to C(a1,a2,…,ar-1)∪̇arK1.Proof.
SinceC(a1,a2,a3,…,ar) is connected, its cotree has ⊗ as a root. Therefore, by Proposition 4.8, the cotree D(a1,a2,…,ar) has ⊕ as a root, and therefore it has coclique Kar.Proposition 4.10.
The binary string coding of the threshold graphC(a1,a2,…,a2k), with the underlying graph A2k, is the 2k-string (0a1-11a2⋯1a2k) of 0 and 1 entries. (The superscripts denote repetition; 1ai denotes the substring 111… with 1 repeated ai times).Similarly the binary string coding of the threshold graphC(a1,a2,…,a2k+1), with underlying graph A2k+1, is the 2k+1-string (1a1-10a2⋯1a2k+1).


## 4.1. The Antiregular Graph

The antiregular graphAr may be considered to be the smallest threshold graph for an equitable vertex partition having a given number (r-1) of parts.Definition 4.2.
Anantiregular graphAr on r vertices is a graph whose vertex degrees take the values of r-1 distinct (nonnegative) integers.We shall use ther-vertex connected antiregular graph Ar with the largest number (r-1) of parts in its equitable partition, having degenerate representation C(1,1,…,1) using Lab1. Any part can be expanded to produce a threshold graph C(a1,a2,…,ar), taking care to preserve the nested split structure. The connected antiregular graph Ar with degenerate equitable partition into r parts is adopted as the underlying graph of a connected threshold graph for an equitable vertex partition with r parts.Lemma 4.3.
An induced subgraphH of G=C(a1,a2,…,ar) is C(b1,b2,…,br), where 0≤bi≤ai for 1≤i≤s.Proof.
Whenai≠bi for at least one value of i, to produce H, vertices are deleted from the part of size ai in the equitable partition of 𝒱G. This procedure produces an induced subgraph at each stage and it is repeated until bi is reached for each i.The threshold graphC(1,1,…,1) having r parts, where each part is of size 1, is the degenerate form of Ar. Its nondegenerate form, consistent with the cotree representations of threshold graphs, is C(2,1,…,1,1) having r-1 parts, with only the first part of size 2. As an immediate consequence of Lemma 4.3 we have the following.Corollary 4.4.
The connected antiregular graphC(2,1,1,…,1), having r-1 parts, with degenerate representation C(1,1,1,…,1), having r parts, is an induced subgraph of C(a1,a2,…,ar) where 1≤ai for 2≤i≤r and a1≥2.On taking the complement ofC(a1,a2,…,ar) or on deleting a dominating vertex when ar=1, a disconnected graph is obtained (see Figures 5 and 6).The threshold graphG=C(a1,a2,…,a7), GC and G-v for a7=1.
(a)(b)(c)The threshold graphG=C(a1,a2,…,a8), GC and G-v for a8=1 (Lab1).
(a)(b)(c)Proposition 4.5.
Letv be the dominating vertex of Ar. Then, (i)Ar-v is K1∪̇Ar-2 and (ii)ArC=K1∪̇Ar-1.Figures5 and 6, respectively, show the threshold graphs with underlying A7 and A8, their complements, and the v-deleted subgraphs when v is the only dominating vertex. The corresponding representations of A7 and A8 are C(2,1,1,1,1,1) and C(2,1,1,1,1,1,1), respectively.Proposition 4.6.
The binary codes for the connected antiregular graphsA2k and A2k+1 are, respectively, the (2k-1)-string (1010⋯1) and the 2k-string (010⋯1) with alternating 0 and 1 entries.Since the binary code follows the construction ofAr algorithmically, we have the following.Corollary 4.7.
The construction of connected antiregular graphs is as follows: fork∈ℤ+:A2k=(⋯(K1∇K1)∪̇K1)∇⋯)∇K1,A2k+1=(⋯(K1∪̇K1)∇K1)∪̇⋯)∇K1.


## 4.2. The Complement of a Threshold Graph

The complement of a connected threshold graphC(a1,a2,…,ar) is disconnected and is denoted by D(a1,a2,…,ar) (see Figure 3). The following result is deduced from the construction of the complement.Proposition 4.8 (see [18]).
The cotreeTGC of the complement GC=D(a1,a2,…,ar) of G=C(a1,a2,…,ar) is obtained from TG by changing the interior vertices from ⊗ to ⊕ and viceversa.Corollary 4.9.
The complementGC of the connected threshold graph C(a1,a2,a3,…,ar), is the disconnected threshold graph D(a1,a2,…,ar) isomorphic to C(a1,a2,…,ar-1)∪̇arK1.Proof.
SinceC(a1,a2,a3,…,ar) is connected, its cotree has ⊗ as a root. Therefore, by Proposition 4.8, the cotree D(a1,a2,…,ar) has ⊕ as a root, and therefore it has coclique Kar.Proposition 4.10.
The binary string coding of the threshold graphC(a1,a2,…,a2k), with the underlying graph A2k, is the 2k-string (0a1-11a2⋯1a2k) of 0 and 1 entries. (The superscripts denote repetition; 1ai denotes the substring 111… with 1 repeated ai times).Similarly the binary string coding of the threshold graphC(a1,a2,…,a2k+1), with underlying graph A2k+1, is the 2k+1-string (1a1-10a2⋯1a2k+1).


## 5. The Nullity of Threshold Graphs

A pair ofduplicate vertices of a graph are nonadjacent and have common neighbours, whereas a pair of coduplicate vertices are adjacent and have common neighbours. The rows of the adjacency matrix corresponding to duplicate vertices are identical and for those of coduplicate vertices k and h, the kth and hth rows differ only in the kth and hth entries. It follows that both duplicates and coduplicates produce the eigenvector with only two nonzero entries, namely, 1 and −1, at positions corresponding to the pair of vertices, with corresponding eigenvalue 0 and −1, respectively.Remark 5.1.
In this section we adopt the vertex labelling Lab2 of a threshold graph induced by the Ferrers/Young diagram in accordance with the procedure to form the “stepwise” adjacency matrix presented in Theorem4.1.A graph with duplicates is often considered as having repeated vertices and therefore redundant properties. We call the induced subgraph of a graph obtained by removing repeated verticescanonical.Theorem 5.2.
An upper bound for the nullityη(G) of the adjacency matrix of a threshold graph is n-f(Π)-1.Proof.
When the adjacency matrixG is obtained from adjList, the first f(Π) rows are shifted so that none of them is repeated. The first f(Π)+1 labelled vertices form a clique and hence the rank rk(G) of the adjacency matrix G of the n-vertex G which is n-η(G) is at least f(Π)+1.The bound in Theorem5.2 is reached, for instance, by the threshold graphs C(f(Π)+1) (the complete graph) and by C(f(Π)+1,f(Π)).Theorem 5.3.
LetG be a threshold graph on n vertices, with Durfee square size f(Π) and nullity η(G). If n>2f(Π), then G has duplicate vertices.Proof.
The lastn-f(Π) rows of F(Π) are not affected by the introduction of the zero diagonal when constructing G as in Theorem 4.1. Hence, duplicates may only occur among the last n-f(Π) labelled vertices. If G were to have no duplicate vertices, then the last n-f(Π) rows of G need to be all different. Since the f(Π)th row is f(Π) long, then, by a form of the pigeon-hole principle, the largest number n of vertices possible for the graph to have no duplicates is 2f(Π). Therefore if n>2f(Π), G has at least one pair of duplicate vertices.A threshold graph may have duplicate vertices even ifn<2f(Π). We note again that a kernel eigenvector corresponding to duplicate vertices has only two nonzero entries. This prompts the question: can a kernel eigenvector of the threshold graph have more that two nonzero entries? The answer is in the negative as we will now see.Theorem 5.4.
The nullityη(G) of a threshold graph G is the number of vertices removed to obtain a canonical graph.Proof.
LetH be the canonical graph obtained from G by removing all the duplicate vertices. Let us say that the number of vertices removed is t. Since the reflection in the first column of the adjacency matrix H of H is in row echelon form, then the rows of H after the f(Π)th is in strict “stepwise” form. Hence, the columns of H are linearly independent. Now if the t vertices are added to H in turn to obtain G again, then the nullity increases by one at each stage, contributing to the nullspace of the graph obtained, a kernel eigenvector (with exactly two nonzero entries) while preserving the existing ones. We deduce that there are only t linear combinations among the rows of G arising from the repeated rows in the last n-f(Π) rows. Therefore, the nullity of G is t. Moreover, a kernel eigenvector cannot have more than two nonzero entries.In the proof of Theorem5.4, the following result becomes evident.Corollary 5.5.
If a threshold graph is singular, then no kernel eigenvector has more than two nonzero entries.Note that any repeated rows in the firstf(Π) rows of F(Π) give coduplicates. Also f(Π) is the degree of a vertex in the first part of the equitable partition of the threshold graph defined by C(a1,a2,a3,…,ar) for Lab1. For Ar, this corresponds to the ⌈(r+1)/2⌉th degree in the monotonic nonincreasing sequence of distinct degrees (the ⌈(r+1)/2⌉th vertex for labeling Lab2).That an antiregular graph has exactly one pair of either duplicates or coduplicates follows from its construction.Theorem 5.6.
(i)
An antiregular graphA2k-1 on an odd number of vertices has a duplicate vertex.(ii)
An antiregular graphA2k on an even number of vertices has a coduplicate vertex.Proof.
The graphAr is C(2,1,1,…,1). Therefore if r is even, it has a clique of two and hence a pair of coduplicate vertices. On the other hand, if r is odd, then it has a coclique of two, producing a pair of duplicate vertices.To obtain the number of duplicate and coduplicate vertices in a threshold graph, we count the number of vertices to be removed fromG and GC, respectively, to obtain a canonical graph.Theorem 5.7.
A threshold graph with nondegenerate representationC(a1,a2,a3,…,ar), where r is even, has(i)
∑k=1r/2(a2k-1-1) duplicate vertices,(ii)
∑k=1r/2(a2k-1) coduplicate vertices.For odd r, C(a1,a2,a3,…,ar) has(i)
∑k=1(r-1)/2(a2k-1) duplicate vertices,(ii)
∑k=1(r+1)/2(a2k-1-1) coduplicate vertices.


## 6. Minimal Configurations

Most of the information to determine the grounds for a labelled graphG to be singular is encoded in the nullspace ker(G) of its adjacency matrix G (i.e., in ker(G):={x:Gx=0}). The support of a kernel eigenvector x in ker(G) is the set of vertices corresponding to the nonzero entries. These vertices induce a subgraph termed the core ofGwith respect tox. Therefore a core of G with respect to x is a core graph in its own right. The size of the support is said to be the core order [19].Definition 6.1 (see [19]).
LetF be a core graph on at least two vertices, with nullity s≥1 and a kernel eigenvector xF having no zero entries. If a graph N, of nullity one, having xF as the nonzero part of the kernel eigenvector, is obtained by adding s-1 independent vertices, whose neighbours are vertices of F, then N is said to be a minimal configuration (MC) with core (F,xF).Hence, an MC with core(F,xF) is a connected singular graph of nullity one having a minimal number of vertices and edges for the core F, satisfying FxF=0. The MCs may be considered as the “atoms” of a singular graph [19, 20]. The smallest MC is P3 corresponding to a pair of duplicates. For core order three, the only MC is P3. The number of MCs increases fast for higher core order (see e.g., [21]). Figure 7 shows two graphs, (a) P5C, the only MC with core C4 and (b) a nut graph of order seven [1].Two minimal configurations:P5C and a nut graph.
(a)(b)A basis for the nullspaceker(G) of the adjacency matrix G of a graph G of nullity η>1 can take different forms. We choose a minimal basisBmin for the nullspace of G, that is, a basis having a minimal total number of nonzero entries in its vectors [19, 22].Such a minimal basis forker(G) has the property that the corresponding monotonic non-decreasing sequence of core orders (termed the core order sequence) is unique and lexicographically placed first in a list of bases for ker(G), also ordered according to the nonincreasing core orders. Moreover, for all i, the ith entry of the core order sequence for Bmin, does not exceed the ith entry of any other core order sequence of the graph. We say that the vectors in Bmin define a fundamental system of cores of G, consisting of a collection of cores of minimal core order corresponding to a basis of linearly independent nullspace vectors [23]. The significance of MCs can be gauged from the next result.Theorem 6.2 (see [19, 20]).
LetH be a singular graph of nullity η. There exist η MCs which are subgraphs of H whose core vertices are associated with the nonzero entries of the η vectors in a minimal basis of the nullspace of H.To give an example supporting Theorem6.2, Figure 8 shows a six-vertex graph of nullity two and two MCs corresponding to a fundamental system of cores found as subgraphs.A graph of nullity two with two MCs as subgraphs.
(a)(b)(c)From Theorem5.4, the following result follows immediately.Corollary 6.3.
The only MC found in a threshold graph as a subgraph isP3.Corollary6.3 has been generalized to cographs in [24]; that is, in cographs, only P3 (corresponding to duplicate vertices) may be found as an MC corresponding to a vector in Bmin. Therefore it is sufficient to have just P4 as a forbidden subgraph for a graph to have only core order two contributing to the nullity.Theorem 6.4.
All MCs with core order at least three haveP4 as an induced subgraph.Proof.
Suppose an MC isP4-free. Then, it is a cograph. Therefore, the only MC to contribute to the nullity is P3 of core order two. We deduce that all other MCs, which have core order at least three, are not cographs.SinceP4 is self-complementary, it follows that the complement of an MC with core order at least three also has P4 as an induced subgraph. Figures 8(b) and 8(c) show P4 as an induced subgraph (dotted edges) of the MC P5C.The second largest eigenvalue ofP4 is the golden section σ:=(5-1)/2. By interlacing, we obtain the following result.Theorem 6.5.
The second largest eigenvalue of anMC≠P3 is bounded below by σ.The only MC for which the bound is known to be strict is the seven-vertex nut graph of Figure7.


## 7. The Main Characteristic Polynomial

The main eigenvalues of a graphG are closely related to the number of walks in G. The product of those factors of the minimum polynomial of G, corresponding to the main eigenvalues only, has interesting properties.Definition 7.1.
The polynomialM(G,x):=∏i=1p(x-μi) whose roots are the main eigenvalues of the adjacency matrix of a graph G is termed the main characteristic polynomial.For a proof of the following result, see [25], for instance.Lemma 7.2 (see [25], rowmain).
The main characteristic polynomialM(G,x)=xp-c0xp-1-c1xp-2-⋯-cp-2x-cp-1 has integer coefficients ci, for all i,  0≤i≤p-1.


### 7.1. The Main Eigenvalues of Antiregular Graphs

Recall thatAr has exactly one pair of either duplicates or coduplicates.Theorem 7.3.
All eigenvalues ofAr other than 0 or −1 are main.Proof.
Let Prop(r) be all eigenvalues of Ar, other than 0 or −1, are main. We prove Prop(r) by induction on r.(i)
Prop(2) refers toK2 whose only nonmain eigenvalue is −1. Prop(3) refers to P3 whose only nonmain eigenvalue is 0.
This establishes the base cases.
(ii)
Assume that Prop(r) is true for all r≤k. Therefore for a nonmain eigenvalue λ other than 0 or −1, Arx=λx implies x=0 for r≤k.(iii)
ConsiderAk+1 and let Ak+1 be its adjacency matrix.For the case when k+1 is odd and Ak+1 is connected, let Ak+1x=λx for an eigenvalue λ and x=(x1,x2,…,xk+1)≠0. It follows that, for 1≤q≤f(Π), ∑i=1k+2-qxi=(1+λ)xq and, for f(Π)+1≤q≤k+1, ∑i=1k+2-qxi=(λ)xq. Similar equations are obtained for the case when k+1 is even.
The eigenvalueλ is nonmain if and only if jtx=0, whence λ=-1 or λ=0 or x1=x2=0.
Ifv (labelled 1) is the dominating vertex of Ak+1, then, by Proposition 4.5, Ak+1-v=K1∪̇Ak-1.
Ifx1=x2=0, then x restricted to Ak-1 is an eigenvector for the same eigenvalue λ. Therefore, by the induction hypothesis x=0. Hence, λ=-1 or λ=0. The result follows by induction on r.


### 7.2. The Main Eigenvalues of Threshold Graphs

By Theorem7.3, all eigenvalues of Ar that are not 0 or −1 are main. We show that this is still the case for a threshold graph C(a1,a2,…,ar) having a1≥2 and ai≥1 for 2≤i≤r obtained from the degenerate form Ar=C(1,1,…,1) by adding duplicates and/or coduplicates.Lemma 7.4.
A graph has the same number of main eigenvalues as its complement.Proof.
LetGC be the adjacency matrix of the complement of a graph G and J the matrix with each entry equal to one. Then, G+GC=J-I. Now λ is a nonmain eigenvalue of G if and only if Jx=0. Hence, G and GC share the same eigenvectors only for nonmain eigenvalues.Theorem 7.5.
LetG be a threshold graph. All eigenvalues, other than 0 or −1, are main.Proof.
LetG be C(a1,a2,…,ar),a1≥2,ai≥1 for 2≤i≤r. Let the proposition Prop(r) be all eigenvalues of C(a1,a2,…,ar) other than 0 or −1, are main. We prove Prop(r) by induction on r.(i)
IfG=C(a1,a2),a1≥2,a2≥1, then G is not regular. Hence, the number of main eigenvalues is at least two. The other distinct eigenvalues, 0 and/or −1, are nonmain. By Theorem 5.7, G has at least n-2 nonmain eigenvalues equal to 0 or −1. Thus, the number of main eigenvalues of G is two. This establishes the base case, namely, Prop(2).(ii)
The induction hypothesis is as follows: assume that Prop(k) is true.(iii)
We show that this is also true for a nondegenerateH=C(a1,a2,…,ak+1).The complement H̅ of H is C(a1,a2,…,ak)∪̇ak+1K1. By Lemma 7.4, H and H¯ have the same number of main eigenvalues. One of the ak+1 isolated vertices in H¯ contributes to the number of main eigenvalues. By the induction hypothesis, C(a1,a2,…,ak) has k main eigenvalues and ∑i=1k(ai-1) nonmain eigenvalues. Hence, H has k+1 main eigenvalues. The result follows by induction on r.We deduce immediately a spectral property of a threshold graph and its underlying antiregular graph.Corollary 7.6.
The nondegenerate threshold graphC(a1,a2,…,ar) and its underlying Ar have r and r-1 main eigenvalues, respectively.An equitable partitionΠ:=𝒱1,𝒱2,…,𝒱r of the vertex set of a graph satisfies GX=XQ, where X is the n×r indicator matrix whose ith column is the characteristic 0-1-vector associated with the ith part, containing |𝒱i| entries equal to 1. The matrix Q turns out to be the adjacency matrix of the quotient graph G/Π (also known as divisor).Lemma 7.7.
The main part of the spectrum ofG is included in the spectrum of Q.Proof.
Letλ be a main eigenvalue of G. Then, Gx=λx, where jtx≠0. Since GX=XQ, λxtX=xtGX=(xtX)Q so that λ(Xtx)=Q(Xtx). Thus, the eigenvalue λ of G is also an eigenvalue of Q, provided that Xtx≠0. Indeed this is the case when λ is a main eigenvalue, since xt·X,j=x.j≠0. Thus, the main part of the spectrum of G is contained in the spectrum of Q.We now show that the main part of the spectrum ofG=C(a1,a2,…,ar) is precisely the spectrum of Q. Consider the equitable vertex partition Π for G=C(a1,a2,…,ar) as outlined in Section 3.2.Theorem 7.8.
Let the threshold graphG=C(a1,a2,a3,…,ar) have η duplicates, η¯ coduplicates, and an equitable partition Π corresponding to the parts {ai}. Let Q be the adjacency matrix of the quotient graph G/Π. Then, ϕ(G,λ)=λη(1+λ)η¯ϕ(Q,λ), where ϕ(Q) is the main characteristic polynomial M(G,λ) of G.Proof.
The vertex labelling Lab1 is used. Let the vertices be labelled in order starting from those corresponding toa1, followed by those for a2 and so on. If X is the n×r indicator matrix whose ith column is the characteristic 0-1-vector associated with ai containing exactly ai nonzero entries (each equal to 1), then GX=XQ, where Q is r×r. Now, by Theorem 7.5, in a threshold graph, 0 and −1 are the only nonmain eigenvalues and these correspond to duplicates and coduplicates, respectively. Therefore, the number of main eigenvalues of G is exactly r. Since the main spectrum of G is contained in the spectrum of Q and Q is r×r, then the roots of ϕ(Q) are the main eigenvalues of G.We give an example to clarify the procedure. Consider the threshold graphG=C(2,2,1,2,1,2) (Lab1), of Figure 3. We use the adjacency matrix G and indicator matrix X, indexed according to Lab2:
(7.1)G=(0111111111101111111111011111101110111110111011110011110111001111110000111111000011110000001100000000),X=(100000100000010000010000001000001000000100000100000010000001).
The rows of Q are the distinct rows of GX. Therefore,
(7.2)Q=(122211212210221200222000220000200000).
Its spectrum is 7.16, 0.892, 0.448, −1.40, −1.59, −2.50, which is precisely the main part of the spectrum of G.Forℓ≥0, the entries of Gℓj give the number of walks of length ℓ from each vertex v of G. The n×k matrix whose ℓth column is Gℓ-1j is denoted by Wk. The dimension of the subspace ColSp(Wk) generated by the columns of Wk is the rank of Wk.Theorem 7.9 (see [26]).
For a graph withp main eigenvalues, the rank, dim(ColSp(Wk)), of the n×k matrix Wk=(j,Gj,G2j,…,Gk-1j) is p, for k≥p.The columnsj,Gj,G2j,⋯,Gp-1j are a maximal set of linearly independent vectors in ColSp(Wk). Thus, the first p columns provide all the information on the number of walks from each vertex of any length [27].Definition 7.10.
The matrixWp=(j,Gj,G2j,…,Gp-1j) of rank p is said to be the walk matrixW.Note thatW has the least number of columns for a walk matrix Wk to reach the maximum rank possible which is p. From Corollary 7.6, C(a1,a2,a3,…,ar) has r main eigenvalues.Theorem 7.11.
The rank of the walk matrix ofC(a1,a2,a3,…,ar) is r.The number of walks of lengthk can be expressed in terms of the main eigenvalues [28, page 46].Theorem 7.12.
The numberwk of walks of length k  starting from any vertex of G is given by
(7.3)wk=∑i=1pci′μik,
where ci′∈ℝ∖{0} is independent of k for each i and μ1,μ2,…,μp are the main eigenvalues of G.Since 0 is never a main eigenvalue ofC(a1,a2,a3,…,ar), it follows that all the main eigenvalues of C(a1,a2,a3,…,ar) contribute to the number of walks.


### 7.3. Cases of Reducible Main Polynomial

By Theorem7.3, only one eigenvalue of Ar is not main. Recall that the minimal equitable vertex partition of G=C(a1,a2,a3,…,ar) satisfies GX=XQ, where Q is the adjacency matrix of the quotient graph G/Π and ϕ(Q,λ)=M(G,λ), the main characteristic polynomial M(G,λ) of G.We note that for many threshold graphsϕ(Q,λ) is irreducible over the integers. For example the only eigenvalue of A8=C(1,1,1,1,1,1,1,1) (in degenerate form) which is not main is −1 and M(A8,x)=(1-7x+9x2+15x3-13x4-15x5-x6+x7), which is irreducible.Now we add vertices to the degenerate formA8=C(1,1,1,1,1,1,1,1). If we add a vertex to the first part, to obtain G1=C(2,1,1,1,1,1,1,1), a negative eigenvalue (not −1) and 0 appear. The eigenvalue −1 is lost and M(G1,x)=(2-12x+6x2+40x3-40x5-20x6+x8). When a vertex is added to the third part to obtain G3=C(2,2,1,1,1,1,1), the eigenvalue −1 is retained while the zero eigenvalue appears and M(G3,x)=(2-12x+12x2+22x3-16x4-18x5-x6+x7). In both these latter two cases ϕ(Q,λ) is irreducible over the integers. Now when a vertex is added to the seventh part to obtain G7=C(2,1,1,1,1,2,1), the eigenvalue −1 is retained while the zero eigenvalue appears. In this case, however, M(G7,x)=(x2+2x-1)(x5-3x4-9x2+3x3+8x-2), and therefore it is reducible over the integers.This is also the case for some instances of the threshold graphsC(d,1,t) when the cubic polynomial ϕ(Q,λ) has an integer as a root and therefore is reducible. The divisor Q is (d-10t00td1t-1) with characteristic polynomial ϕ(Q,λ)=-t+dt+λ-dλ-2tλ+2λ2-dλ2-tλ2+λ3.Ifλ is 0, 2 or 3, there are no integral values of t and d satisfying the polynomial ϕ(Q,λ). If λ=1, the graph either for t=3 and d=8 or for t=4 and d=6 satisfies it. Also for λ=-2 either the graph for t=3 and d=5, or t=4 and d=3, or t=6 and d=2 satisfies it, while for λ=-3, the graph for t=7 and d=40 satisfies it.


## 7.1. The Main Eigenvalues of Antiregular Graphs

Recall thatAr has exactly one pair of either duplicates or coduplicates.Theorem 7.3.
All eigenvalues ofAr other than 0 or −1 are main.Proof.
Let Prop(r) be all eigenvalues of Ar, other than 0 or −1, are main. We prove Prop(r) by induction on r.(i)
Prop(2) refers toK2 whose only nonmain eigenvalue is −1. Prop(3) refers to P3 whose only nonmain eigenvalue is 0.
This establishes the base cases.
(ii)
Assume that Prop(r) is true for all r≤k. Therefore for a nonmain eigenvalue λ other than 0 or −1, Arx=λx implies x=0 for r≤k.(iii)
ConsiderAk+1 and let Ak+1 be its adjacency matrix.For the case when k+1 is odd and Ak+1 is connected, let Ak+1x=λx for an eigenvalue λ and x=(x1,x2,…,xk+1)≠0. It follows that, for 1≤q≤f(Π), ∑i=1k+2-qxi=(1+λ)xq and, for f(Π)+1≤q≤k+1, ∑i=1k+2-qxi=(λ)xq. Similar equations are obtained for the case when k+1 is even.
The eigenvalueλ is nonmain if and only if jtx=0, whence λ=-1 or λ=0 or x1=x2=0.
Ifv (labelled 1) is the dominating vertex of Ak+1, then, by Proposition 4.5, Ak+1-v=K1∪̇Ak-1.
Ifx1=x2=0, then x restricted to Ak-1 is an eigenvector for the same eigenvalue λ. Therefore, by the induction hypothesis x=0. Hence, λ=-1 or λ=0. The result follows by induction on r.


## 7.2. The Main Eigenvalues of Threshold Graphs

By Theorem7.3, all eigenvalues of Ar that are not 0 or −1 are main. We show that this is still the case for a threshold graph C(a1,a2,…,ar) having a1≥2 and ai≥1 for 2≤i≤r obtained from the degenerate form Ar=C(1,1,…,1) by adding duplicates and/or coduplicates.Lemma 7.4.
A graph has the same number of main eigenvalues as its complement.Proof.
LetGC be the adjacency matrix of the complement of a graph G and J the matrix with each entry equal to one. Then, G+GC=J-I. Now λ is a nonmain eigenvalue of G if and only if Jx=0. Hence, G and GC share the same eigenvectors only for nonmain eigenvalues.Theorem 7.5.
LetG be a threshold graph. All eigenvalues, other than 0 or −1, are main.Proof.
LetG be C(a1,a2,…,ar),a1≥2,ai≥1 for 2≤i≤r. Let the proposition Prop(r) be all eigenvalues of C(a1,a2,…,ar) other than 0 or −1, are main. We prove Prop(r) by induction on r.(i)
IfG=C(a1,a2),a1≥2,a2≥1, then G is not regular. Hence, the number of main eigenvalues is at least two. The other distinct eigenvalues, 0 and/or −1, are nonmain. By Theorem 5.7, G has at least n-2 nonmain eigenvalues equal to 0 or −1. Thus, the number of main eigenvalues of G is two. This establishes the base case, namely, Prop(2).(ii)
The induction hypothesis is as follows: assume that Prop(k) is true.(iii)
We show that this is also true for a nondegenerateH=C(a1,a2,…,ak+1).The complement H̅ of H is C(a1,a2,…,ak)∪̇ak+1K1. By Lemma 7.4, H and H¯ have the same number of main eigenvalues. One of the ak+1 isolated vertices in H¯ contributes to the number of main eigenvalues. By the induction hypothesis, C(a1,a2,…,ak) has k main eigenvalues and ∑i=1k(ai-1) nonmain eigenvalues. Hence, H has k+1 main eigenvalues. The result follows by induction on r.We deduce immediately a spectral property of a threshold graph and its underlying antiregular graph.Corollary 7.6.
The nondegenerate threshold graphC(a1,a2,…,ar) and its underlying Ar have r and r-1 main eigenvalues, respectively.An equitable partitionΠ:=𝒱1,𝒱2,…,𝒱r of the vertex set of a graph satisfies GX=XQ, where X is the n×r indicator matrix whose ith column is the characteristic 0-1-vector associated with the ith part, containing |𝒱i| entries equal to 1. The matrix Q turns out to be the adjacency matrix of the quotient graph G/Π (also known as divisor).Lemma 7.7.
The main part of the spectrum ofG is included in the spectrum of Q.Proof.
Letλ be a main eigenvalue of G. Then, Gx=λx, where jtx≠0. Since GX=XQ, λxtX=xtGX=(xtX)Q so that λ(Xtx)=Q(Xtx). Thus, the eigenvalue λ of G is also an eigenvalue of Q, provided that Xtx≠0. Indeed this is the case when λ is a main eigenvalue, since xt·X,j=x.j≠0. Thus, the main part of the spectrum of G is contained in the spectrum of Q.We now show that the main part of the spectrum ofG=C(a1,a2,…,ar) is precisely the spectrum of Q. Consider the equitable vertex partition Π for G=C(a1,a2,…,ar) as outlined in Section 3.2.Theorem 7.8.
Let the threshold graphG=C(a1,a2,a3,…,ar) have η duplicates, η¯ coduplicates, and an equitable partition Π corresponding to the parts {ai}. Let Q be the adjacency matrix of the quotient graph G/Π. Then, ϕ(G,λ)=λη(1+λ)η¯ϕ(Q,λ), where ϕ(Q) is the main characteristic polynomial M(G,λ) of G.Proof.
The vertex labelling Lab1 is used. Let the vertices be labelled in order starting from those corresponding toa1, followed by those for a2 and so on. If X is the n×r indicator matrix whose ith column is the characteristic 0-1-vector associated with ai containing exactly ai nonzero entries (each equal to 1), then GX=XQ, where Q is r×r. Now, by Theorem 7.5, in a threshold graph, 0 and −1 are the only nonmain eigenvalues and these correspond to duplicates and coduplicates, respectively. Therefore, the number of main eigenvalues of G is exactly r. Since the main spectrum of G is contained in the spectrum of Q and Q is r×r, then the roots of ϕ(Q) are the main eigenvalues of G.We give an example to clarify the procedure. Consider the threshold graphG=C(2,2,1,2,1,2) (Lab1), of Figure 3. We use the adjacency matrix G and indicator matrix X, indexed according to Lab2:
(7.1)G=(0111111111101111111111011111101110111110111011110011110111001111110000111111000011110000001100000000),X=(100000100000010000010000001000001000000100000100000010000001).
The rows of Q are the distinct rows of GX. Therefore,
(7.2)Q=(122211212210221200222000220000200000).
Its spectrum is 7.16, 0.892, 0.448, −1.40, −1.59, −2.50, which is precisely the main part of the spectrum of G.Forℓ≥0, the entries of Gℓj give the number of walks of length ℓ from each vertex v of G. The n×k matrix whose ℓth column is Gℓ-1j is denoted by Wk. The dimension of the subspace ColSp(Wk) generated by the columns of Wk is the rank of Wk.Theorem 7.9 (see [26]).
For a graph withp main eigenvalues, the rank, dim(ColSp(Wk)), of the n×k matrix Wk=(j,Gj,G2j,…,Gk-1j) is p, for k≥p.The columnsj,Gj,G2j,⋯,Gp-1j are a maximal set of linearly independent vectors in ColSp(Wk). Thus, the first p columns provide all the information on the number of walks from each vertex of any length [27].Definition 7.10.
The matrixWp=(j,Gj,G2j,…,Gp-1j) of rank p is said to be the walk matrixW.Note thatW has the least number of columns for a walk matrix Wk to reach the maximum rank possible which is p. From Corollary 7.6, C(a1,a2,a3,…,ar) has r main eigenvalues.Theorem 7.11.
The rank of the walk matrix ofC(a1,a2,a3,…,ar) is r.The number of walks of lengthk can be expressed in terms of the main eigenvalues [28, page 46].Theorem 7.12.
The numberwk of walks of length k  starting from any vertex of G is given by
(7.3)wk=∑i=1pci′μik,
where ci′∈ℝ∖{0} is independent of k for each i and μ1,μ2,…,μp are the main eigenvalues of G.Since 0 is never a main eigenvalue ofC(a1,a2,a3,…,ar), it follows that all the main eigenvalues of C(a1,a2,a3,…,ar) contribute to the number of walks.


## 7.3. Cases of Reducible Main Polynomial

By Theorem7.3, only one eigenvalue of Ar is not main. Recall that the minimal equitable vertex partition of G=C(a1,a2,a3,…,ar) satisfies GX=XQ, where Q is the adjacency matrix of the quotient graph G/Π and ϕ(Q,λ)=M(G,λ), the main characteristic polynomial M(G,λ) of G.We note that for many threshold graphsϕ(Q,λ) is irreducible over the integers. For example the only eigenvalue of A8=C(1,1,1,1,1,1,1,1) (in degenerate form) which is not main is −1 and M(A8,x)=(1-7x+9x2+15x3-13x4-15x5-x6+x7), which is irreducible.Now we add vertices to the degenerate formA8=C(1,1,1,1,1,1,1,1). If we add a vertex to the first part, to obtain G1=C(2,1,1,1,1,1,1,1), a negative eigenvalue (not −1) and 0 appear. The eigenvalue −1 is lost and M(G1,x)=(2-12x+6x2+40x3-40x5-20x6+x8). When a vertex is added to the third part to obtain G3=C(2,2,1,1,1,1,1), the eigenvalue −1 is retained while the zero eigenvalue appears and M(G3,x)=(2-12x+12x2+22x3-16x4-18x5-x6+x7). In both these latter two cases ϕ(Q,λ) is irreducible over the integers. Now when a vertex is added to the seventh part to obtain G7=C(2,1,1,1,1,2,1), the eigenvalue −1 is retained while the zero eigenvalue appears. In this case, however, M(G7,x)=(x2+2x-1)(x5-3x4-9x2+3x3+8x-2), and therefore it is reducible over the integers.This is also the case for some instances of the threshold graphsC(d,1,t) when the cubic polynomial ϕ(Q,λ) has an integer as a root and therefore is reducible. The divisor Q is (d-10t00td1t-1) with characteristic polynomial ϕ(Q,λ)=-t+dt+λ-dλ-2tλ+2λ2-dλ2-tλ2+λ3.Ifλ is 0, 2 or 3, there are no integral values of t and d satisfying the polynomial ϕ(Q,λ). If λ=1, the graph either for t=3 and d=8 or for t=4 and d=6 satisfies it. Also for λ=-2 either the graph for t=3 and d=5, or t=4 and d=3, or t=6 and d=2 satisfies it, while for λ=-3, the graph for t=7 and d=40 satisfies it.


## 8. Sign Pattern of the Spectrum of a Threshold Graph

We conclude with a note on the distribution of the eigenvalues of a threshold graph. In [29] it was remarked that an antiregular graph has a bipartite character, that is, the number r- of negative eigenvalues is equal to the number r+ of positive ones. We denote the number of zero eigenvalues by η.


### 8.1. The Spectrum ofAr

Forn≥4, Ar is not bipartite. Therefore, -λmin≠λmax. The proof of the next result is by induction on the order of the antiregular graph. We will need the following evident fact.Lemma 8.1.
To transformAr to Ar+1 (according to the labelling (Lab2) of the stepwise adjacency matrix),(i)
a vertex duplicate to the⌈(r+1)/2⌉th is added for even r,(ii)
a vertex coduplicate to the⌈(r+1)/2⌉th is added for odd r.Theorem 8.2.
r+=r- for Ar.Proof.
The proof is by induction onr.
The spectra of the three smallest antiregular graphs,Sp(A1)={0}, Sp(A2)={-1,1}, and Sp(A3)={-2,0,2}, establish the base cases.
Assume that the theorem is true forAk.
We prove it true forAk+1.
IfAk is singular, then it has a duplicate vertex and k is odd. By the induction hypothesis r+=r-.
If, on the other hand,Ak is nonsingular, then Ak has a coduplicate vertex and k is even. Again the nonzero eigenvalues satisfy r+=r-.
We apply Lemma8.1, using Lab2. For odd k, if a vertex w, coduplicate to the ⌈(r+1)/2⌉th vertex, is added to Ak, then only one of the duplicate vertices of Ak will have w as a neighbour in Ak+1. The zero eigenvalue of Ak vanishes and the eigenvalue −1 is introduced for Ak+1. By the Perron Frobenius theorem adding edges to a graph (Ak∪̇K1) increases the maximum eigenvalue. Therefore, by interlacing, the number of positive eigenvalues increases by one. Since the new coduplicate vertex w contributes the new eigenvalue −1 to the spectrum, it follows that r+=r- will be satisfied in Ak+1. By interlacing, adding a duplicate vertex to any graph retains the number of positive and negative eigenvalues and adds 0 to the spectrum. For even k, if a vertex w, duplicate to the ⌈(r+1)/2⌉th vertex, is added, then a duplicate vertex is added to the graph, retaining r+=r-.
The result follows by induction onn.


### 8.2. The Spectrum of a Threshold Graph

In this section, we shall represent the antiregular graphAr by the degenerate form C(1,1,…,1). As in Section 4, any part can be expanded to produce a threshold graph C(a1,a2,…,ar). We need the following evident facts regarding the effect on the distribution of the spectrum of the adjacency matrix when a vertex is added.Lemma 8.3.
If on adding a vertex to a graph (i) the multiplicity of an eigenvalueλ0 of the adjacency matrix increases, then, by interlacing, the number n-(λ0) of eigenvalues less than λ0 and the number n+(λ0) greater than λ0 remain the same; (ii) the multiplicity of an eigenvalue λ0 of the adjacency matrix decreases, then by interlacing, each of the numbers n+(λ0) and n-(λ0) increases by one.We shall writen+ for n+(0) and n- for n-(0).First we see an application of Lemma8.3(i) using Lab1. For even r, if one of the even indexed ai, for i≥2, of C(a1,a2,a3,…,ar) is increased, then a coduplicate of a vertex is added. This forces η and n+ to remain unchanged while each of n- and the multiplicity m(-1) of the eigenvalue −1 increases by one. If the odd indexed ai, for some i≥1, is increased, then a duplicate of a vertex is added forcing n+ and n- to remain unchanged.Similarly, for oddr, if the even indexed ai, for some i≥2, is increased, then a duplicate of a vertex is added. This forces n- and n+ to remain unchanged while η increases by one. If the odd indexed ai, for some i≥3, is increased, then a coduplicate of a vertex is added forcing n+ and η to remain unchanged.The case for evenr and a1>1 is the same as for odd r with a1=1 (Lab1). Taking C(a1,a2,a3,…,ar) for odd r with a1=1 and expanding to C(a1,a2,a3,…,ar) with a1>1 gives the unique case where η decreases by one and m(-1) increases by one. Since η decreases by one, by Lemma 8.3(ii), each of n+ and n- increases by one, the latter corresponding to the increase in the multiplicity of the eigenvalue −1. We have proved the following result.Theorem 8.4.
If the threshold graphC(a1,a2,…,ar) is transformed to another threshold graph by increasing exactly one of the ais by one, then
(8.1){ifaduplicateisadded,thenn-andn+areunchangedandηincreases;ifacoduplicateisadded,andifriseventhenηandn+areunchangedorifrisoddandai≥3orifrisoddanda1>1,andn-increases;ifacoduplicateisadded,andifrisoddanda1=1thenn-andn+increaseandηdecreases.


## 8.1. The Spectrum ofAr

Forn≥4, Ar is not bipartite. Therefore, -λmin≠λmax. The proof of the next result is by induction on the order of the antiregular graph. We will need the following evident fact.Lemma 8.1.
To transformAr to Ar+1 (according to the labelling (Lab2) of the stepwise adjacency matrix),(i)
a vertex duplicate to the⌈(r+1)/2⌉th is added for even r,(ii)
a vertex coduplicate to the⌈(r+1)/2⌉th is added for odd r.Theorem 8.2.
r+=r- for Ar.Proof.
The proof is by induction onr.
The spectra of the three smallest antiregular graphs,Sp(A1)={0}, Sp(A2)={-1,1}, and Sp(A3)={-2,0,2}, establish the base cases.
Assume that the theorem is true forAk.
We prove it true forAk+1.
IfAk is singular, then it has a duplicate vertex and k is odd. By the induction hypothesis r+=r-.
If, on the other hand,Ak is nonsingular, then Ak has a coduplicate vertex and k is even. Again the nonzero eigenvalues satisfy r+=r-.
We apply Lemma8.1, using Lab2. For odd k, if a vertex w, coduplicate to the ⌈(r+1)/2⌉th vertex, is added to Ak, then only one of the duplicate vertices of Ak will have w as a neighbour in Ak+1. The zero eigenvalue of Ak vanishes and the eigenvalue −1 is introduced for Ak+1. By the Perron Frobenius theorem adding edges to a graph (Ak∪̇K1) increases the maximum eigenvalue. Therefore, by interlacing, the number of positive eigenvalues increases by one. Since the new coduplicate vertex w contributes the new eigenvalue −1 to the spectrum, it follows that r+=r- will be satisfied in Ak+1. By interlacing, adding a duplicate vertex to any graph retains the number of positive and negative eigenvalues and adds 0 to the spectrum. For even k, if a vertex w, duplicate to the ⌈(r+1)/2⌉th vertex, is added, then a duplicate vertex is added to the graph, retaining r+=r-.
The result follows by induction onn.


## 8.2. The Spectrum of a Threshold Graph

In this section, we shall represent the antiregular graphAr by the degenerate form C(1,1,…,1). As in Section 4, any part can be expanded to produce a threshold graph C(a1,a2,…,ar). We need the following evident facts regarding the effect on the distribution of the spectrum of the adjacency matrix when a vertex is added.Lemma 8.3.
If on adding a vertex to a graph (i) the multiplicity of an eigenvalueλ0 of the adjacency matrix increases, then, by interlacing, the number n-(λ0) of eigenvalues less than λ0 and the number n+(λ0) greater than λ0 remain the same; (ii) the multiplicity of an eigenvalue λ0 of the adjacency matrix decreases, then by interlacing, each of the numbers n+(λ0) and n-(λ0) increases by one.We shall writen+ for n+(0) and n- for n-(0).First we see an application of Lemma8.3(i) using Lab1. For even r, if one of the even indexed ai, for i≥2, of C(a1,a2,a3,…,ar) is increased, then a coduplicate of a vertex is added. This forces η and n+ to remain unchanged while each of n- and the multiplicity m(-1) of the eigenvalue −1 increases by one. If the odd indexed ai, for some i≥1, is increased, then a duplicate of a vertex is added forcing n+ and n- to remain unchanged.Similarly, for oddr, if the even indexed ai, for some i≥2, is increased, then a duplicate of a vertex is added. This forces n- and n+ to remain unchanged while η increases by one. If the odd indexed ai, for some i≥3, is increased, then a coduplicate of a vertex is added forcing n+ and η to remain unchanged.The case for evenr and a1>1 is the same as for odd r with a1=1 (Lab1). Taking C(a1,a2,a3,…,ar) for odd r with a1=1 and expanding to C(a1,a2,a3,…,ar) with a1>1 gives the unique case where η decreases by one and m(-1) increases by one. Since η decreases by one, by Lemma 8.3(ii), each of n+ and n- increases by one, the latter corresponding to the increase in the multiplicity of the eigenvalue −1. We have proved the following result.Theorem 8.4.
If the threshold graphC(a1,a2,…,ar) is transformed to another threshold graph by increasing exactly one of the ais by one, then
(8.1){ifaduplicateisadded,thenn-andn+areunchangedandηincreases;ifacoduplicateisadded,andifriseventhenηandn+areunchangedorifrisoddandai≥3orifrisoddanda1>1,andn-increases;ifacoduplicateisadded,andifrisoddanda1=1thenn-andn+increaseandηdecreases.


## 9. Conclusion

The simple graphic appeal of the Ferrers/Young diagramF(Π), with rows representing the degree sequence of a n-vertex threshold graph has been instrumental to obtain interesting results on the nullity and structure of the graph. The shape of F(Π) has been also used to determine the nature of the eigenvalues as main or nonmain.LetD be the diagonal entries whose nonzero entries are the vertex degrees for some labelling of the vertices. Like the adjacency matrix A, the Laplacian D-A also gives a wealth of information about the graph. It is well known that the class of graphs for which the Laplacian spectrum and the conjugate degree sequence π* (i.e., the lengths of the columns of F(Π)) coincide is exactly the class of threshold graphs [30, Chapter 10]. The Grone-Merris Conjecture, asserting that the spectrum of the Laplacian matrix of a finite graph is majorized by the conjugate degree sequence of the graph, has been recently proved by Bai [31].



---

*Source: 108509-2012-01-17.xml*