{'fraction_non_alphanumeric': 0.05028413454154508, 'fraction_numerical': 0.013024113039471664, 'mean_word_length': 3.9878964302129614, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Laplacian Controllability of Threshold Graphs

This paper is concerned with the controllability problem of a connected threshold graph following the Laplacian dynamics. An algorithm is proposed to generate a spanning set of orthogonal Laplacian eigenvectors of the graph from a straightforward computation on its Laplacian matrix. A necessary and sufficient condition for the graph to be Laplacian controllable is then proposed. The condition suggests that the minimum number of controllers to render a connected threshold graph controllable is the maximum multiplicity of entries in the conjugate of the degree sequence determining the graph, and this minimum can be achieved by a binary control matrix. The second part of the work is the introduction of a novel class of single-input controllable graphs, which is constructed by connecting two antiregular graphs with almost the same size. This new connecting structure reduces the sum of the maximum vertex degree and the diameter by almost one half, compared to other well-known single-input controllable graphs such as the path and the antiregular graph, and has potential applications in the design of controllable graphs subject to practical edge constraints. Examples are provided to illustrate our results.


I. INTRODUCTION
Recently, many research efforts have been invested in the study of distributed and cooperative operations of multi-agent networks [1]- [3]. Special synchronization property and various consensus issues for heterogeneous or homogeneous systems with constraints or uncertainties were extensively studied [4]- [7]. The simplicity of network units and scalability of network structure make such systems a promising solution for many engineering challenges in the automation, manufacturing, monitoring, intelligent transportation, and so on. Rather than on centralized coordination or control, a multi-agent system relies on the exchange of local information to reach certain system-wide goals. An immediate question is how the system leverages the network connectivity to ensure effective and efficient information propagation and complete assigned jobs? To set up a platform for the analysis, a frequently utilized measure is to consider the network from the perspective of a connected graph [8], namely, using the nodes (or called vertices) to represent agents and edges to describe the local interactions of the network. Under this framework, the system evolution can be defined based on the specified dynamics. A fundamental issue that draws many attentions of researchers in the control theory community is the system controllability. This property directly reflects the effectiveness of control mechanism and is particularly essential in a large-scale system [9]. Suppose an agent is represented by a state variable, and the status of the agent, or the value of the variable, is directly influenced by its neighboring agents, namely, those agents directly connected to it. Under mild conditions such as the time-invariance of the connection parameters and the so-called consensus policy, the formulation leads naturally to the classical liner and time-invariant (LTI) control system evolving according to the Laplacian dynamics. In terms of multi-agent systems, this formulation is often called the leader-follower control dynamics. The leader agents are actually the independent input signals and maneuver the follower agents to particular status. While several methods including the well-known Kalman test are available, checking the Laplacian controllability of Shun-Pin Hsu is with the Department of Electrical Engineering, National Chung Hsing University, Taichung, 402, Taiwan, e-mail: (shsu@nchu.edu.tw).
multi-agent systems defined on connected graphs is never trivial. The major challenges come from the numerical instability in dealing with the large number of state variables in complex systems. To overcome, graph-theoretic techniques are proposed to analyze the connection patterns and to identify the structure symmetry known as the equitable partition. Existence of such symmetry serves as a sufficient condition for system uncontrollability [10]. A weaker version of the sufficient condition based on the so-called relaxed equitable partition, or almost equitable partition (AEP) [11] was later proposed [12]. However, failing to satisfy these conditions leaves the Laplacian controllability of the connected graphs inconclusive. Following the line of the partition scheme, upper and lower bounds that make elegant use of the information on the AEP and on the so-called distance partition respectively were presented for the dimension of controllable subspace of state variables [13]. These bounds are useful in the design of a Laplacian controllable graph. Unfortunately, the gap between the upper and lower bounds is narrow only in some extreme cases such as the path graph. The process of exploring graph-theoretic methods based on partition schemes is still far from completed. In practice, system architects might need to design various connection structures for networks. To them, a sufficient condition for system controllability is preferable to that for uncontrollability. Since this preferred condition easily applicable to a large-sized graph is not available in general, special classes of graphs were studied and their controllability issues were partially or totally solved. Examples include the paths [14], multi-chain [15], grids [16], circulant graphs [17], and complete graphs [18]. The eigenspaces of these graphs follow specific patterns and thus are analyzable using the well-known Popov-Belevitch-Hautus (PBH) test. Nevertheless, the class of known Laplacian controllable graphs are still insufficient and are in great need of expansion. In this work we continue to explore the class of controllable graphs and focus on threshold graphs, which have many applications in synchronizing process, cyclic scheduling, Guttman scales and so on [19]. We only consider the connected graphs throughout the paper to avoid the apparent uncontrollability due to the disconnection. A connected threshold graph can be uniquely determined from its degree sequence, or from a sequence of vertex add-ins via union or join operation starting from an isolated vertex. Its Laplacian eigenvalues, all integers, are actually the entries in the conjugate of its degree sequence [20]. Using this property, it was shown that for a threshold graph, it is single-input controllable if and only if it is an connected antiregular graph, namely, it is connected and has exactly two vertices with the same degree. The necessary and sufficient condition for a binary control vector to render the system controllable was also provided [21]. This result was later extended to the multi-input case where more vertices with the same degree were considered [22]. In this work we generalize these results to any connected and unweighted threshold graphs and study their controllability conditions under the general, binary and terminal control matrices respectively (a control matrix is terminal if each column of the matrix has only one nonzero entry). Moreover, we study a novel structure closely related to an antiregular graph. The study is motivated by the desire to find a single-input controllable graph that has different connecting statistics from that of the path or the antiregular graph [23]. In practice, to prevent a long response time, an upper bound might be imposed on the graph diameter; to reduce the operation or maintenance complexity of a single unit, an upper bound might be imposed on each vertex degree as well. A k-vertex path has its edge degrees bounded above by 2, and its diameter by k − 1. A k-vertex antiregular graph has the maximum edge degree k − 1 and diameter 2. In both cases the sum of these two parameters is k + 1. We propose to combine two antiregular graphs with nearly equal number of vertices and reduce the sum to k 2 + 4 and k+1 2 + 4 for even and odd k respectively, while ensuring the single-input controllability of the resulting graph.
The contributions of our results are twofold. Firstly, we propose a simple algorithm to generate a complete set of orthogonal Laplacian eigenvectors of a connected threshold graph. These vectors are obtained from a straightforward computation on the entries of the Laplacian matrix. Based on this result, we propose the necessary and sufficient condition for a connected threshold graph to be Laplacian controllable. In particular, we show that if the control matrix is binary, checking the controllability of a connected threshold graph is equivalent to checking the controllability of several intermediate connected threshold graphs generated in the entire construction process of the graph. Our result suggests that the difficulty in checking the controllability is not directly related to the number of vertices of the entire graph but mainly to that of equal degrees. The knowledge of Laplacian eigenspaces of the graph allows one to check the controllability locally and efficiently. Furthermore, we prove that under general and binary control matrices, the minimum number of controllers rendering the graph controllable is the same as the largest multiplicity of Laplcian eigenvalues; however, if the control matrix is terminal, the minimum number is the difference between the number of vertices and the number of vertices with different degrees. The second contribution of the paper is the introduction of a new class of single-input controllable graphs obtained by connecting two antiregular graphs. This novel class of graphs is unique in the following two senses: 1) it does not belong to any known family that has completely tractable Laplacian eigenspaces; 2) it has a much smaller sum of diameter and the maximum vertex degree, compared to that of a path or an antiregular graph. Our result demonstrates how adding one edge affects the Laplacian controllability of a graph, and thus has potential applications to the design of controllable graphs subject to edge constraints.

