Signed graphs with integral net Laplacian spectrum

Abstract

Given a signed graph $\dot{G}$, let $A_{\dot{G}}$ and $D_{\dot{G}}^{\pm }$ be its standard adjacency matrix and the diagonal matrix of net-degrees, respectively. The net Laplacian matrix of $\dot{G}$ is defined as $N_{\dot{G}}=D_{\dot{G}}^{\pm }-A_{\dot{G}}$. In this paper we investigate signed graphs whose net Laplacian spectrum consists entirely of integers. The focus is mainly on the two extreme cases, the one in which all eigenvalues of $N_{\dot{G}}$ are simple and the other in which $N_{\dot{G}}$ has 2 or 3 (distinct) eigenvalues. Both cases include structure theorems, degree constraints and particular constructions of new examples. Several applications in the framework of control theory are reported.

KEYWORDS:

• Net-degree
• net Laplacian matrix
• join
• signed cograph
• graph product
• regular signed graph
• controllable signed graph

1 Introduction

A signed graph $\dot{G}$ is a pair $(G,\sigma )$, where $G=(V,E)$ is an (unsigned) graph, called the underlying graph, and $\sigma :E\to \{-1,+1\}$ is the sign function. The edge set of a signed graph is composed of subsets of positive and negative edges. We denote the number of vertices (also known as the order) of a signed graph by n. In literature, one may find a slightly different notation with Γ or Σ for a signed graph. Our dot-notation appears in papers concerning spectra, where the absence of a dot refers to the underlying graph simultaneously interpreting a signed graph with all-positive signature.

Many familiar notions about graphs extend directly to the domain of signed graphs. For example, the degree d_u of a vertex u of $\dot{G}$ is its degree in G. Similarly, a signed graph is regular if its underlying graph is regular. On the other hand, there are some notions exclusive to signed graphs. The positive degree $d_u^{+}$ is the number of positive neighbors of u (i.e. those adjacent to u by a positive edge). In a similar way, we define the negative degree $d_u^{-}$. The net-degree of u is defined as $d_u^{\pm }=d_u^{+}-d_u^{-}$. A signed graph is said to be net-regular if the net-degree, considered as a function on the vertex set, is constant.

The adjacency matrix $A_{\dot{G}}$ of $\dot{G}$ is obtained from the standard adjacency matrix of G by replacing + 1 with –1 whenever the corresponding edge is negative. The Laplacian matrix is defined as $L_{\dot{G}}=D_{\dot{G}}-A_{\dot{G}}$, where $D_{\dot{G}}$ is the diagonal matrix of vertex degrees.

The net Laplacian matrix is defined as $N_{\dot{G}}=D_{\dot{G}}^{\pm }-A_{\dot{G}}$, where $D_{\dot{G}}^{\pm }$ is the diagonal matrix of net-degrees. The matrices $A_{\dot{G}}$ and $L_{\dot{G}}$ have received a great deal of attention in the theory of spectra of signed graphs. On the contrary, the net Laplacian appears very sporadically, say in [7, 13, 15–17]. The authors of [7] highlighted its significance in the study of controllability of undirected signed graphs. To the best of our knowledge, the first appearance of the term ‘net Laplacian’ is recorded in [16]. Evidently, in particular case of unsigned graphs the net Laplacian coincides with the Laplacian.

We denote the eigenvalues (with possible repetitions) of $N_{\dot{G}}$ by ${\nu }_1,{\nu }_2,\dots ,{\nu }_n$. The eigenvalues, the spectrum and the eigenvectors of $N_{\dot{G}}$ are simultaneously considered as the net Laplacian eigenvalues, the net Laplacian spectrum and the net Laplacian eigenvectors of $\dot{G}$, but to ease language, except in the formulations of the statements, we suppress the prefix ‘net Laplacian’ from the previous terminology. In addition, we write ‘$\dot{G}$ has k eigenvalues’ to mean that $\dot{G}$ has k distinct eigenvalues. It is not difficult to see that 0 is an eigenvalue of every signed graph with the all-1 eigenvector.

We say that the spectrum of $\dot{G}$ is integral if it consists entirely of integers. When this occurs, we also say that $\dot{G}$ is integral. Such signed graphs are subject of the research reported in this paper. In particular, we consider the case in which $\dot{G}$ has no repeated eigenvalues and its counterpart in which the number of eigenvalues of $\dot{G}$ is extremely small; precisely, equal to 2 or 3. In both cases we establish some theoretical results concerning the structure of signed graphs under consideration, and then provide particular constructions. An application of integral signed graphs without repeated eigenvalues in the framework of control theory is investigated.

The paper is organized as follows. Section 2 contains some additional terminology and notation, along with some known results. In particular, one can find definition of the class of integral signed graphs called ∇-cographs and the particular subclass of ∇-threshold graphs. In Section 3 we investigate the spectrum of ∇-cographs and give constructions of those that avoid repeated eigenvalues. All connected signed graphs with 2 eigenvalues and at most 8 vertices are reported in Section 4; all of them are integral. Structural examinations of certain signed graphs with 2 or 3 eigenvalues are given in Section 5. Finally, some applications in control theory are separated in Section 6.

2 Preparatory

We use j, $\mathbf{0}$, J and I to denote the all-1 vector, the all-0 vector, the all-1 matrix and the identity matrix, respectively. The length or the size may be given in the subscript. We write $〈\mathbf{x},\mathbf{y}〉$ to denote the Euclidean inner product of the vectors x and y. For the signed graphs ${\dot{G}}_1$ and ${\dot{G}}_2,{\dot{G}}_1\cup {\dot{G}}_2$ denotes their disjoint union, and $k{\dot{G}}_1$ the disjoint union of k copies of ${\dot{G}}_1$. The negation $-{\dot{G}}_1$ of ${\dot{G}}_1$ is obtained by reversing the sign of every edge of ${\dot{G}}_1$. Evidently, $-N_{{\dot{G}}_1}$ acts as the net Laplacian matrix of $-{\dot{G}}_1$, and the spectrum of $-{\dot{G}}_1$ is obtained by negating every eigenvalue of ${\dot{G}}_1$. Finally, if ${\dot{G}}_1$ and ${\dot{G}}_2$ are isomorphic, we write ${\dot{G}}_1\cong {\dot{G}}_2$. For the undefined notions, we refer the reader to [18].

The join $G_1\nabla G_2$ of (unsigned) graphs G₁, G₂ is obtained by inserting an edge between every vertex of ${\dot{G}}_1$ and every vertex of ${\dot{G}}_2$. In the framework of signed graphs we have similar definitions. For the signed graphs ${\dot{G}}_1,{\dot{G}}_2$, the positive join (resp. negative join) ${\dot{G}}_1{\nabla }^{+}{\dot{G}}_2$ (${\dot{G}}_1{\nabla }^{-}{\dot{G}}_2$) is obtained by inserting a positive (negative) edge between every vertex of ${\dot{G}}_1$ and every vertex of ${\dot{G}}_2$.