II. PRELIMINARIES
We define several standard notations and review some concepts used throughout the paper before starting our discussion. Let R and N be the sets of real and natural numbers, respectively, and 1 and 0 the column vectors of 1's and 0's, respectively. We use I to represent the identity matrix with appropriate sizes and ei, e−i are the ith and the ith to last column vectors, respectively, of I. Define the index set I k := {1, 2, · · · k}. A vector u is called the i to j For two sets S1 and S2, the set difference S1 \ S2 is defined as {s|s ∈ S1, s / ∈ S2}. The floor and ceiling function of x, i.e., ⌊x⌋ and ⌈x⌉, are the largest integer not greater than x and the smallest integer not less than x, respectively. Suppose λ ∈ R, v ∈ R n , and P is a matrix of order n, meaning that P ∈ R n×n . We call (λ, v) an eigenpair of P if P v = λv. If V = I k and E is a subset of { (v1, v2) | v1, v2 ∈ V }, then (V, E) describes a k-vertex graph, or a graph on k vertices, where V and E are called the vertex set and edge set respectively, of the graph. A path between vertices v1 and v2 is a subset {(v1, u1), (u1, u2), (u2, u3), · · · , (um−1, um), (um, v2)} of E where u1, u2, · · · , um ∈ V . A graph is connected if for every pair of vertices there exists a path between them. A graph is unweighted if all its connecting edges carry the same weight. A graph is undirected Fig. 1 if every entry of its edge set is not an ordered pair. A unweighted and undirected graph is simple if it has no (self) loops and no multiple edges [24]. In this work we restrict our discussion only to the class of simple and connected graphs. In a k-vertex simple graph described by (V, E), if v1, v2 ∈ V and (v1, v2) ∈ E, v1 and v2 are called neighbors. The neighbor set Nv of the vertex v is {u | (v, u) ∈ E}.
The degree of vertex v is defined as the cardinality of Nv, written as |Nv|, meaning the number of elements in Nv. A vertex v is called an isolated vertex, a terminal vertex, and a dominating vertex if |Nv| is 0, 1 and k − 1, respectively. Furthermore, define A, D, L ∈ R k×k where D is the diagonal matrix with its ith diagonal term being the degree of the ith vertex; A is the adjacent matrix of the graph, meaning that its (i, j)th element is 1 if (i, j) ∈ E and is 0 otherwise; L := D − A is the Laplacian matrix of the graph. Suppose di is the degree of the ith vertex of a k-vertex graph and satisfies di ≥ di+1 for each i ∈ I k−1 , then the degree sequence of the graph is wheredi, with multiplicity mi, satisfiesdi >di+1 for each i in Ik −1 . The conjugate of the degree sequence d is We say a sequence d of nonnegative integers is graphical if there exists a graph whose degree sequence is d. Suppose d = (d1, d2, · · · , d k ). It was shown that the necessary and sufficient condition for d to be graphical is [25, p.72 In the extreme case that the equality in (3) holds, the degree sequence determines the so called threshold graphs or maximal graphs [20]. Threshold graphs admit several equivalent definitions [19, Theorem 1.2.4]. One of the simplest ways to identify them is using the so-called Ferrers-Sylvester diagram. In Fig. 1 two degree sequences are checked using the diagram to see if they form threshold graphs. Another well-known definition is based on recursive vertex add-in operations to form the graph. Specifically, if we start from an isolated vertex and increase the number of vertices one by one, with one of the two following operations: 1) adding an isolated vertex to the graph (union); 2) adding a dominating vertex to the graph (join); the resulting graph is a threshold graph [26]. We use CT to represent the class of connected threshold graphs. A k-vertex graph in CT is written as G (k) T , and its corresponding Laplacian matrix L (k) T . The constructing process of G (k) T can be encoded with a binary string S (k) of size k − 1, whose ith element is 1 if the (i + 1)th vertex is added via the join operation, and is 0 if it is via the union operation [27]. Let S (k) = ( s1, s2, · · · , s k−1 ). Then we can write ( s1, s1, s2, s3, · · · , s k−1 ) = (s1, · · · ,s1,s2, · · · ,s2, · · · ,sk, · · · ,sk ) wheres =si+1 and the multiplicity ofsi, written as mσ i , is a permutation of mi in (1) We are particularly interested in the substrings S (k i ) , i ∈ Is, wheres is the number of successions in S (k) and the terminal 1 of each S (k i ) is preceded by a succession of 0, or is the final entry of a succession of 1. Thus G with its constructing string S (k i ) containing the first i successions of S (k) . S (k i ) with this property is called an essential substring of S (k) . A threshold graph has an integral Laplacian spectrum and tractable eigenspace since its construction involves only the graph operations of union and join [20], [28]. These properties are intimately related to our main result of generating orthogonal Laplacian eigenvectors directly from the Laplacian matrix of the graph. A special threshold graph, which allows only interlacing operations of join and union in the constructing process, or equivalently, has exactly two vertices of the same degree, is known as the antiregular graph [29]. The class of connected antiregular graphs was proved to be the only class of threshold graphs controllable by single controllers [21]. Let CA be the class of these special graphs. A k-vertex graph in CA is written as G

(k)
A and its Laplacian matrix L (k) A . Consider an autonomous linear and time-invariant (LTI) system defined on a k-vertex graph (V, E), in the sense that each system states xi evolves according to the so-called consensus policy: for each vertex i ∈ V = I k , where Ni ⊆ V , is the neighbor set of vertex i. In the matrix form we havė where x := [ x1 x2 · · · x k ] T and L is the Laplacian matrix of the graph This is known as the Laplacian dynamics [30, p.1613] on the graph (V, E). Suppose p control inputs u(t) = [ u1(t) u2(t) · · · up(t) ] T is applied to (5) via the p-control matrix B := [ b1 b2 · · · , bp ] where the (i, j)th element of B, or bij , is nonzero if vertex i is connected to input uj (t), and is 0 otherwise. B is called binary if the nonzero entry is restricted to 1, otherwise it is called general. In particular, B is called terminal if every column has only one nonzero entry. The system under control evolves according to the following equation: which is written as (L, B) for simplicity. In the single-input case, namely p = 1, the more specific notation (L, b) is used. Clearly bj records the connection information of controller j to each vertex. We saybj is a local control vector of bj subject to some vertices if bj records only the connection information of controller j to these vertices. Let S be a substring of S (k) that generates G If the last succession of S is a succession of 0, all ei's are replaced with e−i's and δ with 0. In the next section we study the Laplacian controllability problems of connected threshold graphs. The study is based on the following conclusion from the classical Popov-Belevitch-Hautus (PBH) test.
Theorem 2.1: [31] The system (L, B) defined in (6) is uncontrollable if and only if L has an eigenvector in the null space of B T .