We recall from [10] that an unsigned cograph is iteratively defined in the following way: K₁ is a cograph; if G₁, G₂ are cographs, then $G_1\nabla G_2$ is a cograph. Alternatively, a cograph is a P₄-free graph. Similarly, a threshold graph $G\cong G(\mathbf{b})$ is defined on the basis of its binary generating sequence $\mathbf{b}=(b_1,b_2,\dots ,b_n)$ in the following way: $G_1\cong G_1(b_1)\cong K_1$; if $G_{i-1}(b_1,b_2,\dots ,b_{i-1})$ is already constructed, then $G_i(b_1,b_2,\dots ,b_i)$ is formed by adding a vertex non-adjacent to the vertices of $G_{i-1}$ if b_i = 0 or by adding a vertex adjacent to all the vertices of $G_{i-1}$ if b_i = 1. Alternatively, a threshold graph is a $\{2K_2,P_4,C_4\}$-free graph, and so every threshold graph is a cograph. For more details see [9].

In the framework of signed graphs we may define a signed cograph (resp. signed threshold graph) as a signed graph whose underlying graph is a cograph (threshold graph). However, in this study we are more interested in particular classes so called ∇-cographs. A ∇-cograph is a signed graph defined in the following way: K₁ is a ∇-cograph; if ${\dot{G}}_1,{\dot{G}}_2$ are ∇-cographs, then ${\dot{G}}_1\cup {\dot{G}}_2,{\dot{G}}_1{\nabla }^{+}{\dot{G}}_2$ and $G_1{\nabla }^{-}{G}_2$ are ∇-cographs. Similarly, a ∇-threshold graph is defined on the basis of its $(0,1,-1)$-generating sequence $\mathbf{b}=(b_1,b_2,\dots ,b_n)$ as follows: ${\dot{G}}_1\cong {\dot{G}}_1(b_1)\cong K_1$ is a ∇-threshold graph and if ${\dot{G}}_{i-1}(b_1,b_2,\dots ,b_{i-1})$ is already constructed, then ${\dot{G}}_i(b_1,b_2,\dots ,b_i)$ is formed by adding a vertex non-adjacent to the vertices of ${\dot{G}}_{i-1}$ if b_i = 0, or adding a vertex joined by a positive edge to all the vertices of ${\dot{G}}_{i-1}$ if b_i = 1, or adding a vertex joined by a negative edge to all the vertices of ${\dot{G}}_{i-1}$ if $b_i=-1$. Observe that a ∇-threshold graph does not depend on the choice for b₁ and it is uniquely determined by the remainder of b.

Remark 1.

Evidently, every ∇-cograph is a signed cograph and every ∇-threshold graph is a signed threshold graph (and consequently, it is a signed cograph). The prefix ∇ suggests that the sign of every edge is determined by the positive or the negative join operation.

In this paper we will frequently use the following result of [15]. It is a ‘signed’ generalization of the known result obtained by Merris [10] (see also [11]).

Theorem 2.1.

[15, Theorem 3] Let ${\dot{G}}_1$ and ${\dot{G}}_2$ be signed graphs with net Laplacian eigenvalues ${\nu }_1({\dot{G}}_1),{\nu }_2({\dot{G}}_1),\dots ,{\nu }_{n_1}({\dot{G}}_1)=0$ and ${\nu }_1({\dot{G}}_2),{\nu }_2({\dot{G}}_2),\dots ,{\nu }_{n_2}({\dot{G}}_2)=0$, respectively, and let $\mathcal{l}$ be a fixed element of $\{+,-\}$. The net Laplacian eigenvalues of ${\dot{G}}_1{\nabla }^{\mathcal{l}}{\dot{G}}_2$ are ${\nu }_1({\dot{G}}_1)\mathcal{l}{n}_2,{\nu }_2({\dot{G}}_1)\mathcal{l}{n}_2,\dots ,{\nu }_{n_1-1}({\dot{G}}_1)\mathcal{l}{n}_2,{\nu }_1({\dot{G}}_2)\mathcal{l}{n}_1,{\nu }_2({\dot{G}}_2)\mathcal{l}{n}_1,\dots ,{\nu }_{n_2-1}({\dot{G}}_2)\mathcal{l}{n}_1,\mathcal{l}(n_1+n_2)$ and 0.

If x is a net Laplacian eigenvector of ${\dot{G}}_1$ orthogonal to j and associated with a net Laplacian eigenvalue ν, then its extension defined to be zero on each vertex of ${\dot{G}}_2$ is a net Laplacian eigenvector of ${\dot{G}}_1{\nabla }^{\mathcal{l}}{\dot{G}}_2$ associated with $\nu \mathcal{l}{n}_2$, and similarly for the net Laplacian eigenvectors of ${\dot{G}}_1{\nabla }^{\mathcal{l}}{\dot{G}}_2$ that arise from those of ${\dot{G}}_2$. The net Laplacian eigenvalue $\mathcal{l}(n_1+n_2)$ is associated with the net Laplacian eigenvector with weight $-n_2$ on each vertex of ${\dot{G}}_1$ and n₁ on each vertex of ${\dot{G}}_2$.

As observed in [14], an immediate consequence of the previous theorem is the fact that the largest eigenvalue of a signed graph $\dot{G}$ with n vertices does not exceed n, and it attains n if and only if $\dot{G}$ is a positive join of two signed graphs.

We conclude this section with a simple corollary treating ∇-thresholds graphs.

Corollary 2.2.

Let $\dot{G}$ be a ∇-threshold graph generated by the sequence $$(b_1,b_2,\dots ,b_k,\underset{t}{\underbrace{0,0,\dots ,0}}),$$with $b_k\ne 0$. For t = 0, $\dot{G}$ is a positive (for b_k = 1) or a negative (for $b_k=-1$) join and its net Laplacian spectrum is formed as in Theorem 2.1. For t > 0, $\dot{G}$ is a disjoint union of a connected ∇-threshold graph $\dot{G}\prime$ generated by $(b_1,b_2,\dots ,b_k)$ and the set of t isolated vertices. The net Laplacian spectrum of $\dot{G}$ consists of the net Laplacian eigenvalues of $\dot{G}\prime$ obtained as in Theorem 2.1 and t zeroes.

Proof.

For t = 0, the result follows immediately from definition of a ∇-threshold graph and Theorem 2.1.

For t > 0, we have $\dot{G}\cong \dot{G}\prime \cup t{K}_1$, and thus the spectrum of $\dot{G}$ consists of the eigenvalues of $\dot{G}\prime$ and the eigenvalues of tK₁ (zero with multiplicity t). In addition, $b_k\ne 0$ implies that $\dot{G}\prime$ is connected. Moreover, it is a positive or a negative join (depending on the sign of b_k ), and so its eigenvalues are obtained as in Theorem 2.1. □

3 Spectrum of ∇-cographs

As we said in the first section, the spectrum of the net Laplacian matrix is studied in just few references. Some particular results (including small structural perturbations, relations with the spectrum of the standard Laplacian matrix and certain operations on signed graphs) can be found in [15, 17]. In this section we establish some spectral properties of ∇-cographs and the subclass of ∇-threshold graphs. We devote a particular attention to those that have no repeated eigenvalues.

First, every ∇-cograph (as well as every ∇-threshold graph) is integral. To see this, one may suppose that $\dot{G}$ is the smallest connected non-integral ∇-cograph and then use Theorem 2.1 to show that it contains a connected ∇-cograph with smaller order which must be non-integral. In what follows we prove that the class of all ∇-threshold graphs does not contain two that share the same spectrum.

Theorem 3.1.

No two ∇-threshold graphs have the same net Laplacian spectrum.

Proof.