A. Laplacian Eigenspaces of Threshold Graphs
Consider a k-vertex connected threshold graphs with degree sequence d = (d1, d2, · · · , d k ). Note that a connected threshold graph can be determined uniquely from its degree sequence (up to isomorphism). Following the definition of the degree sequence and the symmetric property of the graph in the Ferrers-Sylvester diagram, we can write its Laplacian matrix L (k) T , without loss of generality, as where x in the (i, j)th entry is 1 if vertices i and j are connected, otherwise it is 0. If the (i, j)th element ℓi,j of L (k) T is 1, then i > j implies ℓi,m = 1 for each m ∈ Ij−1, and i < j implies ℓm,j = 1 for each m ∈ Ii−1. Similarly, if ℓi,j = 0, then i > j implies ℓm,j = 0 for each m ∈ {i + 1, i + 2, · · · , k}, and i < j implies ℓi,m = 0 for each m ∈ {j + 1, j + 2, · · · , k}. To see this we can use the definition of sequential union or join operations to construct the graph and manage to align the vertices, from left to right, when the construction is complete. The rule to decide the order of each vertex in the line is: the vertex is added to the leftmost and rightmost locations of the current line of vertices if it is added via the join and union operations respectively. When we complete the k-vertex graph, we obtain a line of vertices with their degrees, from left to right, being decreasing. It turns out that a vertex with degree t where t < k, has those, excluding the vertex itself, with top t degrees as its neighbors due to the sure join operations performed after the t-edge vertex is added and possible join operations when it is added. In the following we first review and present related results that help further analysis of the Laplacian eigenspace of a connected threshold graph.
Theorem 3.1: (cf. [20]) Let τ d be the trace of d with corresponding L (k) T in (7). Let v := [ v1 · · · v k ] T be the (τ d + 1)th column of L (k) T , and for i ∈ I k , mi and m * i are the multiplicities defined in (1) and (2) respectively. We then have 2) dτ d > dτ d +2; 3) the multiplicity of dτ d +1 is at least 2;

Proof:
In the first item, the case of i ∈ I k \ {τ d + 1} follows directly from the symmetry of the Ferrers-Sylvester diagran of a threshold graph. If dτ d +1 > τ d , then the trace of the graph will be at least τ d + 1, a contradiction. If dτ d +1 < τ d , d * τ d = τ d and thus dτ d = τ d due to the symmetry of the diagram. On the other hand, the definition of a threshold graph requires that d * i = di + 1 for each i ∈ Iτ d , which leads to a contradiction. In the second item, note that elements of d are in non-increasing order. If dτ d = dτ d +2, then the first part of the lemma implies dτ d = dτ d +1 = dτ d +2 = τ d , which breaks the symmetry of the Ferrers-Sylvester diagram of a threshold graph. In the third item, if the multiplicity of dτ d +1 is 1, then the first part of the lemma implies dτ d ≥ τ d + 1 and dτ d +2 ≤ τ d − 1, which again breaks the symmetry of the Ferrers-Sylvester diagram of a threshold graph. Item 4) follows directly from the position property of 1 and 0 in (7) and the fact that each column sum of L (k) T is 0. The final item is a natural result from the Ferrers-Sylvester diagram of a threshold graph. Now we present a systematic approach to generate a set of k − 1 eigenvectors of L (k) T . This approach includes two steps only. The first step is to modify the upper-right triangular part of L (k) T . The second step is to make sure the column sum after the modification is 0. Specifically, 1) Let vij be the (i, j)th entry of V, and let V be L (k) T initially. If j > i, then vij is replaced with −1 − vij . As a result, vij becomes 0 if it is originally −1; or becomes −1 if it is originally 0. 2) Update the diagonal terms of V generated by the first step, such that each column sum is 0.
This approach is algorithmized in Algorithm 1. Note that in the algorithm vii is updated before vst, where t > s, t > i, is replaced such that two nested for loops are enough. Observe that for generating the matrix V from L (k) T , Algorithm 1 modifies: 1). k 2 entries, for each using only one addition operation; 2). k − 1 entries, for each using k − 2 addition operations for summation. Thus for a threshold graph with data size n, we can run the algorithm with complexity O(n). The following theory verifies that the ith column of the output V of Algorithm 1 is an eigenvector corresponding to the ith largest eigenvalue of the given L  vjj ← − k i=1,i =j vij 7: end for 8: Remove the zero column of V 9: Append 1, the column of 1's, to the last column of V 10: return V This result is based on the well-known fact that adding a dominating vertex to a (k − 1)-vertex simple and connected graph results in an eigenpair (k, v) where v = [ (k −1) −1 · · · −1 ] T is the first column of the Laplacian matrix of the resulting k-vertex graph and the first diagonal entry of the matrix corresponds to the degree of the added dominating vertex [28].
Theorem 3.2: Suppose a threshold graph with its Laplacian matrix L (k) T in (7) has the degree sequence d = (d1, · · · , d k ) and its conjugate d * = (d * 1 , · · · , d * k ). Then the jth column of V generated by Algorithm 1 is the eigenvector of L Proof: Consider the case that the eigenvalue is in the set of {d * 1 , d * 2 , · · · , d * τ d }. From the Ferrers-Sylvester diagram, it can be seen that if the vertex with the maximum degree is removed (along with its connecting edges), the remaining graph becomes a (d * 2 −1)-vertex threshold graph. Let and We can thus write L (k) . Continuing this argument we conclude that if v ℓ is the ℓth column of Q (d * ℓ −(ℓ−1)) ℓ for each ℓ ∈ Iτ d , then Now it remains to show the case that the eigenvalue is less than or equal to d * τ d +1 . Let v ℓ be the ℓth column of L Tṽ ℓ = d ℓṽℓ . Since for a threshold graph, d ℓ = d * ℓ−1 for each ℓ ∈ {τ d + 2, τ d + 3, · · · , k}. The proof is completed.
Remark 3.1: Let Rij be the identity matrix with its ith and jth columns switched. If di = dj, then L Consequently, if di = dj and v is an eigenvector of L (k) T , then switching the ith and jth entries of v also yields an eigenvector.