Assume for the sake of contradiction that ${\dot{G}}_1,{\dot{G}}_2$ make a smallest pair (relative to the number of vertices) of ∇-threshold graphs with the same spectrum. Let n be their common order.

Let first ${\dot{G}}_1$ be disconnected. Hence, we have ${\dot{G}}_1\cong \dot{G}{\prime }_1\cup c_1{K}_1$, where $\dot{G}{\prime }_1$ is a connected ∇-threshold graph with $k\ge 2$ vertices. Without loss of generality, we may suppose that $\dot{G}{\prime }_1$ is a positive join, and in this case k is the largest eigenvalue of $\dot{G}{\prime }_1$, by Corollary 2.2. In addition, the least eigenvalue of $\dot{G}{\prime }_1$ is greater than – k. Consequently, we have the same situation for ${\dot{G}}_2$: its largest eigenvalue is k and its spectrum is bounded from below by $-k+1$. Since k < n, we get that ${\dot{G}}_2$ is disconnected, as well; otherwise, one of $n,-n$ would appear in its spectrum. Therefore, we have ${\dot{G}}_2\cong \dot{G}{\prime }_2\cup c_2{K}_1$, where $\dot{G}{\prime }_2$ is a connected ∇-threshold graph. Moreover, k is an eigenvalue of $\dot{G}{\prime }_2$ and its least eigenvalue is greater than – k (as ${\dot{G}}_1$ and ${\dot{G}}_2$ share the same spectrum). In other words, $\dot{G}{\prime }_2$ is a positive join and has k vertices, which implies c₁ = c₂, which further implies that $\dot{G}{\prime }_1$ and $\dot{G}{\prime }_2$ share the same spectrum, but this contradicts the assumption that ${\dot{G}}_1,{\dot{G}}_2$ make a smallest such a pair.

Let now ${\dot{G}}_1$ be connected and, without loss of generality, let it be a positive join. By Corollary 2.2, the order of ${\dot{G}}_1$ appears as a common eigenvalue of ${\dot{G}}_1$ and ${\dot{G}}_2$, which implies that ${\dot{G}}_2$ is also a positive join. In other words, we have ${\dot{G}}_1\cong K_1{\nabla }^{+}\dot{G}{\prime }_1$ and ${\dot{G}}_2\cong K_1{\nabla }^{+}\dot{G}{\prime }_2$ for some ∇-threshold graphs $\dot{G}{\prime }_1,\dot{G}{\prime }_2$. If ${\nu }_1=n,{\nu }_2,\dots ,{\nu }_n=0$ are the common eigenvalues of ${\dot{G}}_1$ and ${\dot{G}}_2$, then the eigenvalues of $$ and $\dot{G}{\prime }_2$ are ${\nu }_2-1,{\nu }_3-1,\dots ,{\nu }_{n-1}-1$ and 0 (by Corollary 2.2, as well). In other words, $\dot{G}{\prime }_1$ and $\dot{G}{\prime }_2$ share the same spectrum, which as before contradicts the initial assumption on minimality of ${\dot{G}}_1$ and ${\dot{G}}_2$. This completes the proof. □

On the basis of Theorem 2.1 (and Corollary 2.2) we can give a simple algorithm that computes the eigenvalues and the eigenvectors of a ∇-threshold graph. Its correctness is inspected directly, by employing the previous results.