B. Controllability of Connected Threshold graphs
Theorem 3.2 provides all independent eigenvectors required by Theorem 2.1 to check the controllability of (L (k) T , B) for the general p-control matrix B. It can be readily seen that if p is less than the largest multiplicity among eigenvalues of L (k) T , then (L (k) T , B) is uncontrollable. In the following we show that this largest multiplicity is the minimum number of controllers required to render the graph controllable and this minimum can be achieved via a binary B.
Theorem 3.4: Suppose S (k) is a constructing string that generates a k-vertex connected threshold graph G T , and has the essential substrings S (k i ) 's satisfying S (k 1 ) ⊆ S (k 2 ) ⊆ · · · S (ks) ⊆ S (k) wheres is the number of successions in S (k) and is full row rank for each i ∈ Is, where C(S (k i ) ) andB(S (k i ) ) are local checking matrix and local control matrix, respectively, defined in Preliminaries.
Proof: For each i ∈ Is, Theorem 3.2 implies that an eigenvector of L T generated by S (k) must be [ 1 1 ] T or [ 0 0 ] T , which implies the row rank deficiency of C T (S (k 1 ) )B(S (k 1 ) ).
Corollary 3.5: Suppose in Theorem 3.4 L (k) T has the degree sequence d in (1) and B is a p-input control matrix. To render (L (k) T , B) controllable, 1) the minimum rank ofBi, which is composed of the (mi−1 + 1)th, · · · ,mith rows of B, is mi − 1, ∀i ∈ Ik, for general B. 2) the minimum p is maxi m * i , the largest multiplicity of eigenvalues of L (k) T if B is binary, and is k −k if B is terminal; Proof: If the rank ofBi is mi−2 or less for some i, then the rank ofC T (S (kσ i ) )Bi is at most mi−2. HereC(S (kσ i ) ) is the matrix obtained by dropping the last column and the zero submatrix in the first (mi −1)th columns of C(S (kσ i ) ), and σ· is the permutation function mapping {1, 2, · · · ,k} to {σ1, σ2, · · · , σk} for mi and mσ i defined in Preliminaries, i ∈ Ik. Consequently, C T (S (kσ i ) )B(S (kσ i ) ) has dependent rows. Now we show how to achieve the minimum number of controllers using a binary B and terminal B respectively. Let p = maxi m * i and partition the vertices according to their degrees. We obtain the partition Π := { π1, π2, · · · , πk }. Thus |πi| = mi. Let vij be the ith vertex in πj. The first item of the corollary suggests that each πi needs at least |πi| − 1 connections to controllers. If B is binary, connect vij to controller i for each i ∈ Im j −2. Ifdj = τ d then connect the (mj − 1)th vertex in πj to controller mj − 1, otherwise, connect the mjth vertex in πj to controller p. It can be readily seen that this binary B renders the graph controllable. If B is terminal, each controller is connected to only one vertex, thus we need mi − 1 controllers for each πi to implement the connection using a binary B. We conclude that k −k is the minimum number of controllers for a terminal B. T ,B(S (k) )) is controllable for each k ∈ {3, 5, 7}. Observe that S (k 1 ) is always an essential substring of S (k 2 ) if k1 < k2. An efficient check on the controllability of (L (11) T , B) should work on the smaller graph first and then on the larger one, and each check requires only one rank test. In the design problem where B is not available, the corollary above suggests to construct a 3-control binary matrix B = [ b1 b2 b3 ] where b1 = e3 + e5 + e8, b2 = e9 and b3 = e7. If B is terminal, then at least 5 controllers, e.g., B = [ e3 e5 e7 e8 e9 ], are needed to render (L (11) T , B) controllable.

C. Design of a Single-Input Controllable Graph
We now consider a special class of connected threshold graphs, namely, the class CA of connected antiregular graphs. Without loss of generality, the Laplacian matrix L is a square matrix of order k and can be written as . . . . . .
where δ k is 1 if k is even, and is 0 otherwise. Observe that the repeated degree for every k-vertex graph in CA is ⌊ k 2 ⌋. For convenience, letκ := k 2 and κ := k 2 . Clearly, we can express k asκ + κ. Combine the graphs G (κ) A and G and z (k) := e1 − eκ +⌈ κ 2 ⌉ where ei's are the standard basis vectors defined in Preliminaries. Occasionally we replace z (k) with z for simplicity as the context is clear. Using the notations defined above, we have, for example, The following interlacing theorem follows directly from Weyl's inequality and is helpful in further spectral analysis of L (k) A . Theorem 3.6: [32] Suppose A1 is a Hermitian matrix of order n and A2 = A1 + zz T where z is a nonzero column vector of size n. If λ (1) i and λ (2) i are the ith smallest eigenvalues of A1 and A2, respectively, then Our objective is to combine two anti-regular graphs while maintaining the single-input controllability. To achieve this, the Laplcian matrix corresponding to the combined graph should not have any repeated eigenvalue. In the following, we show that our proposed combination of two anti-regular graphs actually leads to distinct Laplacian eigenvalues.
where R (γ) α,β is the elementary row operation matrix, namely, the identity matrix except its (β, α)th entry being γ. As a result, where for integer m > 2, andD The eigenspace property of L

(k)
A , which is closely related to the controllability of G

(k)
A , is given in the following theorem.
for some c ∈ R. If c = 0, then v1 = 0, and thus the first row ofL (k) A (λ) implies that the κ 2 th entry of v2 is 0. In addition, the κ + κ 2 th row implies that the κ 2 + 1 th entry is 0 as well. Following these arguments we obtain that v2 = 0, and thus v = 0, a contradiction. We conclude that c = 0. The case of odd k but evenκ, or the case of even k can be proved in a similar fashion and is skipped.
The eigenpair analysis above reveals the Laplacian controllability relation between the antiregular graph G A ,b controllable. A sufficient condition for the controllability of the combined graph can thus be readily derived.
Corollary 3.9: Supposeb is a binary vector of sizeκ. b is a zeropadding version ofb in the sense that b T = b T 0 T with size k. Then the following statements are equivalent: A ,b is controllable; 2) the sum of the κ 2 th and κ 2 + 1 th entries ofb is 1; Proof: The equivalence of the first two items follows from Theorem 3.4. Observe that an apparent eigenpair (λ, v) of L

(k)
A is λ = κ 2 +(−1)κ and v = e ⌈κ 2 ⌉ −e (⌈κ 2 ⌉+1) . If the second item fails, then b is orthogonal to this v. Suppose the second item holds. If λ ∈ Λ in (21), clearly b is not orthogonal to the corresponding v; otherwise, the proof of Theorem 3.8 suggests the form of [ (1 − λ) 1 1 · · · 1 ] for the firstκ entries of v and implies the non-orthogonality of b to v.

IV. CONCLUSION
We have studied in this work the problem of Laplacian controllability of connected threshold graphs on k vertices. In the first part of the paper, we have derived a spanning set of k orthogonal Laplacian eigenvectors and proposed the necessary and sufficient condition for the graphs to be controllable. If a binary control matrix is used, we have shown that we can check the rank fullness of several specific control submatrices to determine the Laplacian controllability of the graph, or use the minimum number, namely, the maximum multiplicity of entries in the conjugate of the degree sequence defining the graph, of controllers to render the graph controllable. In the second part, we have proposed to connect two antiregular graphs, one on ⌈ k 2 ⌉ vertices and the other on ⌊ k 2 ⌋, to form a k-vertex graph that is single-input controllable. The proposed graph structure is new to the class of known single-input controllable graphs and has some compromised graph parameters, compared to other wellknown single-input controllable cases. For example, the diameter and the maximum vertex degree of the proposed graph are 4 and ⌈ k 2 ⌉ respectively (in a path graph they are k − 1 and 2 respectively, and in an antiregular graph they are 2 and k − 1 respectively). The proposed structure enriches the class of single-input controllable graphs and provides more choices for the system designers when these parameters are their concerns. For future research topics, generalizing from the unweighted graph to the signed graph or more general graph should be interesting [33]. Exploring more possibilities to connect two controllable graphs while maintaining the controllability will also be the topic of interest.  = V DV T where D = diag([ λ k λ k−1 · · · λ1 ]) and V = [ v k v k−1 · · · v1 ] such that

APPENDIX
and v T ℓ := Moreover, let x T Ax/x T x be the Rayleigh-Ritz quotient for a square matrix A and nonzero column vector x. Equivalently, the quotient can be defined as R(A, x) := x T Ax where x 2 = 1. Supposeλi is the ith smallest eigenvalue of L Thus for any (k − i + 1)-dimensional U we haveλi ≥ minx∈U R L (k) A , x , and for any i-dimensional space U we havẽ λi ≤ maxx∈U R L (k) A , x . If k orκ is even, the interlacing theorem has thatλ2i−1 = λi for each i ∈ Iκ. In case k andκ are both odd, we haveλ It remains to show that λ2i <λ2i < λ2i+1 (26) for any i ∈ Iκ. Consider the vector x = V y where y T = [ y k y k−1 · · · y2i o T ] and y 2 = 1. Thus If y2i+1 = y2i+2 = · · · = y k = 0, then R L (k)