RETURN $({\nu }_1,{\nu }_2,\dots {\nu }_n),({\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_n)$ $\backslash \backslash$ Eigenvalues and eigenvectors.

The algorithm contains a linear loop which in each iteration includes another linear loop, so the time complexity is quadratic. We now extend a rooted tree representation of cographs of [4] to ∇-cographs. For a ∇-cograph $\dot{G}$, the root and every interior vertex of the corresponding tree $T_{\dot{G}}$, called a ∇-cotree, is either of 0-type (corresponding to disjoint union), or (+)-type (corresponding to positive join), or (–)-type (corresponding to negative join). The terminal vertices (leaves) are typeless and each of them represents itself in $\dot{G}$. Unless $\dot{G}$ consists of an isolated vertex, the root and every interior vertex have at least two direct successors. Moreover, every non-terminal direct successor of any vertex v has a type that differs from the type of v. It can be easily seen that every ∇-cograph has such a rooted representation and that every rooted tree formed as above represents the unique ∇-cograph. An example is given in Figure 1; clearly, the notation for every non-terminal vertex corresponds to its type.

Fig. 1. A ∇-cograph $\dot{G}$ and its representation $T_{\dot{G}}$. In $\dot{G}$, negative edges are dashed.

One can observe that interchanging $(+)$-type and $(-)$-type vertices results in the negation of the corresponding ∇-cograph.

We now prove the following result.

Lemma 3.2.

Every vertex-deleted subgraph of a ∇-cograph (resp. ∇-threshold graph) is a ∇-cograph (∇-threshold graph).

Proof.

Let v be a vertex of a ∇-cograph $\dot{G}$. Then v is a terminal vertex in the ∇-cotree $T_{\dot{G}}$. If v shares a common direct predecessor with at least 2 terminal vertices, then the ∇-cotree $T_{\dot{G}-v}$ representing $\dot{G}-v$ is obtained by removing v from $T_{\dot{G}}$. For otherwise, $T_{\dot{G}-v}$ is obtained by removing v and its direct predecessor, say u, and inserting and edge between the direct predecessor and the direct successor of u. The existence of $T_{\dot{G}-v}$ confirms that $\dot{G}-v$ is a ∇-cograph.

Vertex-deleted subgraphs of ∇-threshold graphs are considered by employing the fact that every ∇-threshold graph is a ∇-cograph.

We now consider ∇-cographs without repeated eigenvalues. We start with the following result.

Theorem 3.3.

Let $\dot{G}$ be a ∇-cograph without repeated net Laplacian eigenvalues. The following statements hold true.

1. Let ${\dot{G}}_v$ be a subgraph determined by a non-terminal vertex v (and its successors) of $T_{\dot{G}}$. The non-zero net Laplacian eigenvalues of ${\dot{G}}_v$ are simple. The multiplicity of zero is at most 2.

2. $T_{\dot{G}}$ is a binary tree.

3. $T_{\dot{G}}$ has no subtree illustrated in Figure 2.

Fig. 2. A forbidden subtree for Theorem 3.3(iii).

Proof.

(i): By virtue of Theorem 2.1, an application of $\cup ,{\nabla }^{+}$ or ${\nabla }^{-}$ operation to two signed graphs such that one of them has either a repeated nonzero eigenvalue or the eigenvalue 0 with multiplicity at least 3 results in a signed graph with either a repeated eigenvalue or 0 with multiplicity at least 3. In particular, if ${\dot{G}}_v$ does not satisfy the assumptions of (i), then $\dot{G}$ has a repeated eigenvalue.

(ii): Assume for contradiction that a vertex v of $T_{\dot{G}}$ has at least 3 direct successors. If v is of 0-type, then the subgraph ${\dot{G}}_v$ (determined by v) has the eigenvalue 0 with multiplicity at least 3. If v is of some of the remaining types and ${\dot{G}}_v$ has k vertices, then either k or – k is an eigenvalue with multiplicity at least 2 in ${\dot{G}}_v$. In both cases the desired conclusion follows from the previous item.

(iii): If v is of 0-type (briefly, 0) then $u\in \{+,-\}$. If u is + (resp. –), 2 (–2) has multiplicity 2 in ${\dot{G}}_u$, and the result follows from (i). If v is +, then in ${\dot{G}}_u$ the eigenvalue 2 has multiplicity 2 for u being 0, and 0 has multiplicity 3 for u being –, and similarly for the remaining possibility for v. Again, the result follows from (i). □

We proceed with two particular constructions. For the first one, let a $(1,-1,2,-2)$-sequence determine a ∇-cograph in the following way: 1 and –1 have the same roles as in the similar sequences related to ∇-threshold graphs, while 2 (resp. –2) represents adding two non-adjacent vertices joined by positive (negative) edges to all the vertices of the already formed ∇-cograph. In particular, if a generating sequence starts with either 2 or –2, this means that in the first step we take 2 isolated vertices.

Theorem 3.4.

A $(1,-1,2,-2)$-sequence generates a ∇-cograph without repeated net Laplacian eigenvalues if and only if this sequence is

1. $$,

2. $(a,1,-1,1,-1,\dots ,-1)$,

3. $(b,1,-1,1,-1,\dots ,1)$,

or the negation of some of these sequences, where $a\in \{1,-1\},b\in \{2,-2\}$.

Proof.

Using Theorem 2.1, we get that the sequences of (i)–(iii) generate the ∇-cographs with eigenvalues(1) $$n,n-2,\dots ,2,0,-2,\dots ,-n+4,-n+2,$$(1) (2) $$n-2,n-4,\dots ,1,0,-3,\dots ,-n+2,-n,$$(2)

and(3) $$n,n-2,\dots ,1,0,-3,\dots ,-n+4,-n+2,$$(3) respectively. Their negations generate ∇-cographs with negated eigenvalues, which proves one implication.

Assume now that $\dot{G}$ which has no repeated eigenvalues is generated by a sequence $\mathbf{b}=(b_1,b_2,\dots ,b_n)$ that differs from the previous ones. In this case, every induced subgraph generated by $(b_1,b_2,\dots ,b_i)$ has no repeated nonzero eigenvalues.

For $i\ge 2$ the consecutive entries b_i and $b_{i+1}$ must differ in sign, as otherwise $(b_1,b_2,\dots ,b_{i+1})$ would generate a ∇-cograph with a repeated eigenvalue (equal to i + 1 or $-i-1$). Therefore, if b does not contain ±2, then b coincides with (i) or (ii), up to negation.

Assume further that b contains 2 or –2, and let $b_{i+1},i\ge 1$, be the first occurrence of ±2 in b. According to the previous computation, the sequence $(b_1,b_2,\dots ,b_i)$ generates a ∇-cograph, say ${\dot{G}}_i$, whose eigenvalues are up to negation given by replacing n with i in one of (1)–(3). By extending the generating sequence with $b_{i+1}=\pm 2$, we get ${\dot{G}}_{i+1}$ with a repeated non-zero eigenvalue. Indeed, if the spectrum of ${\dot{G}}_i$ is determined by (1), then $b_{i+1}$ must differ in sign from b_i , and thus $b_{i+1}=-2$ which gives – i of multiplicity 2, and similarly if the spectrum of ${\dot{G}}_i$ is determined by the negation of (1). The remaining two possibilities ((2) and (3)) are considered in the same way.

It remains to consider the case in which $b_1=\pm 2$. Then $b_2\ne \pm 2$, as otherwise 2 or –2 is a repeated eigenvalue of ${\dot{G}}_2$. Thus, b starts with $(b,1,-1,1,-1,\dots )$ or its negation. If $b_i\ne \pm 2$ for $i\ge 2$ then $b_n=b_2$, as otherwise 0 has the multiplicity 2 in $\dot{G}$. But then b coincides with (iii). If $b_{i+1}$ is the first occurrence of ±2, then b_i differ in sign, and then either i or – i has multiplicity 2. This eliminates the last possibility for b and completes the proof. □

Observe that ∇-cographs generated by $(1,-1,2,-2)$-sequences are obtained by removing a matching from a complete signed graph. The previous result gives those without repeated eigenvalues.

In what follows we use $S_{i,n}$ to denote the set of all integers from 0 to n excluding $i\notin \{0,n\}$. By $-S_{i,n}$ we denote the negation of the previous set. We say that a signed graph without repeated eigenvalues realizes $S_{i,n}$ if its spectrum coincides with $S_{i,n}$.

The following result gives some particular constructions of ∇-cographs without repeated and without negative eigenvalues.

Theorem 3.5.

For $k,l\ge 3$, let ${\dot{H}}_1$ be a ∇-cograph that realizes $-S_{i,k}$ and ${\dot{H}}_2$ a ∇-cograph that realizes $S_{j,l}$. Then the net Laplacian eigenvalues of $\dot{G}\cong \stackrel{.}{H_1}{\nabla }^{+}(K_1\cup {\dot{H}}_2)$ are non-negative and simple if and only if i = 1 (and then $\dot{G}$ realizes $S_{k+j,k+l+1}$) or i = 2, j = 1 (and then $\dot{G}$ realizes $S_{1,k+l+1}$).

Proof.

The eigenvalues of $\dot{G}$ are $0,k+l+1,l,l-1,\dots ,l-k+1,k,k+1,\dots ,k+l$ with $l-i+1$ and k + j removed. For $l\le k-1,\dot{G}$ contains a repeated zero eigenvalue or a negative eigenvalue (both arise from $l-k+1$). For $l\ge k+2$, the spectrum of $\dot{G}$ avoids 1 and 2, which means that it must have at least one repeated eigenvalue.

For l = k, there must be i = 1; otherwise, l is a repeated eigenvalue. Then $\dot{G}$ obviously realizes $S_{k+j,k+l+1}$.

For $l=k+1$, there must be i = 2 (otherwise, l – 1 is a repeated eigenvalue) and also j = 1 (otherwise, l is a repeated eigenvalue). Then $\dot{G}$ realizes $S_{1,k+l+1}$. □

To get some examples we need to define the following operations. Let $f_1(H)$ denote the operation $(2K_1)\nabla (K_1\cup H)$ applied to an unsigned graph H. Similarly, we denote $f_2(H)=K_1\nabla (K_2\cup H)$ and $f_3(H)=K_1\nabla (K_1\cup H)$. We also use ${\mathcal{P}}_1$ (resp. ${\mathcal{P}}_2$) to denote the composition $f_1°f_2°f_3$ (resp. $f_3°f_1°f_2$). We know from [16] that a ∇-cograph without negative edges realizes $S_{1,k}$ if and only if it is realized by the iterative procedure having one of the following forms

• $K_2\to f_1\to {\mathcal{P}}_1\to {\mathcal{P}}_1\to \cdots \to {\mathcal{P}}_1\text{or}{K}_2\to {\mathcal{P}}_1\to {\mathcal{P}}_1\to \cdots \to {\mathcal{P}}_1$ ,

• $P_3\to f_1\to {\mathcal{P}}_1\to {\mathcal{P}}_1\to \cdots \to {\mathcal{P}}_1\text{or}{P}_3\to f_2\to f_1\to {\mathcal{P}}_1\to {\mathcal{P}}_1\to \cdots \to {\mathcal{P}}_1$

and it realizes $S_{2,k}$ if and only if it is realized by the iterative procedure having one of the following forms

• $K_2\to f_3\to {\mathcal{P}}_2\to {\mathcal{P}}_2\to \cdots \to {\mathcal{P}}_2\text{or}{K}_2\to f_1\to f_3\to {\mathcal{P}}_2\to {\mathcal{P}}_2\to \cdots \to {\mathcal{P}}_2$,

• $P_3\to {\mathcal{P}}_2\to {\mathcal{P}}_2\to \cdots \to {\mathcal{P}}_2\text{or}{P}_3\to f_1\to f_3\to {\mathcal{P}}_2\to {\mathcal{P}}_2\to \cdots \to {\mathcal{P}}_2$

These constructions are sufficient for us to establish examples for Theorem 3.5. Namely, we can take the negation of a cograph that realizes $S_{1,k}$ and any cograph that realizes $S_{j,l}$ (here we can also take $j\in \{1,2\}$, while for the other possibilities we refer to [16]) to get a cograph that realizes $S_{k+j,k+l+j}$, and similarly for that realizing $S_{1,k+l+1}$.

Moreover, Theorem 3.5 enables us to give another example. We proved in Theorem 3.1 that any pair of ∇-threshold graphs differ in spectrum. The reader may recall the result in the particular case of unsigned graphs stating that every threshold graph is determined by its Laplacian spectrum (in the sense that there is no graph with the same Laplacian spectrum) [10]. Naturally, we can ask whether the same holds for ∇-threshold graphs and the net Laplacian spectrum, and the answer is negative. Namely, we know from [6, 16] that every ∇-threshold graph that realizes $S_{i,n}$ is generated by either(4) $$(1,1,\underset{2(i-1)}{\underbrace{0,1,0,1,\dots ,0,1}}) \text{or} (1,\underset{2(i-1)}{\underbrace{0,1,0,1,\dots ,0,1}}).$$(4)

Now, using Theorem 3.5 we can construct a ∇-cograph with the same spectrum. An example is obtained by taking $-{\dot{H}}_1\cong {\dot{H}}_2\cong (2K_1){\nabla }^{+}(K_1\cup K_2)$ and the ∇-threshold graph generated by the latter sequence for i = 6. The common spectrum is $S_{6,11}$.

We further prove that every ∇-threshold graph whose eigenvalues are simple and non-negative is generated by one of the aforementioned sequences.

Theorem 3.6.

If a ∇-threshold graph $\dot{G}$ generated by a $(0,1,-1)$-sequence $\mathbf{b}=(b_1,b_2,\dots ,b_n)$ has no repeated net Laplacian eigenvalue and has no negative net Laplacian eigenvalue, then b is one of the sequences of (4).

Proof.

We first prove that $b_i\ne -1$, for $i\ge 2$. Assume that this is not true and let b_i , $i\ge 2$, be the last occurrence of –1 in the generating sequence. In this case, by Theorem 2.1, there are at least i ones after b_i (otherwise, there is a negative eigenvalue in $\dot{G}$). In addition, the entries of $(b_{i+1},b_{i+2},\dots ,b_n)$ alternately take the values of {0, 1}.

Let b_j be the ith occurrence of 1 after b_i . The ∇-threshold graph ${\dot{G}}_j$ generated by $(b_1,b_2,\dots ,b_j)$ has the eigenvalue 0 of multiplicity 2, as ${\dot{G}}_{j-1}$ has the eigenvalue –1. Therefore, since $b_{j+1}=0$, we deduce that ${\dot{G}}_{j+1}$ has the eigenvalue 0 of multiplicity 3, and then $\dot{G}$ has a repeated eigenvalue, which is a contradiction.

Now, b₁ has an arbitrary value that does not affect the corresponding signed graph, say $b_1=1$ as in (4). It is a matter of routine to verify that $b_i=b_{i+1}$ implies the existence of a repeated eigenvalue in $\dot{G}$, unless i = 1, which leads to the desired result. □

4 Computer search on connected signed graphs with 2 eigenvalues

Here is the data for computer search on connected signed graphs with at most 8 vertices and 2 eigenvalues of the net Laplacian matrix. One of these eigenvalues is 0, while the other is an integer whose absolute value does not exceed the number of vertices.

For every order n there is the complete unsigned graph with spectrum $\{n^{n-1},0\}$ (the exponent stands for the multiplicity). For even order, there is the ∇-threshold graph $K_{n/2}{\nabla }^{+}(-K_{n/2})$ with spectrum $\{n^{n/2},0^{n/2}\}$. The net Laplacian matrices and spectra of the remaining connected signed graphs with non-negative spectrum are given below. The negation of every signed graphs with 2 eigenvalues also has 2 eigenvalues.$$\begin{array}{c}\begin{array}{c}\begin{array}{cccc}1& -1& -1& 1\\ -1& 1& 1& -1\\ -1& 1& 1& -1\\ 1& -1& -1& 1\end{array}\\ \{4,0^3\}\end{array}\\ \begin{array}{c}\begin{array}{cccccc}3& 0& -1& 0& -1& -1\\ 0& 1& 0& -1& -1& 1\\ -1& 0& 3& 0& -1& -1\\ 0& -1& 0& 1& 1& -1\\ -1& -1& -1& 1& 2& 0\\ -1& 1& -1& -1& 0& 2\end{array}\\ \{4^3,0^3\}\end{array} \begin{array}{c}\begin{array}{cccccc}1& 0& -1& 0& -1& 1\\ 0& 1& 0& 1& -1& -1\\ -1& 0& 1& 0& 1& -1\\ 0& 1& 0& 1& -1& -1\\ -1& -1& 1& -1& 2& 0\\ 1& -1& -1& -1& 0& 2\end{array}\\ \{4^2,0^4\}\end{array} \begin{array}{c}\begin{array}{cccccc}1& -1& -1& 1& -1& 1\\ -1& 1& 1& -1& 1& -1\\ -1& 1& 1& -1& 1& -1\\ 1& -1& -1& 1& -1& 1\\ -1& 1& 1& -1& 1& -1\\ 1& -1& -1& 1& -1& 1\end{array}\\ \{6,0^5\}\end{array}\\ \begin{array}{c}\begin{array}{cccccccc}1& 0& 0& -1& 0& 0& -1& 1\\ 0& 2& 0& 0& -1& 1& -1& -1\\ 0& 0& 2& 0& 1& -1& -1& -1\\ -1& 0& 0& 1& 0& 0& 1& -1\\ 0& -1& 1& 0& 1& -1& 0& 0\\ 0& 1& -1& 0& -1& 1& 0& 0\\ -1& -1& -1& 1& 0& 0& 2& 0\\ 1& -1& -1& -1& 0& 0& 0& 2\end{array}\\ \{4^3,0^5\}\end{array} \begin{array}{c}\begin{array}{cccccccc}3& 0& 0& -1& 0& 0& -1& -1\\ 0& 2& 0& 0& -1& -1& -1& 1\\ 0& 0& 2& 0& -1& -1& 1& -1\\ -1& 0& 0& 3& 0& 0& -1& -1\\ 0& -1& -1& 0& 1& 1& 0& 0\\ 0& -1& -1& 0& 1& 1& 0& 0\\ -1& -1& 1& -1& 0& 0& 2& 0\\ -1& 1& -1& -1& 0& 0& 0& 2\end{array}\\ \{4^4,0^4\}\end{array}\\ \begin{array}{c}\begin{array}{cccccccc}3& 0& 0& -1& 0& 0& -1& -1\\ 0& 2& 0& 0& -1& -1& -1& 1\\ 0& 0& 2& 0& -1& -1& 1& -1\\ -1& 0& 0& 3& 0& 0& -1& -1\\ 0& -1& -1& 0& 3& -1& 0& 0\\ 0& -1& -1& 0& -1& 3& 0& 0\\ -1& -1& 1& -1& 0& 0& 2& 0\\ -1& 1& -1& -1& 0& 0& 0& 2\end{array}\\ \{4^5,0^3\}\end{array} \begin{array}{c}\begin{array}{cccccccc}1& -1& -1& 1& -1& 1& 1& -1\\ -1& 1& 1& -1& 1& -1& -1& 1\\ -1& 1& 1& -1& 1& -1& -1& 1\\ 1& -1& -1& 1& -1& 1& 1& -1\\ -1& 1& 1& -1& 1& -1& -1& 1\\ 1& -1& -1& 1& -1& 1& 1& -1\\ 1& -1& -1& 1& -1& 1& 1& -1\\ -1& 1& 1& -1& 1& -1& -1& 1\end{array}\\ \{8,0^7\}\end{array}\end{array}$$

5 Particular cases of 2 or 3 eigenvalues

Inspired by the previous computational results, in this section we consider some classes of signed graphs with 2 or 3 eigenvalues. In particular, we are interested in (a) regular signed graphs with 2 eigenvalues, (b) arbitrary signed graphs with 2 eigenvalues such that one of them is simple and (c) regular signed graphs with 3 eigenvalues such that 0 is a simple one.

If $\dot{G}$ is net-regular with common net-degree ϱ, then we have $D_{\dot{G}}^{\pm }=\varrho \mathrm{I}$, which means that ν is an eigenvalue of $N_{\dot{G}}=D_{\dot{G}}^{\pm }-A_{\dot{G}}$ if and only if $\varrho -\nu$ is an eigenvalue of the adjacency matrix $A_{\dot{G}}$. More interesting case arises when we drop the net-regularity and keep the regularity condition. Hence, suppose that $\dot{G}$ is a regular signed graph with vertex degree r and 2 eigenvalues: 0 and ν. Taking into account the minimal polynomial, we get $N_{\dot{G}}(N_{\dot{G}}-\nu I)=O$, so $N_{\dot{G}}^2-\nu N_{\dot{G}}=O$. Consider now the diagonal entries of the left hand side of the last identity. We have $N_{\dot{G}}^2={(D_{\dot{G}}^{\pm })}^2-D_{\dot{G}}^{\pm }{A}_{\dot{G}}-A_{\dot{G}}{D}_{\dot{G}}^{\pm }+A_{\dot{G}}^2$, and the diagonal entries of $D_{\dot{G}}^{\pm }{A}_{\dot{G}}$ and $A_{\dot{G}}{D}_{\dot{G}}^{\pm }$ are 0, while the diagonal entries of $A_{\dot{G}}^2$ are all equal to r. Thus, for every vertex i of $\dot{G}$ its net-degree $d_i^{\pm }$ satisfies the quadratic equation $x^2-\nu x+r=0$, which leads to the following result.

Theorem 5.1.

Let $\dot{G}$ be a regular signed graph, with degree r. If $\dot{G}$ has 2 net Laplacian eigenvalues, then net-degrees of the vertices of $\dot{G}$ can take only 2 values which are solutions of the quadratic equation $x^2-\nu x+r=0$, where ν is the non-zero net Laplacian eigenvalue of $\dot{G}$.

It is well-known that, for unsigned graphs, the multiplicity of 0 in the Laplacian spectrum is equal to the number of connected components [10, 11]. Here we have a bit different situation in which the multiplicity of 0 in the net Laplacian spectrum of $\dot{G}$ is not less than the number of components [14]. In other words, every component has 0 as an eigenvalue of multiplicity at least 1. Examples of connected signed graphs for which 0 is not a simple eigenvalue can be found in the previous section and also in [2]. This inspires us to consider signed graphs with 2 eigenvalues such that 0 has either minimum or maximum multiplicity.

Theorem 5.2.

Let $\dot{G}$ be a signed graph with 2 net Laplacian eigenvalues, 0 and ν. The following statements hold true.

1. If 0 is simple, then $\dot{G}$ is the complete unsigned graph or its negation.

2. If ν is simple, then $\dot{G}$ is the disjoint union of a complete signed graph $\dot{K}$ of even order and a set of isolated vertices, where the vertices of $\dot{K}$ are partitioned into 2 parts of equal size in such a way that the edges joining vertices within each part have one sign, while the edges joining vertices belonging to different parts have the opposite sign.

Proof.

(i): If the multiplicity of ν is n – 1, where n is the order of $\dot{G}$, then $N_{\dot{G}}-\nu I$ is a rank one matrix with a non-zero eigenvalue $-\nu$ and associated eigenvector j, so $N_{\dot{G}}-\nu I=-\frac{\nu }{n}J$ (where J denotes the all-1 matrix). Comparing the off-diagonal entries in the previous matrix identity, we deduce that ν must be equal to n or – n, and then we have $N_{\dot{G}}=(n-1)I-(J-I)$ or $N_{\dot{G}}=(1-n)I-(I-J)$, which means that $\dot{G}$ is the complete unsigned graph or its negation.

(ii): If ν is simple and x is the corresponding unit eigenvector, then $N_{\dot{G}}$ has the spectral decomposition $N_{\dot{G}}=\nu \mathbf{x}{\mathbf{x}}^{⊺}$. Observe that if x has a zero entry, then the corresponding vertex is not joined to any other vertex of $\dot{G}$. Therefore, we may suppose that there are no isolated vertices in $\dot{G}$. Now, if x_i and x_j are the entries corresponding to the vertices i and j, then $\nu x_i{x}_j=\pm 1$ must hold; in particular $\nu x_i^2=1$. We also have $\nu x_i^2=d_i^{\pm }$ and $\nu x_j^2=d_j^{\pm }$, and from ${\nu }^2{x}_i^2{x}_j^2=1$, we obtain $d_i^{\pm }{d}_j^{\pm }=1$. This implies $d_i^{\pm }=d_j^{\pm }=\pm 1$, which means that $\dot{G}$ is in fact net-regular with net-degree 1 or –1. From $\nu x_i^2=1$, we have that the trace of $N_{\dot{G}}$ is either n or – n, so ν equals n or – n, and thus $x_i^2=\frac{1}{n}$ with $x_i=\pm \frac{1}{\sqrt{n}}$. Since x is orthogonal to j, n must be even, i.e. $n=2k$, and the adjacency matrix $A_{\dot{G}}$ has the form$$\left(\begin{array}{cc}{J}_k-I_k& -J_k\\ -J_k& J_k-I_k\end{array}\right) \text{or} \left(\begin{array}{cc}{I}_k-J_k& J_k\\ J_k& I_k-J_k\end{array}\right),$$which leads to the desired result. □

We conclude the section with the following result.

Theorem 5.3.

Let $\dot{G}$ be a regular signed graph with degree r, order n and 3 net Laplacian eigenvalues: simple one 0, ν and μ. Then n divides $\nu \mu$ and net-degrees are the solutions of $x^2-(\nu +\mu )x+r+\nu \mu -\frac{\nu \mu }{n}=0$.

Proof.

The matrix $(N_{\dot{G}}-\nu I)(N_{\dot{G}}-\mu I)$ is a rank one matrix with one nonzero eigenvalue $\nu \mu$ and the corresponding eigenvector j. Accordingly,(5) $$(N_{\dot{G}}-\nu I)(N_{\dot{G}}-\mu I)=\frac{\nu \mu }{n}J.$$(5)

From the minimal polynomial $N_{\dot{G}}(N_{\dot{G}}^2-(\nu +\mu )N_{\dot{G}}+\nu \mu I)=O$, we conclude that $\nu +\mu$ is an integer, which means that the off-diagonal entries of the matrix in the left-hand side of (5) are integers, and this implies that νμ is divisible by n. Considering the diagonal entries, we get that the net-degree of every vertex satisfies the quadratic equation given in the statement formulation, and we are done. □

Examples for Theorems 5.1 and 5.2 can be found in the previous section. It is not difficult to see that the ∇-threshold graph generated by $(1,1,\dots ,1,-1,-1,\dots ,-1)$ (with arbitrary numbers of 1s and –1s) is an example for Theorem 5.3.

6 An application

Matrices with simple eigenvalues are required in various fields of applied mathematics. Graph theory can serve as a useful tool for their generation as well as for the analysis of their spectra. Here we emphasize an application in control theory of certain net Laplacian matrices having the mentioned spectral property.

We recall from [7, 12] that for an $n\times 1$ binary vector b and the n × n net Laplacian matrix $N_{\dot{G}}$ of a signed graph $\dot{G}$, the pair $(N_{\dot{G}},\mathbf{b})$ is controllable if $N_{\dot{G}}$ has no eigenvector orthogonal to b. The terminology comes from the domain of control theory, and for more details we refer the reader to [7, 8, 12]. In the same references one may find a more general approach concerning an arbitrary matrix and an arbitrary vector (of the appropriate size). The matrices associated with (signed) graphs have received a great deal of attention in the past; some references are [5, 7, 12, 16, 14].

It follows that if $N_{\dot{G}}$ has a repeated eigenvalue, then $N_{\dot{G}}$ has an eigenvector orthogonal to b for any choice of b. To see this, suppose that ${\mathbf{x}}_1$ and ${\mathbf{x}}_2$ are linearly independent eigenvectors associated with a fixed eigenvalue, and neither of them is orthogonal to b. Then the vector $\mathbf{x}=({\mathbf{b}}^{⊺}{\mathbf{x}}_1){\mathbf{x}}_2-({\mathbf{b}}^{⊺}{\mathbf{x}}_2){\mathbf{x}}_1$ is an eigenvector associated with the same eigenvalue, but also orthogonal to b. Therefore, a necessary controllability condition requires all the eigenvalues to be simple.

We consider the controllability of signed graphs of Theorems 3.4, 3.5 and of graphs obtained by some standard products. We first recall a result of [15] in which the spectrum of some standard products is computed.

As in Theorem 2.1, let ${\dot{G}}_1$ be a signed graph with the vertex set $\{u_1,u_2,\dots ,u_{n_1}\}$ and the eigenvalues ${\nu }_1({\dot{G}}_1),{\nu }_2({\dot{G}}_1),$ $\dots ,{\nu }_{n_1}({\dot{G}}_1)$, and let ${\dot{G}}_2$ be a signed graph with the vertex set $\{v_1,v_2,\dots ,v_{n_2}\}$ and the eigenvalues ${\nu }_1({\dot{G}}_2),{\nu }_2({\dot{G}}_2),\dots ,{\nu }_{n_2}({\dot{G}}_2)$.

We consider the products in which the set of vertices is the Cartesian product of the sets of vertices of ${\dot{G}}_1$ and ${\dot{G}}_2$. In the Cartesian product ${\dot{G}}_1\square {\dot{G}}_2$, the vertices (u_i , v_j ) and (u_k , v_l ) are adjacent if and only if u_i = u_k and $v_j\sim v_l$, or $u_i\sim u_k$ and v_j = v_l . The sign of an edge coincides with the sign of the edge it arises from. In the tensor product ${\dot{G}}_1\times {\dot{G}}_2$, the vertices (u_i , v_j ) and (u_k , v_l ) are adjacent if and only if $u_i\sim u_k$ and $v_j\sim v_l$. The sign of an edge is the product of signs of the corresponding edges of ${\dot{G}}_1$ and ${\dot{G}}_2$. In the strong product ${\dot{G}}_1⊠{\dot{G}}_2$, the vertices (u_i , v_j ) and (u_k , v_l ) are adjacent if and only if they are adjacent in any of the previous two products and the sign of an edge is determined as in the previous particular cases.

Theorem 6.1.

[15, Theorem 4] For the signed graphs ${\dot{G}}_1$ and ${\dot{G}}_2$ of orders n₁ and n₂, we have:

1. the net Laplacian eigenvalues of $N_{{\dot{G}}_1\square {\dot{G}}_2}$ are ${\nu }_i({\dot{G}}_1)+{\nu }_j({\dot{G}}_2), 1\le i\le n_1, 1\le j\le n_2$;

2. if ${\dot{G}}_1$ and ${\dot{G}}_2$ are net-regular with net-degrees ${\varrho }_1$ and ${\varrho }_2$, respectively, then the net Laplacian eigenvalues of $N_{{\dot{G}}_1\times {\dot{G}}_2}$ are ${\varrho }_1{\nu }_j({\dot{G}}_2)+{\varrho }_2{\nu }_i({\dot{G}}_1)-{\nu }_i({\dot{G}}_1){\nu }_j({\dot{G}}_2), 1\le i\le n_1, 1\le j\le n_2$;

3. if ${\dot{G}}_1$ and ${\dot{G}}_2$ are net-regular with net-degrees ${\varrho }_1$ and ${\varrho }_2$, respectively, then the net Laplacian eigenvalues of $N_{{\dot{G}}_1⊠{\dot{G}}_2}$ are $({\varrho }_1+1){\nu }_j({\dot{G}}_2)+({\varrho }_2+1){\nu }_i({\dot{G}}_1)-{\nu }_i({\dot{G}}_1){\nu }_j({\dot{G}}_2), 1\le i\le n_1, 1\le j\le n_2$.

Hence, if ${\dot{G}}_1$ and ${\dot{G}}_2$ are integral, then the signed graphs constructed in the previous theorem are also integral.

In what follows we assume that the vertices of a signed graph under consideration are labeled in the order given by the corresponding operation. For example, if $\dot{G}\cong {\dot{G}}_1{\nabla }^{+}{\dot{G}}_2$, then we first take the vertices of ${\dot{G}}_1$ and then those of ${\dot{G}}_2$.

Theorem 6.2.

If $\dot{G}$ is a signed graph with n vertices formed as in Theorem 3.4, then $(N_{\dot{G}},\mathbf{b})$ is controllable if and only if $$\mathit{b}\in \left\{\left(\begin{array}{c}0\\ 1\\ \mathit{c}\end{array}\right),\left(\begin{array}{c}1\\ 0\\ \mathit{c}\end{array}\right)\right\},$$where c is an arbitrary binary vector of length n – 2.

Proof.

First, if the generating sequence contains just 2 entries (in this case $\dot{G}$ has 2 vertices that are either non-adjacent or joined by a positive edge), then the eigenvectors of $\dot{G}$ are ${(1,1)}^{⊺}$ and ${(1,-1)}^{⊺}$, and so $(N_{\dot{G}},\mathbf{b})$ is controllable if and only if $\mathbf{b}\in \{{(0,1)}^{⊺},{(1,0)}^{⊺}\}$. Assume that the statement holds for ${\dot{G}}_{n-1}$ generated by the sequence of length n – 1. Then the eigenvectors of $\dot{G}\cong {\dot{G}}_n$ are$$\left(\begin{array}{cccccc}\mathit{j}& {\mathit{x}}_1& {\mathit{x}}_2& \cdots & {\mathit{x}}_{n-2}& -\frac{1}{n-1}\mathit{j}\\ 1& 0& 0& \cdots & 0& 1\end{array}\right),$$where ${\mathbf{x}}_1,{\mathbf{x}}_2,\dots ,{\mathbf{x}}_{n-2}$ are the eigenvectors of ${\dot{G}}_{n-1}$ orthogonal to j. Let $\mathbf{b}={({\mathbf{b}}_{n-1}^{⊺},b)}^{⊺}$, where ${\mathbf{b}}_{n-1}$ is a binary vector such that $(N_{{\dot{G}}_{n-1}},{\mathbf{b}}_{n-1})$ is controllable and $b\in \{0,1\}$. Evidently, b is non-orthogonal to the eigenvectors of $\dot{G}$ which proves one implication. Conversely, if the first two entries of b are equal, then its restriction obtained by removing the last entry is non-orthogonal to all the eigenvectors of ${\dot{G}}_{n-1}$, which contradicts our assumption on ${\dot{G}}_{n-1}$, and the proof is complete. □

We proceed with particular ∇-cographs of Theorem 3.5. We recall from Section 2 that $〈 , 〉$ stands for the Euclidean inner product.

Theorem 6.3.

Let $\dot{G}$ be a signed graph formed as in Theorem 3.5, so $\dot{G}\cong \stackrel{.}{H_1}{\nabla }^{+}(K_1\cup {\dot{H}}_2)$. The pair $(N_{\dot{G}},\mathbf{b})$ is controllable if and only if $$\mathit{b}=\left(\begin{array}{c}{\mathit{b}}_1\\ {\mathit{b}}_2\end{array}\right),$$where ${\mathbf{b}}_1$ (resp. ${\mathbf{b}}_2$) is a vector of length k (l + 1) non-orthogonal to the net eigenvectors of ${\dot{H}}_1$ ( $K_1\cup {\dot{H}}_2$), along with $〈{\mathbf{b}}_2,{\mathbf{j}}_{l+1}〉\notin \{-〈{\mathbf{b}}_1,{\mathbf{j}}_k〉,\frac{l+1}{k}〈{\mathbf{b}}_1,{\mathbf{j}}_k〉\}$.

Proof.

Let $(N_{\dot{G}},\mathbf{b})$ be controllable. If $\mathbf{b}={({\mathbf{a}}_1^{⊺},{\mathbf{a}}_2^{⊺})}^{⊺}$, where, say ${\mathbf{a}}_2$ is not as we described in the formulation of the statement, then there is an eigenvector x of $K_1\cup {\dot{H}}_2$ which is orthogonal to ${\mathbf{a}}_2$ but then ${({\mathbf{0}}^{⊺},\mathbf{x})}^{⊺}$ is an eigenvector of $\dot{G}$ orthogonal to b. If both ${\mathbf{a}}_1$ and ${\mathbf{a}}_2$ are as in the statement, but $〈{\mathbf{b}}_2,{\mathbf{j}}_{l+1}〉\in \{-〈{\mathbf{b}}_1,{\mathbf{j}}_k〉,\frac{l+1}{k}〈{\mathbf{b}}_1,{\mathbf{j}}_k〉\}$, then b is orthogonal to either ${\mathbf{j}}_n$ or the eigenvector associated with the largest eigenvalue of $\dot{G}$, and we are done.

Let now b be as in the statement, and let x be an eigenvector of $\dot{G}$. If x is associated with 0 or $k+l+1$, then $〈\mathbf{b},\mathbf{x}〉\ne 0$ due to the particular condition on $〈{\mathbf{b}}_2,{\mathbf{j}}_{l+1}〉$. If x is associated with some of the remaining eigenvalues, then $〈\mathbf{b},\mathbf{x}〉\in \{〈{\mathbf{b}}_1,{\mathbf{x}}_1〉,〈{\mathbf{b}}_2,{\mathbf{x}}_2〉\}$, where ${\mathbf{x}}_1$ (resp. ${\mathbf{x}}_2$) is an eigenvector of ${\dot{H}}_1$ ($K_1\cup {\dot{H}}_2$) orthogonal to ${\mathbf{j}}_k$ (${\mathbf{j}}_{l+1}$), which yields $〈\mathbf{b},\mathbf{x}〉\ne 0$. □

We conclude this section by considering the signed graphs of Theorem 6.1. Since the eigenvectors of all three products considered in the mentioned theorem are the Kronecker products of the corresponding eigenvectors of ${\dot{G}}_1$ and ${\dot{G}}_2$ (see [15]), we conclude that if $\mathbf{x}={(x_1,x_2,\dots ,x_{n_1})}^{⊺}$ and y are the eigenvectors of ${\dot{G}}_1$ and ${\dot{G}}_2$, respectively, then $(x_1{\mathbf{y}}^{⊺},x_2{\mathbf{y}}^{⊺},$ $\dots ,x_{n_1}{\mathbf{y}}^{⊺}{)}^{⊺}$ is an eigenvector of $\dot{G}$.

If $\mathbf{b}={({\mathbf{b}}_1^{⊺},{\mathbf{b}}_2^{⊺},\dots ,{\mathbf{b}}_{n_1}^{⊺})}^{⊺}$ is a binary vector, such that length of each ${\mathbf{b}}_i$ is n₂, then $(N_{\dot{G}},\mathbf{b})$ is controllable if and only if ${\sum }_{i=1}^{n_1}{x}_i〈\mathbf{y},{\mathbf{b}}_i〉\ne 0$, for all the eigenvectors x of ${\dot{G}}_1$ and y of ${\dot{G}}_2$. This leads to the following result.

Theorem 6.4.

Let $\dot{G}$ be a signed graph formed as in Theorem 6.1, such that its net Laplacian eigenvalues are all simple, let $(N_{{\dot{G}}_1},{\mathbf{b}}_1)$ and $(N_{{\dot{G}}_2},{\mathbf{b}}_2)$ be controllable, where ${\mathbf{b}}_1={(b_{11},b_{12},\dots ,b_{1n_1})}^{⊺}$, and let $\mathbf{b}={(b_{11}{\mathbf{b}}_2^{⊺},b_{12}{\mathbf{b}}_2^{⊺},\dots ,b_{1n_1}{\mathbf{b}}_2^{⊺})}^{⊺}$. Then $(N_{\dot{G}},\mathbf{b})$ is controllable.

Similar links between spectral graph theory and control theory can be found in [1, 3, 5, 7, 8, 12, 14, 16] and references therein.

Additional information

Funding

Research of the first three authors is supported by the Science Fund of the Republic of Serbia; grant number 7749676: Spectrally Constrained Signed Graphs with Applications in Coding Theory and Control Theory – SCSG-ctct.