Introduction
Throughout this article, G G G denotes a simple undirected graph with vertex set V ( G ) V(G) V ( G ) (or simply V V V ) and edge set E ( G ) E(G) E ( G ) . If two vertices u u u and v v v are adjacent, we write u ∼ v u\sim v u ∼ v and denote the edge between them by u v uv uv . Let λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n \lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n be the eigenvalues of the adjacency matrix A ( G ) A(G) A ( G ) . The energy of G G G is
E ( G ) = ∑ i = 1 n ∣ λ i ∣ . \mathcal{E}(G)=\sum_{i=1}^{n}|\lambda_i|. E ( G ) = i = 1 ∑ n ∣ λ i ∣.
Gutman introduced graph energy in 1978 [22 ] , motivated by its connection with the total π \pi π -electron energy of conjugated hydrocarbons. Since then it has been studied extensively; see [26 , 3 , 17 , 37 , 14 , 13 , 16 ] and the references therein. Because the energy depends on the whole spectrum, it can rarely be computed in closed form. Much of the literature is therefore devoted to bounding it in terms of simpler graph parameters, such as the number of vertices or edges, the chromatic number, the matching number and the vertex cover number, see [2 , 32 , 43 , 23 ] .
A set S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) is a vertex cover of G G G if every edge of G G G has at least one end in S S S . The vertex cover number τ ( G ) \tau(G) τ ( G ) is the size of a minimum vertex cover. A set of vertices is independent if no two of its vertices are adjacent, and the independence number α ( G ) \alpha(G) α ( G ) is the size of a maximum independent set. The complement of a vertex cover is an independent set and vice versa, so τ ( G ) + α ( G ) = n \tau(G) + \alpha(G) = n τ ( G ) + α ( G ) = n .
In the 1980s, Fajtlowicz [19 , 18 ] conjectured, on the basis of his computer program Graffiti, that every graph G G G satisfies
E ( G ) ≥ 2 τ ( G ) ; (1) \mathcal{E}(G) \ge2\tau(G); \tag*{(1)} E ( G ) ≥ 2 τ ( G ) ; (1)
see also [5 Conjecture 543] and [29 ] . The conjecture attracted considerable attention. Wang and Ma [40 ] proved the weaker bound E ( G ) ≥ 2 τ ( G ) − 2 c ( G ) \mathcal{E}(G) \ge2\tau(G) - 2c(G) E ( G ) ≥ 2 τ ( G ) − 2 c ( G ) , where c ( G ) c(G) c ( G ) is the number of odd cycles of G G G , and Samanta and Kannan [36 ] extended it to complex unit gain graphs. Wong, Wang and Chu [42 ] proved E ( G ) ≥ 2 μ ( G ) \mathcal{E}(G) \ge2\mu(G) E ( G ) ≥ 2 μ ( G ) in terms of the matching number μ ( G ) \mu(G) μ ( G ) , with analogues for oriented graphs [39 ] , mixed graphs [41 ] and complex unit gain graphs [27 ] . Since τ ( G ) ≥ μ ( G ) \tau(G) \ge\mu(G) τ ( G ) ≥ μ ( G ) , inequality (1) improves this last bound. Inequality (1) was verified for several classes of graphs in [4 , 34 ] , and Abiad, Coutinho, Juliano and Reijnders [1 ] obtained further partial results using semidefinite programming. The conjecture was finally settled by Kumar and Pragada [25 ] , who proved that (1) holds for every graph. Shortly afterwards, Mojallal [31 ] determined all graphs attaining equality.
It is natural to ask whether (1) survives when the edges carry weights. A signed graph [44 ] Γ = ( G , σ ) \Gamma= (G,\sigma) Γ = ( G , σ ) consists of an underlying graph G G G together with a signature σ : E ( G ) → { − 1 , + 1 } \sigma: E(G) \to\{-1,+1\} σ : E ( G ) → { − 1 , + 1 } . Its adjacency matrix A ( Γ ) A(\Gamma) A ( Γ ) is a symmetric ∣ V ∣ × ∣ V ∣ |V| \times|V| ∣ V ∣ × ∣ V ∣ matrix, defined by
( u , v ) -th entry of A ( Γ ) = A ( Γ ) u v = { σ ( u v ) , if u ∼ v , 0 , otherwise, (u,v)\text{-th entry of } A(\Gamma) = A(\Gamma)_{uv} =
\begin{cases}
\sigma(uv), & \text{if } u \sim v,\\
0, & \text{otherwise,}
\end{cases} ( u , v ) -th entry of A ( Γ ) = A ( Γ ) uv = { σ ( uv ) , 0 , if u ∼ v , otherwise,
and its energy E ( Γ ) \mathcal{E}(\Gamma) E ( Γ ) is the sum of the absolute values of the eigenvalues of A ( Γ ) A(\Gamma) A ( Γ ) . An unsigned graph is the special case in which every edge is positive, that is, A ( G ) = A ( ( G , + 1 ) ) A(G) = A((G,+1)) A ( G ) = A (( G , + 1 )) . Signed graphs are in turn a special case of the complex unit gain graphs (T-gain graphs) introduced by Reff [33 ] , whose edges carry complex numbers of modulus one. Switching at a vertex set U U U reverses the sign of every edge with exactly one end in U U U ; it does not change the spectrum. A signed graph is balanced if it can be switched to the all-positive signature, and antibalanced if ( G , − σ ) (G,-\sigma) ( G , − σ ) is balanced.
In this article, we prove that (1) holds for every signed graph and we completely characterize the case of equality. The extremal signed graphs are described by the following family. Let N ≥ 1 N \ge1 N ≥ 1 and let a = ( a 1 , … , a N ) a=(a_1,\ldots,a_N) a = ( a 1 , … , a N ) and b ( b 1 , … , b N ) b(b_1,\ldots,b_N) b ( b 1 , … , b N ) be vectors of nonnegative integers. The additive rook graph Rook N ( a , b ) \operatorname{Rook}_N(a,b) Rook N ( a , b ) is the signed graph built on an N × N N \times N N × N board with a i + b j a_i+b_j a i + b j vertices on square ( i , j ) (i,j) ( i , j ) , in which two vertices are joined by a positive edge if they lie in the same row but in different columns, and by a negative edge if they lie in the same column but in different rows. All other pairs of vertices are non-adjacent. Our main result is the following.
Theorem 0.1. Let Γ = ( G , σ ) \Gamma=(G,\sigma) Γ = ( G , σ ) be a signed graph with vertex cover number τ ( G ) \tau(G) τ ( G ) . Then
E ( Γ ) ≥ 2 τ ( G ) . (2) \mathcal{E}(\Gamma) \ge2\tau(G). \tag*{(2)} E ( Γ ) ≥ 2 τ ( G ) . (2) Equality holds if and only if every connected component of Γ \Gamma Γ is switching equivalent to an additive rook graph Rook N ( a , b ) \operatorname{Rook}_{N}(a,b) Rook N ( a , b ) .
Theorem 0.1 reveals features that do not appear in the unsigned case. The class of underlying graphs that attain equality is strictly larger than for unsigned graphs, and equality is attained by some signed graphs that are neither balanced nor antibalanced. This leads to a balanced/antibalanced trichotomy for the extremal signed graphs. Restricting Theorem 0.1 to unsigned graphs, we recover Mojallal’s characterization [31 ] . On the other hand, the bound does not extend further: we give an example showing that (2) fails for the Hermitian adjacency matrices of mixed graphs and for T \mathbb{T} T -gain graphs.
The article is organized as follows. § 2 collects the notation, definitions and preliminary results used throughout. In § 3 , we introduce additive rook graphs and establish their basic properties. § 4 contains the proof of (2) . § 5 characterizes equality in two steps: we first show that every additive rook graph attains equality, and then prove the converse, namely that every signed graph attaining equality is switching equivalent to a disjoint union of additive rook graphs. Finally, in § 7 , we state Mojallal’s theorem in full and deduce it from Theorem 0.1, and we present an example showing that the bound cannot be extended to Hermitian adjacency matrices of mixed graphs or to T \mathbb{T} T -gain graphs.
Preliminaries
Throughout this article, G G G denotes a finite simple undirected graph with vertex set V ( G ) V(G) V ( G ) and edge set E ( G ) E(G) E ( G ) . We put n = ∣ V ( G ) ∣ n=|V(G)| n = ∣ V ( G ) ∣ and m = ∣ E ( G ) ∣ m=|E(G)| m = ∣ E ( G ) ∣ . The edge joining two vertices u u u and v v v is written u v uv uv , and we write u ∼ v u\sim v u ∼ v when u v ∈ E ( G ) uv\in E(G) uv ∈ E ( G ) . For a vertex v v v , the set N ( v ) = { u ∈ V ( G ) : u ∼ v } N(v)=\{u\in V(G):u\sim v\} N ( v ) = { u ∈ V ( G ) : u ∼ v } is its neighbourhood, N [ v ] = N ( v ) ∪ { v } N[v]=N(v)\cup\{v\} N [ v ] = N ( v ) ∪ { v } is its closed neighbourhood, and d v = ∣ N ( v ) ∣ d_v=|N(v)| d v = ∣ N ( v ) ∣ is its degree. For a signed graph Γ = ( G , σ ) \Gamma=(G,\sigma) Γ = ( G , σ ) , every purely graph-theoretic notion is taken from the underlying graph G G G . So the vertex covers and the independent sets of Γ \Gamma Γ are those of G G G , and we write τ ( Γ ) = τ ( G ) \tau(\Gamma)=\tau(G) τ ( Γ ) = τ ( G ) and α ( Γ ) = α ( G ) \alpha(\Gamma)=\alpha(G) α ( Γ ) = α ( G ) . For U ⊆ V ( G ) U\subseteq V(G) U ⊆ V ( G ) , the signed graph induced by Γ \Gamma Γ on V ( G ) ∖ U V(G)\setminus U V ( G ) ∖ U is denoted by Γ − U \Gamma-U Γ − U , and its edges keep their signs from Γ \Gamma Γ .
If the rows and columns of a matrix M M M are indexed by V ( G ) V(G) V ( G ) , then the ( u , v ) (u,v) ( u , v ) -th entry of M M M is written M u v M_{uv} M uv . The adjacency matrix A ( Γ ) A(\Gamma) A ( Γ ) is the real symmetric matrix with A ( Γ ) u v = σ ( u v ) A(\Gamma)_{uv}=\sigma(uv) A ( Γ ) uv = σ ( uv ) if u ∼ v u\sim v u ∼ v , and A ( Γ ) u v = 0 A(\Gamma)_{uv}=0 A ( Γ ) uv = 0 otherwise. If λ 1 ≥ ⋯ ≥ λ n \lambda_1\ge\cdots\ge\lambda_n λ 1 ≥ ⋯ ≥ λ n are the eigenvalues of A ( Γ ) A(\Gamma) A ( Γ ) , the energy of Γ \Gamma Γ is defined as E ( Γ ) = ∑ k = 1 n ∣ λ k ∣ \mathcal{E}(\Gamma)=\sum_{k=1}^{n}|\lambda_k| E ( Γ ) = ∑ k = 1 n ∣ λ k ∣ .
A switching function is a map ζ : V ( G ) → { 1 , − 1 } \zeta:V(G)\to\{1,-1\} ζ : V ( G ) → { 1 , − 1 } . It turns Γ = ( G , σ ) \Gamma=(G,\sigma) Γ = ( G , σ ) into the signed graph Γ ζ = ( G , σ ζ ) \Gamma^\zeta=(G,\sigma^\zeta) Γ ζ = ( G , σ ζ ) , where σ ζ ( u v ) = ζ ( u ) σ ( u v ) ζ ( v ) \sigma^\zeta(uv)=\zeta(u)\sigma(uv)\zeta(v) σ ζ ( uv ) = ζ ( u ) σ ( uv ) ζ ( v ) for every edge u v uv uv . We then say that Γ \Gamma Γ and Γ ζ \Gamma^\zeta Γ ζ are switching equivalent, and write Γ ∼ Γ ζ \Gamma\sim\Gamma^\zeta Γ ∼ Γ ζ . With D = diag ( ζ ( v ) ) v ∈ V ( G ) D=\operatorname{diag}(\zeta(v))_{v\in V(G)} D = diag ( ζ ( v ) ) v ∈ V ( G ) we have A ( Γ ζ ) = D A ( Γ ) D A(\Gamma^\zeta)=D A(\Gamma)D A ( Γ ζ ) = D A ( Γ ) D , and we also write Γ D \Gamma^D Γ D for Γ ζ \Gamma^\zeta Γ ζ . As D − 1 = D D^{-1}=D D − 1 = D , switching equivalent signed graphs have the same eigenvalues, and so the same energy. The sign of a cycle is the product of the signs of its edges, and the cycle is positive when this product equals 1 1 1 . A signed graph is balanced if all of its cycles are positive. The negation of Γ \Gamma Γ is − Γ = ( G , − σ ) -\Gamma=(G,-\sigma) − Γ = ( G , − σ ) . Since A ( − Γ ) = − A ( Γ ) A(-\Gamma)=-A(\Gamma) A ( − Γ ) = − A ( Γ ) , we get E ( − Γ ) = E ( Γ ) \mathcal{E}(-\Gamma)=\mathcal{E}(\Gamma) E ( − Γ ) = E ( Γ ) . We call Γ \Gamma Γ antibalanced if − Γ -\Gamma − Γ is balanced.
For a real symmetric matrix S S S , we write S ⪰ 0 S\succeq0 S ⪰ 0 if S S S is positive semidefinite, and S ⪰ T S\succeq T S ⪰ T if S − T ⪰ 0 S-T\succeq0 S − T ⪰ 0 . We use J J J for the all-ones matrix and 1 \mathbf{1} 1 for the all-ones vector, and we write 1 k \mathbf{1}_k 1 k when its length k k k has to be shown. For other notation and basic facts from matrix theory, we refer to [24 ] . In addition, we shall repeatedly use the following standard facts.
(F1) Every real symmetric n × n n\times n n × n matrix S S S can be written as S = ∑ k = 1 n λ k u k u k T S=\sum_{k=1}^{n}\lambda_k u_k u_k^{\mathsf{T}} S = ∑ k = 1 n λ k u k u k T , where λ 1 , … , λ n \lambda_1,\ldots,\lambda_n λ 1 , … , λ n are the eigenvalues of S S S and u 1 , … , u n u_1,\ldots,u_n u 1 , … , u n is an orthonormal basis of corresponding eigenvectors.
(F2) For S S S as in (F1), the matrices S + = ∑ λ k > 0 λ k u k u k T S_+=\sum_{\lambda_k>0}\lambda_k u_k u_k^{\mathsf{T}} S + = ∑ λ k > 0 λ k u k u k T and S − = − ∑ λ k < 0 λ k u k u k T S_-=-\sum_{\lambda_k<0}\lambda_k u_k u_k^{\mathsf{T}} S − = − ∑ λ k < 0 λ k u k u k T satisfy S ± ⪰ 0 S_\pm\succeq0 S ± ⪰ 0 , S + S − = S − S + = 0 S_+S_-=S_-S_+=0 S + S − = S − S + = 0 and S = S + − S − S=S_+-S_- S = S + − S − . We put ∣ S ∣ = S + + S − |S|=S_++S_- ∣ S ∣ = S + + S − . Note that ∣ S ∣ |S| ∣ S ∣ is not the matrix of the absolute values of the entries of S S S . The energy of S S S is E ( S ) = tr ∣ S ∣ = ∑ k ∣ λ k ∣ \mathcal{E}(S)=\operatorname{tr}|S|=\sum_k|\lambda_k| E ( S ) = tr ∣ S ∣ = ∑ k ∣ λ k ∣ . If in addition tr S = 0 \operatorname{tr}S=0 tr S = 0 , then tr S + = tr S − = 1 2 E ( S ) \operatorname{tr}S_+=\operatorname{tr}S_-=\frac{1}{2}\mathcal{E}(S) tr S + = tr S − = 2 1 E ( S ) .
(F3) A matrix S S S with rows and columns indexed by V V V satisfies S ⪰ 0 S\succeq0 S ⪰ 0 if and only if there are vectors s v s_v s v (v ∈ V v\in V v ∈ V ) in some R k \mathbb{R}^k R k such that S u v = ⟨ s u , s v ⟩ S_{uv}=\langle s_u,s_v\rangle S uv = ⟨ s u , s v ⟩ for all u , v ∈ V u,v\in V u , v ∈ V . These vectors are called a Gram representation of S S S .
(F4) For x , y ∈ R k x,y\in\mathbb{R}^k x , y ∈ R k we have ∣ ⟨ x , y ⟩ ∣ ≤ ∥ x ∥ ∥ y ∥ |\langle x,y\rangle|\leq\|x\|\|y\| ∣ ⟨ x , y ⟩ ∣ ≤ ∥ x ∥∥ y ∥ , and equality holds if and only if x x x and y y y are linearly dependent. In particular, if ∥ x ∥ = ∥ y ∥ = r > 0 \|x\|=\|y\|=r>0 ∥ x ∥ = ∥ y ∥ = r > 0 , then ⟨ x , y ⟩ = r 2 \langle x,y\rangle=r^2 ⟨ x , y ⟩ = r 2 exactly when x = y x=y x = y , and ⟨ x , y ⟩ = − r 2 \langle x,y\rangle=-r^2 ⟨ x , y ⟩ = − r 2 exactly when x = − y x=-y x = − y .
Finally, we recall two families of graphs. The complete multipartite graph K x , … , x K_{x,\ldots,x} K x , … , x with r r r parts consists of r r r independent sets of size x x x , and two vertices are adjacent exactly when they lie in different parts. For r ≥ 2 r\geq2 r ≥ 2 and x , y ≥ 1 x,y\geq1 x , y ≥ 1 , the graph H r ( x , y ) H_r(x,y) H r ( x , y ) is built from two complete multipartite graphs, one with parts X 1 , … , X r X_1,\ldots,X_r X 1 , … , X r of size x x x and the other with parts Y 1 , … , Y r Y_1,\ldots,Y_r Y 1 , … , Y r of size y y y , by joining every vertex of X i X_i X i to every vertex of Y i Y_i Y i for each i i i . Thus the edges of H r ( x , y ) H_r(x,y) H r ( x , y ) are exactly the pairs u v uv uv with u ∈ X i u\in X_i u ∈ X i , v ∈ X j v\in X_j v ∈ X j and i ≠ j i\ne j i = j , the pairs u v uv uv with u ∈ Y i u\in Y_i u ∈ Y i , v ∈ Y j v\in Y_j v ∈ Y j and i ≠ j i\ne j i = j , and the pairs u v uv uv with u ∈ X i u\in X_i u ∈ X i and v ∈ Y i v\in Y_i v ∈ Y i .
Additive rook graphs and independence numbers
In this section we introduce additive rook graphs . These signed graphs turn out to be exactly the extremal graphs for the energy bound (2) . We first define a more general family called signed grid graphs and obtain additive rook graphs as a special case. We then determine the independence number and the vertex cover number of additive rook graphs. Finally, we prove a few further properties that are needed in § 5 .
Definition 2.1 (Signed grid graph). Let W = ( w i j ) W=(w_{ij}) W = ( w ij ) be an s × t s \times t s × t matrix of nonnegative integers. The signed grid graph Γ [ W ] \Gamma[W] Γ [ W ] has vertex set V : = ⋃ i , j V i j V:=\bigcup_{i,j}V_{ij} V := ⋃ i , j V ij where ∣ V i j ∣ = w i j \lvert V_{ij}\rvert=w_{ij} ∣ V ij ∣ = w ij . The set V i j V_{ij} V ij is called the square ( i , j ) (i,j) ( i , j ) . The i i i -th row is R i : = ⋃ j = 1 t V i j R_i:=\bigcup_{j=1}^{t}V_{ij} R i := ⋃ j = 1 t V ij and the j j j -th column is C j : = ⋃ i = 1 s V i j C_j:=\bigcup_{i=1}^{s}V_{ij} C j := ⋃ i = 1 s V ij . For v ∈ V i j v\in V_{ij} v ∈ V ij we write r ( v ) = i r(v)=i r ( v ) = i and c ( v ) = j c(v)=j c ( v ) = j , meaning that v v v lies in the i i i -th row and the j j j -th column. Two distinct vertices u u u and v v v of Γ [ W ] \Gamma[W] Γ [ W ] are joined by a positive edge if r ( u ) = r ( v ) r(u)=r(v) r ( u ) = r ( v ) and c ( u ) ≠ c ( v ) c(u)\ne c(v) c ( u ) = c ( v ) , and by a negative edge if c ( u ) = c ( v ) c(u)=c(v) c ( u ) = c ( v ) and r ( u ) ≠ r ( v ) r(u)\ne r(v) r ( u ) = r ( v ) . All other pairs of distinct vertices are non-adjacent.
Next we define two matrices and a graph.
Definition 2.2. Let Γ [ W ] \Gamma[W] Γ [ W ] be the signed grid graph of an s × t s \times t s × t matrix W W W . We define the following matrices and graph associated with Γ [ W ] \Gamma[W] Γ [ W ] .
(i) The row-incidence matrix R R R is the ∣ V ∣ × s \lvert V\rvert\times s ∣ V ∣ × s matrix with R v i = 1 R_{vi}=1 R v i = 1 if r ( v ) = i r(v)=i r ( v ) = i and R v i = 0 R_{vi}=0 R v i = 0 otherwise.
(ii) The column-incidence matrix C C C is the ∣ V ∣ × t \lvert V\rvert\times t ∣ V ∣ × t matrix with C v j = 1 C_{vj}=1 C v j = 1 if c ( v ) = j c(v)=j c ( v ) = j and C v j = 0 C_{vj}=0 C v j = 0 otherwise.
(iii) The cell graph B ( W ) \mathcal{B}(W) B ( W ) is the bipartite graph whose vertices are the nonempty rows and the nonempty columns, in which row i i i is adjacent to column j j j if and only if w i j > 0 w_{ij}>0 w ij > 0 .
Examples 2.3. Let W = ( 3 2 3 2 3 2 ) W=\begin{pmatrix}3&2&3\\2&3&2\end{pmatrix} W = ( 3 2 2 3 3 2 ) . The signed grid graph Γ [ W ] \Gamma[W] Γ [ W ] is shown in Figure 1 . In Γ [ W ] \Gamma[W] Γ [ W ] , the vertex set V = ⋃ i = 1 2 ⋃ j = 1 3 V i j V=\bigcup_{i=1}^{2}\bigcup_{j=1}^{3}V_{ij} V = ⋃ i = 1 2 ⋃ j = 1 3 V ij . It has two rows, R 1 = V 11 ∪ V 12 ∪ V 13 R_1=V_{11}\cup V_{12}\cup V_{13} R 1 = V 11 ∪ V 12 ∪ V 13 and R 2 = V 21 ∪ V 22 ∪ V 23 R_2=V_{21}\cup V_{22}\cup V_{23} R 2 = V 21 ∪ V 22 ∪ V 23 . Also, it has three columns C 1 = V 11 ∪ V 21 C_1=V_{11}\cup V_{21} C 1 = V 11 ∪ V 21 , C 2 = V 12 ∪ V 22 C_2=V_{12}\cup V_{22} C 2 = V 12 ∪ V 22 , and C 3 = V 13 ∪ V 23 C_3=V_{13}\cup V_{23} C 3 = V 13 ∪ V 23 .
Figure 1. The signed grid graph Γ [ W ] \Gamma[W] Γ [ W ] .
Definition 2.4 (Additive rook graph). Let N ≥ 1 N \ge1 N ≥ 1 and let a = ( a 1 , … , a N ) a=(a_1,\ldots,a_N) a = ( a 1 , … , a N ) and b = ( b 1 , … , b N ) b=(b_1,\ldots,b_N) b = ( b 1 , … , b N ) be nonnegative integer vectors, not both zero. The additive rook graph Rook N ( a , b ) \operatorname{Rook}_N(a,b) Rook N ( a , b ) is the signed grid graph Γ [ W ] \Gamma[W] Γ [ W ] , where W W W is the N × N N \times N N × N matrix with entries w i j = a i + b j w_{ij}=a_i+b_j w ij = a i + b j . We denote
ℓ : = ∑ i = 1 N a i + ∑ j = 1 N b j . \ell:= \sum_{i=1}^{N} a_i+\sum_{j=1}^{N} b_j. ℓ := i = 1 ∑ N a i + j = 1 ∑ N b j . Thus Rook N ( a , b ) \operatorname{Rook}_N(a,b) Rook N ( a , b ) is obtained by placing a i + b j a_i+b_j a i + b j vertices on square ( i , j ) (i,j) ( i , j ) of an N × N N \times N N × N chessboard; vertices sharing only a row are joined by positive edges, and vertices sharing only a column by negative edges.
Examples 2.5. The following signed graphs are additive rook graphs up to switching equivalence. Here 0 \mathbf{0} 0 is the zero vector of suitable size.
Consider the third line of the table. In Rook r ( ( x , y , 0 , … , 0 ) , 0 ) \operatorname{Rook}_r((x,y,0,\ldots,0),\mathbf{0}) Rook r (( x , y , 0 , … , 0 ) , 0 ) only the first two rows of the board are nonempty. Write X j = V 1 j X_j=V_{1j} X j = V 1 j and Y j = V 2 j Y_j=V_{2j} Y j = V 2 j , so that ∣ X j ∣ = x |X_j|=x ∣ X j ∣ = x and ∣ Y j ∣ = y |Y_j|=y ∣ Y j ∣ = y . Two different squares X j X_j X j and X l X_l X l are joined by positive edges, and the same holds for Y j Y_j Y j and Y l Y_l Y l . Each X j X_j X j is joined to Y j Y_j Y j by negative edges, and there are no other edges. Switching at all vertices of Y 1 ∪ ⋯ ∪ Y r Y_1\cup\cdots\cup Y_r Y 1 ∪ ⋯ ∪ Y r makes every edge positive. The resulting graph is exactly H r ( x , y ) H_r(x,y) H r ( x , y ) of Mojallal [31 ] .
We now list some basic properties of signed grid graphs. Here 1 k \mathbf{1}_k 1 k denotes the all-ones column vector of length k k k .
Lemma 2.6. Let W W W be an s × t s \times t s × t matrix of nonnegative integers and let V V V be the vertex set of Γ [ W ] \Gamma[W] Γ [ W ] .
(i) A ( Γ [ W ] ) = R R T − C C T A(\Gamma[W])=RR^{\mathsf{T}}-CC^{\mathsf{T}} A ( Γ [ W ]) = R R T − C C T . Moreover, R 1 s = C 1 t = 1 ∣ V ∣ R\mathbf{1}_s=C\mathbf{1}_t=\mathbf{1}_{|V|} R 1 s = C 1 t = 1 ∣ V ∣ , and all diagonal entries of R R T RR^{\mathsf{T}} R R T and C C T CC^{\mathsf{T}} C C T are equal to 1.
(ii) A set U ⊆ V U\subseteq V U ⊆ V is independent if and only if the squares meeting U U U lie in pairwise distinct rows and pairwise distinct columns.
(iii) Γ [ W T ] = − Γ [ W ] \Gamma[W^{\mathsf{T}}]=-\Gamma[W] Γ [ W T ] = − Γ [ W ] , where square ( i , j ) (i,j) ( i , j ) of W W W is identified with square ( j , i ) (j,i) ( j , i ) of W T W^{\mathsf{T}} W T . In particular, the two signed graphs have the same underlying graph.
(iv) Adding or deleting zero rows or zero columns of W W W does not change Γ [ W ] \Gamma[W] Γ [ W ] or B ( W ) \mathcal{B}(W) B ( W ) .
(v) If Γ [ W ] \Gamma[W] Γ [ W ] is connected, then so is B ( W ) \mathcal{B}(W) B ( W ) .
Proof. (i) Since every vertex lies in exactly one row, ( R R T ) u v = ∑ i R u i R v i (RR^{\mathsf{T}})_{uv} = \sum_i R_{ui}R_{vi} ( R R T ) uv = ∑ i R u i R v i is 1 if r ( u ) = r ( v ) r(u) = r(v) r ( u ) = r ( v ) and 0 otherwise. Similarly, ( C C T ) u v (CC^{\mathsf{T}})_{uv} ( C C T ) uv is 1 if c ( u ) = c ( v ) c(u) = c(v) c ( u ) = c ( v ) and 0 otherwise. Hence ( R R T − C C T ) u v (RR^{\mathsf{T}}-CC^{\mathsf{T}})_{uv} ( R R T − C C T ) uv equals 1 if u u u and v v v share only a row, − 1 -1 − 1 if they share only a column, and 0 if they share both or neither (in particular when u = v u=v u = v ). This is exactly the adjacency rule of Γ [ W ] \Gamma[W] Γ [ W ] . Each row of R R R and of C C C has a single entry 1, which gives the remaining assertions.
(ii) Two distinct vertices are non-adjacent precisely when they lie in the same square or have neither a row nor a column in common. So U U U is independent if and only if no two of the squares meeting U U U share a row or a column.
(iii) Transposing W W W interchanges the row and the column of each vertex. Hence the roles of R R R and C C C are exchanged, and by (i) the adjacency matrix becomes C C T − R R T = − A ( Γ [ W ] ) CC^{\mathsf{T}}-RR^{\mathsf{T}}=-A(\Gamma[W]) C C T − R R T = − A ( Γ [ W ]) .
(iv) A zero row or column contains no vertices and is not a vertex of B ( W ) \mathcal{B}(W) B ( W ) .
(v) Each nonempty square ( i , j ) (i,j) ( i , j ) is an edge of B ( W ) \mathcal{B}(W) B ( W ) , and B ( W ) \mathcal{B}(W) B ( W ) has no isolated vertices. Suppose B ( W ) \mathcal{B}(W) B ( W ) is disconnected, let K K K be one of its components, and let U U U be the set of vertices of Γ [ W ] \Gamma[W] Γ [ W ] whose square is an edge of K K K . Then U ≠ ∅ U\ne\varnothing U = ∅ , and V ∖ U ≠ ∅ V\setminus U\ne\varnothing V ∖ U = ∅ since another component also contains an edge. If u ∈ U u\in U u ∈ U and v ∉ U v\notin U v ∈ / U , their squares lie in different components of B ( W ) \mathcal{B}(W) B ( W ) , so they share no row and no column, and u , v u,v u , v are non-adjacent. Therefore Γ [ W ] \Gamma[W] Γ [ W ] is disconnected.
Next we compute the independence number of Γ [ W ] \Gamma[W] Γ [ W ] by means of rook placements. We write [ k ] = { 1 , … , k } [k]=\{1,\ldots,k\} [ k ] = { 1 , … , k } .
Lemma 2.7. Let W W W be an s × t s\times t s × t matrix of nonnegative integers with s ≤ t s\le t s ≤ t , and let n = ∑ i , j w i j n=\sum_{i,j}w_{ij} n = ∑ i , j w ij . For an injection function φ : [ s ] → [ t ] \varphi:[s]\to[t] φ : [ s ] → [ t ] put η ( φ ) = ∑ i = 1 s w i φ ( i ) \eta(\varphi)=\sum_{i=1}^{s}w_{i\varphi(i)} η ( φ ) = ∑ i = 1 s w i φ ( i ) ; this is the number of vertices on the squares occupied by the s s s non-attacking rooks placed at ( i , φ ( i ) ) (i,\varphi(i)) ( i , φ ( i )) . Then
(a) α ( Γ [ W ] ) = max φ η ( φ ) \alpha(\Gamma[W])=\max_{\varphi}\eta(\varphi) α ( Γ [ W ]) = max φ η ( φ ) ;
(b) the average of η ( φ ) \eta(\varphi) η ( φ ) over all injections φ \varphi φ is n / t n/t n / t ; hence α ( Γ [ W ] ) ≥ n / t \alpha(\Gamma[W])\ge n/t α ( Γ [ W ]) ≥ n / t ;
(c) α ( Γ [ W ] ) = n / t \alpha(\Gamma[W])=n/t α ( Γ [ W ]) = n / t if and only if η \eta η is constant;
(d) η \eta η is constant if and only if either s < t s<t s < t and w i j = a i w_{ij}=a_i w ij = a i for some integers a i a_i a i , or s = t s=t s = t and w i j = a i + b j w_{ij}=a_i+b_j w ij = a i + b j for some integers a i , b j a_i,b_j a i , b j .
Proof. (a) For each injection φ \varphi φ , the set U φ = ⋃ i V i φ ( i ) U_\varphi=\bigcup_i V_{i\varphi(i)} U φ = ⋃ i V i φ ( i ) is independent by Lemma 2.6 (ii), and ∣ U φ ∣ = η ( φ ) |U_\varphi|=\eta(\varphi) ∣ U φ ∣ = η ( φ ) . Conversely, let U U U be independent. By Lemma 2.6 (ii), the squares meeting U U U are ( i 1 , j 1 ) , … , ( i k , j k ) (i_1,j_1),\ldots,(i_k,j_k) ( i 1 , j 1 ) , … , ( i k , j k ) with distinct i i i 's and distinct j j j 's. Since t − k ≥ s − k t-k\ge s-k t − k ≥ s − k , the remaining s − k s-k s − k rows can be mapped injectively into the t − k t-k t − k unused columns. This extends i r ↦ j r i_r\mapsto j_r i r ↦ j r to an injection φ \varphi φ with U ⊆ U φ U\subseteq U_\varphi U ⊆ U φ , so ∣ U ∣ ≤ η ( φ ) |U|\le\eta(\varphi) ∣ U ∣ ≤ η ( φ ) . (b) There are t ! / ( t − s ) ! t!/(t-s)! t ! / ( t − s )! injections, and exactly ( t − 1 ) ! / ( t − s ) ! (t-1)!/(t-s)! ( t − 1 )! / ( t − s )! of them satisfy φ ( i ) = j \varphi(i)=j φ ( i ) = j for a fixed pair ( i , j ) (i,j) ( i , j ) , that is, a fraction 1 / t 1/t 1/ t of all. Hence the average of η \eta η is 1 t ∑ i , j w i j = n / t \frac{1}{t}\sum_{i,j}w_{ij}=n/t t 1 ∑ i , j w ij = n / t , and the maximum is at least this value.
(c) The maximum of finitely many numbers equals their average if and only if they are all equal.
(d) If s < t s<t s < t and w i j = a i w_{ij}=a_i w ij = a i , then η ≡ ∑ i a i \eta\equiv\sum_i a_i η ≡ ∑ i a i . If s = t s=t s = t and w i j = a i + b j w_{ij}=a_i+b_j w ij = a i + b j , then every injection is a permutation and η ≡ ∑ i a i + ∑ j b j \eta\equiv\sum_i a_i+\sum_j b_j η ≡ ∑ i a i + ∑ j b j .
Conversely, suppose η \eta η is constant. Let s < t s<t s < t . Fix a row i i i and columns j ≠ j ′ j\ne j' j = j ′ . As s − 1 ≤ t − 2 s-1\le t-2 s − 1 ≤ t − 2 , the other s − 1 s-1 s − 1 rows can be mapped injectively into [ t ] ∖ { j , j ′ } [t]\setminus\{j,j'\} [ t ] ∖ { j , j ′ } . Extending this map by i ↦ j i\mapsto j i ↦ j or by i ↦ j ′ i\mapsto j' i ↦ j ′ gives two injections of equal weight, so w i j = w i j ′ w_{ij}=w_{ij'} w ij = w i j ′ . Hence w i j = a i w_{ij}=a_i w ij = a i for all i , j i,j i , j .
Let s = t s=t s = t . If s = 1 s=1 s = 1 , take a 1 = w 11 a_1=w_{11} a 1 = w 11 and b 1 = 0 b_1=0 b 1 = 0 . If s ≥ 2 s\ge2 s ≥ 2 , let i ≠ k i\ne k i = k and j ≠ l j\ne l j = l . Choose a permutation π \pi π with π ( i ) = j \pi(i)=j π ( i ) = j and π ( k ) = l \pi(k)=l π ( k ) = l , and let π ′ \pi' π ′ agree with π \pi π except that π ′ ( i ) = l \pi'(i)=l π ′ ( i ) = l and π ′ ( k ) = j \pi'(k)=j π ′ ( k ) = j . Then η ( π ) = η ( π ′ ) \eta(\pi)=\eta(\pi') η ( π ) = η ( π ′ ) gives
w i j + w k l = w i l + w k j . (3) w_{ij}+w_{kl}=w_{il}+w_{kj}. \tag*{(3)} w ij + w k l = w i l + w k j . (3)
This identity is trivial when i = k i=k i = k or j = l j=l j = l , so it holds for all i , j , k , l i,j,k,l i , j , k , l . Setting a i = w i 1 a_i=w_{i1} a i = w i 1 and b j = w 1 j − w 11 b_j=w_{1j}-w_{11} b j = w 1 j − w 11 , identity (E) with k = l = 1 k=l=1 k = l = 1 gives w i j = a i + b j w_{ij}=a_i+b_j w ij = a i + b j .
Remark 2.8. The integers a i , b j a_i,b_j a i , b j in Lemma 2.7(d) may be chosen nonnegative. Indeed, let b j 0 = min j b j b_{j_0}=\min_j b_j b j 0 = min j b j and replace a i a_i a i by a i + b j 0 a_i+b_{j_0} a i + b j 0 and b j b_j b j by b j − b j 0 b_j-b_{j_0} b j − b j 0 . This does not change w i j w_{ij} w ij ; the new b j b_j b j are nonnegative, and the new a i a_i a i equal w i j 0 ≥ 0 w_{ij_0}\ge0 w i j 0 ≥ 0 . Hence, if W W W is square with w i j = a i + b j w_{ij}=a_i+b_j w ij = a i + b j , then Γ [ W ] \Gamma[W] Γ [ W ] is an additive rook graph.
Corollary 2.9. The additive rook graph Rook N ( a , b ) \operatorname{Rook}_N(a,b) Rook N ( a , b ) has n = N ℓ n=N\ell n = N ℓ vertices, α = ℓ \alpha=\ell α = ℓ and τ = ( N − 1 ) ℓ \tau=(N-1)\ell τ = ( N − 1 ) ℓ .
Proof. We have n = ∑ i , j ( a i + b j ) = N ℓ n=\sum_{i,j}(a_i+b_j)=N\ell n = ∑ i , j ( a i + b j ) = N ℓ . Every permutation π \pi π of [ N ] [N] [ N ] has weight ∑ i a i + ∑ i b π ( i ) = ℓ \sum_i a_i+\sum_i b_{\pi(i)}=\ell ∑ i a i + ∑ i b π ( i ) = ℓ , so α = ℓ \alpha=\ell α = ℓ by Lemma 2.7(a), and τ = n − α = ( N − 1 ) ℓ \tau=n-\alpha=(N-1)\ell τ = n − α = ( N − 1 ) ℓ .
We now recall the main result of this article, stated in the introduction.
Theorem 0.1. Let Γ = ( G , σ ) \Gamma=(G,\sigma) Γ = ( G , σ ) be a signed graph. Then E ( Γ ) ≥ 2 τ ( G ) \mathcal{E}(\Gamma)\ge2\tau(G) E ( Γ ) ≥ 2 τ ( G ) . Equality holds if and only if every connected component of Γ \Gamma Γ is switching equivalent to an additive rook graph Rook N ( a , b ) \operatorname{Rook}_N(a,b) Rook N ( a , b ) .
The inequality is proved in § 4 , and the characterization of equality in § 5 .
Proof of E ( Γ ) ≥ 2 τ ( G ) \mathcal{E}(\Gamma)\ge2\tau(G) E ( Γ ) ≥ 2 τ ( G )
In this section we prove the inequality part of Theorem 0.1. We first collect some results from linear algebra and matrix theory that are needed in the proof. Few parts of the argument follow/adapt the approach of Kumar and Pragada [25 ] for unsigned graphs. For the sake of completeness, we include all the details. Our main novel contribution, the characterization of equality, is established in the later sections 4.
Lemma 3.1. Let M M M be a real symmetric n × n n \times n n × n matrix. If M = X − Y M = X - Y M = X − Y with X , Y ⪰ 0 X, Y \succeq0 X , Y ⪰ 0 , then
E ( M ) ≤ tr X + tr Y . \mathcal{E}(M) \le\operatorname{tr} X + \operatorname{tr} Y. E ( M ) ≤ tr X + tr Y .
Proof. By (F1), let u 1 , … , u n u_1,\ldots,u_n u 1 , … , u n be an orthonormal basis of eigenvectors of M M M with M u k = λ k u k M u_k = \lambda_k u_k M u k = λ k u k . Let U U U be the n × n n \times n n × n matrix with columns u 1 , … , u n u_1,\ldots,u_n u 1 , … , u n . The ( j , k ) (j,k) ( j , k ) -th entry of U T U U^{\mathsf{T}}U U T U is u j T u k u_j^{\mathsf{T}}u_k u j T u k , which equals 1 if j = k j=k j = k and 0 otherwise. Hence U T U = I U^{\mathsf{T}}U=I U T U = I and therefore, for any n × n n \times n n × n matrix Z Z Z ,
tr ( Z ) = tr ( Z I ) = tr ( Z U T U ) = tr ( U T Z U ) = ∑ k = 1 n u k T Z u k . \operatorname{tr}(Z) = \operatorname{tr}(ZI) = \operatorname{tr}(ZU^{\mathsf{T}}U) = \operatorname{tr}(U^{\mathsf{T}}ZU) = \sum_{k=1}^{n} u_k^{\mathsf{T}}Zu_k. tr ( Z ) = tr ( Z I ) = tr ( Z U T U ) = tr ( U T Z U ) = k = 1 ∑ n u k T Z u k .
Therefore, tr X = ∑ k = 1 n u k T X u k \operatorname{tr} X = \sum_{k=1}^{n}u_k^{\mathsf{T}}Xu_k tr X = ∑ k = 1 n u k T X u k and tr Y = ∑ k = 1 n u k T Y u k \operatorname{tr} Y = \sum_{k=1}^{n}u_k^{\mathsf{T}}Yu_k tr Y = ∑ k = 1 n u k T Y u k . As X ⪰ 0 X \succeq0 X ⪰ 0 and Y ⪰ 0 Y \succeq0 Y ⪰ 0 , every term u k T X u k u_k^{\mathsf{T}}Xu_k u k T X u k and u k T Y u k u_k^{\mathsf{T}}Yu_k u k T Y u k is nonnegative. Hence
tr X ≥ ∑ λ k > 0 u k T X u k ≥ ∑ λ k > 0 u k T ( X − Y ) u k = ∑ λ k > 0 u k T M u k = ∑ λ k > 0 λ k , \operatorname{tr} X \ge\sum_{\lambda_k>0} u_k^{\mathsf{T}}Xu_k \ge\sum_{\lambda_k>0}u_k^{\mathsf{T}}(X-Y)u_k = \sum_{\lambda_k>0}u_k^{\mathsf{T}}Mu_k = \sum_{\lambda_k>0}\lambda_k, tr X ≥ λ k > 0 ∑ u k T X u k ≥ λ k > 0 ∑ u k T ( X − Y ) u k = λ k > 0 ∑ u k T M u k = λ k > 0 ∑ λ k ,
and similarly
tr Y ≥ ∑ λ k < 0 u k T Y u k ≥ ∑ λ k < 0 u k T ( Y − X ) u k = − ∑ λ k < 0 λ k = ∑ λ k < 0 ∣ λ k ∣ . \operatorname{tr} Y \ge\sum_{\lambda_k<0}u_k^{\mathsf{T}}Yu_k \ge\sum_{\lambda_k<0}u_k^{\mathsf{T}}(Y-X)u_k = -\sum_{\lambda_k<0}\lambda_k = \sum_{\lambda_k<0}|\lambda_k|. tr Y ≥ λ k < 0 ∑ u k T Y u k ≥ λ k < 0 ∑ u k T ( Y − X ) u k = − λ k < 0 ∑ λ k = λ k < 0 ∑ ∣ λ k ∣.
Adding the two inequalities gives tr X + tr Y ≥ ∑ k ∣ λ k ∣ = E ( M ) \operatorname{tr} X+\operatorname{tr} Y\ge\sum_k|\lambda_k|=\mathcal{E}(M) tr X + tr Y ≥ ∑ k ∣ λ k ∣ = E ( M ) .
To simplify notation, we fix the following for the rest of the article. For a signed graph Γ = ( G , σ ) \Gamma=(G,\sigma) Γ = ( G , σ ) , let A = A ( Γ ) A=A(\Gamma) A = A ( Γ ) , and let P = A + P=A_+ P = A + , Q = A − Q=A_- Q = A − and B = ∣ A ∣ = P + Q B=|A|=P+Q B = ∣ A ∣ = P + Q be as in (F2). By (F3), we also fix Gram representations P u v = ⟨ p u , p v ⟩ P_{uv}=\langle p_u,p_v\rangle P uv = ⟨ p u , p v ⟩ and Q u v = ⟨ q u , q v ⟩ Q_{uv}=\langle q_u,q_v\rangle Q uv = ⟨ q u , q v ⟩ for all vertices u , v u,v u , v .
Lemma 3.2. Let Γ \Gamma Γ be a signed graph, and let A A A , P P P , Q Q Q , B B B and the Gram vectors p v , q v p_v,q_v p v , q v be as fixed above. Then the following hold.
(1) A = P − Q A=P-Q A = P − Q , B = P + Q B=P+Q B = P + Q , P Q = Q P = 0 PQ=QP=0 P Q = QP = 0 , B 2 = A 2 B^2=A^2 B 2 = A 2 and tr B = E ( Γ ) \operatorname{tr}B=\mathcal{E}(\Gamma) tr B = E ( Γ ) .
(2) P v v = Q v v = 1 2 B v v P_{vv}=Q_{vv}=\frac{1}{2}B_{vv} P v v = Q v v = 2 1 B v v for every vertex v v v . If u ≠ v u\ne v u = v are non-adjacent, then P u v = Q u v = 1 2 B u v P_{uv}=Q_{uv}=\frac{1}{2}B_{uv} P uv = Q uv = 2 1 B uv .
(3) ( B 2 ) v v = d v (B^2)_{vv}=d_v ( B 2 ) v v = d v for every vertex v v v .
(4) Let D = diag ( δ v ) D=\operatorname{diag}(\delta_v) D = diag ( δ v ) with δ v ∈ { 1 , − 1 } \delta_v\in\{1,-1\} δ v ∈ { 1 , − 1 } , and let Γ D \Gamma^D Γ D be the signed graph with A ( Γ D ) = D A D A(\Gamma^D)=DAD A ( Γ D ) = D A D . Then A ( Γ D ) ± = D A ± D A(\Gamma^D)_\pm=DA_\pm D A ( Γ D ) ± = D A ± D and ∣ A ( Γ D ) ∣ = D ∣ A ∣ D |A(\Gamma^D)|=D|A|D ∣ A ( Γ D ) ∣ = D ∣ A ∣ D . Consequently, the vectors δ v p v \delta_vp_v δ v p v and δ v q v \delta_vq_v δ v q v form Gram representations of A ( Γ D ) + A(\Gamma^D)_+ A ( Γ D ) + and A ( Γ D ) − A(\Gamma^D)_- A ( Γ D ) − , respectively.
Proof. (1) All assertions except the last follow from (F2), and tr B = E ( Γ ) \operatorname{tr}B=\mathcal{E}(\Gamma) tr B = E ( Γ ) is the formula for the energy in (F2). Since P Q = Q P = 0 PQ=QP=0 P Q = QP = 0 , we get B 2 = ( P + Q ) 2 = P 2 + Q 2 = ( P − Q ) 2 = A 2 B^2=(P+Q)^2=P^2+Q^2=(P-Q)^2=A^2 B 2 = ( P + Q ) 2 = P 2 + Q 2 = ( P − Q ) 2 = A 2 .
(2) By (1), P = 1 2 ( B + A ) P=\frac{1}{2}(B+A) P = 2 1 ( B + A ) and Q = 1 2 ( B − A ) Q=\frac{1}{2}(B-A) Q = 2 1 ( B − A ) . Since A v v = 0 A_{vv}=0 A v v = 0 , this gives P v v = Q v v = 1 2 B v v P_{vv}=Q_{vv}=\frac{1}{2}B_{vv} P v v = Q v v = 2 1 B v v . If u ≠ v u\ne v u = v are non-adjacent, then A u v = 0 A_{uv}=0 A uv = 0 , and in the same way P u v = Q u v = 1 2 B u v P_{uv}=Q_{uv}=\frac{1}{2}B_{uv} P uv = Q uv = 2 1 B uv . (3) By (1), ( B 2 ) v v = ( A 2 ) v v = ∑ u A u v 2 (B^2)_{vv} = (A^2)_{vv} = \sum_u A_{uv}^2 ( B 2 ) v v = ( A 2 ) v v = ∑ u A uv 2 . Each neighbour u u u of v v v contributes σ ( u v ) 2 = 1 \sigma(uv)^2 = 1 σ ( uv ) 2 = 1 , and every other vertex contributes 0. Hence ( B 2 ) v v = d v (B^2)_{vv} = d_v ( B 2 ) v v = d v .
(4) Write A = ∑ k λ k u k u k T A = \sum_k \lambda_k u_k u_k^{\mathsf T} A = ∑ k λ k u k u k T as in (F1). Then D A D = ∑ k λ k ( D u k ) ( D u k ) T DAD = \sum_k \lambda_k (Du_k)(Du_k)^{\mathsf T} D A D = ∑ k λ k ( D u k ) ( D u k ) T , and the vectors D u k Du_k D u k are again orthonormal because D T D = I D^{\mathsf T}D = I D T D = I . So this is a spectral decomposition of D A D DAD D A D with the same eigenvalues, and therefore
A ( Γ D ) + = ∑ λ k > 0 λ k D u k u k T D = D P D , A ( Γ D ) − = D Q D , ∣ A ( Γ D ) ∣ = D B D . A(\Gamma^D)_+ = \sum_{\lambda_k>0} \lambda_k Du_k u_k^{\mathsf T}D = DPD,\qquad A(\Gamma^D)_- = DQD,\qquad|A(\Gamma^D)| = DBD. A ( Γ D ) + = λ k > 0 ∑ λ k D u k u k T D = D P D , A ( Γ D ) − = D Q D , ∣ A ( Γ D ) ∣ = D B D .
Finally, ( D P D ) u v = δ u δ v P u v = ⟨ δ u p u , δ v p v ⟩ (DPD)_{uv} = \delta_u\delta_vP_{uv} = \langle\delta_u p_u, \delta_v p_v\rangle ( D P D ) uv = δ u δ v P uv = ⟨ δ u p u , δ v p v ⟩ , and similarly ( D Q D ) u v = ⟨ δ u q u , δ v q v ⟩ (DQD)_{uv} = \langle\delta_u q_u, \delta_v q_v\rangle ( D Q D ) uv = ⟨ δ u q u , δ v q v ⟩ .
The number B v v = ∣ A ∣ v v B_{vv} = |A|_{vv} B v v = ∣ A ∣ v v is the vertex energy E Γ ( v ) \mathcal{E}_{\Gamma}(v) E Γ ( v ) of [6 ] ; note that ∑ v E Γ ( v ) = E ( Γ ) \sum_v \mathcal{E}_{\Gamma}(v) = \mathcal{E}(\Gamma) ∑ v E Γ ( v ) = E ( Γ ) .
Lemma 3.3. If u v ∈ E uv \in E uv ∈ E , then B u u B v v ≥ ( 1 + ∣ B u v ∣ ) 2 B_{uu}B_{vv} \ge(1 + |B_{uv}|)^2 B uu B v v ≥ ( 1 + ∣ B uv ∣ ) 2 . In particular B v v > 0 B_{vv} > 0 B v v > 0 for every non-isolated vertex v v v .
Proof. Let x = B u u x = B_{uu} x = B uu , y = B v v y = B_{vv} y = B v v , z = B u v z = B_{uv} z = B uv and ς = A u v ∈ { ± 1 } \varsigma= A_{uv} \in\{\pm1\} ς = A uv ∈ { ± 1 } . The matrices 2 P = B + A 2P = B + A 2 P = B + A and 2 Q = B − A 2Q = B - A 2 Q = B − A are PSD, and their principal submatrices on { u , v } \{u,v\} { u , v } are
( x z + ς z + ς y ) , ( x z − ς z − ς y ) . \begin{pmatrix} x & z+\varsigma\\ z+\varsigma& y \end{pmatrix},\qquad
\begin{pmatrix} x & z-\varsigma\\ z-\varsigma& y \end{pmatrix}. ( x z + ς z + ς y ) , ( x z − ς z − ς y ) . By (P2), x y ≥ ( z ± ς ) 2 xy \ge(z\pm\varsigma)^2 x y ≥ ( z ± ς ) 2 . One of z + ς z+\varsigma z + ς and z − ς z-\varsigma z − ς has absolute value 1 + ∣ z ∣ 1+|z| 1 + ∣ z ∣ . Hence x y ≥ ( 1 + ∣ z ∣ ) 2 ≥ 1 xy \ge(1+|z|)^2 \ge1 x y ≥ ( 1 + ∣ z ∣ ) 2 ≥ 1 , and since x , y ≥ 0 x,y \ge0 x , y ≥ 0 we get x , y > 0 x,y > 0 x , y > 0 .
Lemma 3.4. Let v v v be non-isolated and S ( v ) : = V ∖ N [ v ] S(v) := V \setminus N[v] S ( v ) := V ∖ N [ v ] . Then
E ( Γ − N [ v ] ) ≤ ∑ u ∈ S ( v ) B u u − 1 B v v ∑ u ∈ S ( v ) B u v 2 . \mathcal{E}(\Gamma- N[v]) \le\sum_{u\in S(v)} B_{uu} - \frac{1}{B_{vv}}\sum_{u\in S(v)} B_{uv}^2. E ( Γ − N [ v ]) ≤ u ∈ S ( v ) ∑ B uu − B v v 1 u ∈ S ( v ) ∑ B uv 2 . Proof. Put β = P v v = Q v v = 1 2 B v v > 0 \beta= P_{vv} = Q_{vv} = \frac{1}{2}B_{vv} > 0 β = P v v = Q v v = 2 1 B v v > 0 (Lemmas 3.2 and 3.5 ). For u ∈ S ( v ) u \in S(v) u ∈ S ( v ) define the projections
p u ′ = p u − P u v β p v , q u ′ = q u − Q u v β q v . p'_u = p_u - \frac{P_{uv}}{\beta}p_v,\qquad q'_u = q_u - \frac{Q_{uv}}{\beta}q_v. p u ′ = p u − β P uv p v , q u ′ = q u − β Q uv q v . Since ∥ p v ∥ 2 = β \|p_v\|^2 = \beta ∥ p v ∥ 2 = β , for u , w ∈ S ( v ) u,w \in S(v) u , w ∈ S ( v ) we have ⟨ p u ′ , p w ′ ⟩ = P u w − P u v P w v / β \langle p'_u,p'_w\rangle= P_{uw} - P_{uv}P_{wv}/\beta ⟨ p u ′ , p w ′ ⟩ = P u w − P uv P w v / β , and similarly for q ′ q' q ′ . As P u v = Q u v P_{uv} = Q_{uv} P uv = Q uv and P w v = Q w v P_{wv} = Q_{wv} P w v = Q w v by Lemma 3.2 (2),
⟨ p u ′ , p w ′ ⟩ − ⟨ q u ′ , q w ′ ⟩ = P u w − Q u w = A u w . \langle p'_u,p'_w\rangle- \langle q'_u,q'_w\rangle= P_{uw} - Q_{uw} = A_{uw}. ⟨ p u ′ , p w ′ ⟩ − ⟨ q u ′ , q w ′ ⟩ = P u w − Q u w = A u w . So the Gram matrices X X X of ( p u ′ ) (p'_u) ( p u ′ ) and Y Y Y of ( q u ′ ) (q'_u) ( q u ′ ) are PSD with X − Y = A ( Γ − N [ v ] ) X - Y = A(\Gamma- N[v]) X − Y = A ( Γ − N [ v ]) . By Lemma 3.1 ,
E ( Γ − N [ v ] ) ≤ ∑ u ∈ S ( v ) ( P u u + Q u u − P u v 2 + Q u v 2 β ) = ∑ u ∈ S ( v ) ( B u u − B u v 2 B v v ) . \mathcal{E}(\Gamma- N[v]) \le\sum_{u\in S(v)}\left(P_{uu}+Q_{uu}-\frac{P_{uv}^2+Q_{uv}^2}{\beta}\right) = \sum_{u\in S(v)}\left(B_{uu}-\frac{B_{uv}^2}{B_{vv}}\right). E ( Γ − N [ v ]) ≤ u ∈ S ( v ) ∑ ( P uu + Q uu − β P uv 2 + Q uv 2 ) = u ∈ S ( v ) ∑ ( B uu − B v v B uv 2 ) . If S ( v ) = ∅ S(v) = \varnothing S ( v ) = ∅ , both sides are 0.
Lemma 3.5. If u v ∈ E uv \in E uv ∈ E , then B u u B v v ≥ ( 1 + ∣ B u v ∣ ) 2 B_{uu}B_{vv} \ge(1 + |B_{uv}|)^2 B uu B v v ≥ ( 1 + ∣ B uv ∣ ) 2 . In particular, B v v > 0 B_{vv} > 0 B v v > 0 for every non-isolated vertex v v v .
Proof. Let x = B u u x = B_{uu} x = B uu , y = B v v y = B_{vv} y = B v v , z = B u v z = B_{uv} z = B uv and s = A u v ∈ { 1 , − 1 } s = A_{uv} \in\{1,-1\} s = A uv ∈ { 1 , − 1 } . By Lemma 3.2 (1), the matrices 2 P = B + A 2P = B + A 2 P = B + A and 2 Q = B − A 2Q = B - A 2 Q = B − A are positive semidefinite. Since A u u = A v v = 0 A_{uu} = A_{vv} = 0 A uu = A v v = 0 , their principal submatrices on { u , v } \{u,v\} { u , v } are
( x z + s z + s y ) and ( x z − s z − s y ) . \begin{pmatrix} x & z+s \\ z+s & y \end{pmatrix}
\qquad\text{and}\qquad
\begin{pmatrix} x & z-s \\ z-s & y \end{pmatrix}. ( x z + s z + s y ) and ( x z − s z − s y ) .
Both have nonnegative determinant, so x y ≥ ( z + s ) 2 xy \ge(z+s)^2 x y ≥ ( z + s ) 2 and x y ≥ ( z − s ) 2 xy \ge(z-s)^2 x y ≥ ( z − s ) 2 . As s = ± 1 s = \pm1 s = ± 1 , one of the numbers z + s z+s z + s and z − s z-s z − s has absolute value 1 + ∣ z ∣ 1+|z| 1 + ∣ z ∣ . Hence x y ≥ ( 1 + ∣ z ∣ ) 2 ≥ 1 xy \ge(1+|z|)^2 \ge1 x y ≥ ( 1 + ∣ z ∣ ) 2 ≥ 1 . Since x x x and y y y are diagonal entries of B ⪰ 0 B \succeq0 B ⪰ 0 , they are nonnegative, and therefore x , y > 0 x,y > 0 x , y > 0 .
Lemma 3.6. Let v v v be a non-isolated vertex and put S ( v ) = V ∖ N [ v ] S(v) = V \setminus N[v] S ( v ) = V ∖ N [ v ] . Then
E ( Γ − N [ v ] ) ≤ ∑ u ∈ S ( v ) B u u − 1 B v v ∑ u ∈ S ( v ) B u v 2 . \mathcal{E}(\Gamma-N[v]) \le\sum_{u\in S(v)} B_{uu} - \frac{1}{B_{vv}}\sum_{u\in S(v)} B_{uv}^{2}. E ( Γ − N [ v ]) ≤ u ∈ S ( v ) ∑ B uu − B v v 1 u ∈ S ( v ) ∑ B uv 2 .
Proof. If S ( v ) = ∅ S(v) = \varnothing S ( v ) = ∅ , both sides are 0. Otherwise, let β = P v v = Q v v = 1 2 B v v \beta= P_{vv} = Q_{vv} = \frac{1}{2}B_{vv} β = P v v = Q v v = 2 1 B v v , which is positive by Lemmas 3.2 (2) and 3.5. For u ∈ S ( v ) u \in S(v) u ∈ S ( v ) , let p u ′ p'_u p u ′ and q u ′ q'_u q u ′ be the components of p u p_u p u and q u q_u q u orthogonal to p v p_v p v and q v q_v q v , respectively:
p u ′ = p u − P u v β p v , q u ′ = q u − Q u v β q v . p'_u = p_u - \frac{P_{uv}}{\beta}p_v,\qquad q'_u = q_u - \frac{Q_{uv}}{\beta}q_v. p u ′ = p u − β P uv p v , q u ′ = q u − β Q uv q v .
Since ∥ p v ∥ 2 = ∥ q v ∥ 2 = β \lVert p_v\rVert^2 = \lVert q_v\rVert^2 = \beta ∥ p v ∥ 2 = ∥ q v ∥ 2 = β , for all u , w ∈ S ( v ) u,w \in S(v) u , w ∈ S ( v ) we get
⟨ p u ′ , p w ′ ⟩ = P u w − P u v P w v β , ⟨ q u ′ , q w ′ ⟩ = Q u w − Q u v Q w v β . \langle p'_u,p'_w\rangle= P_{uw} - \frac{P_{uv}P_{wv}}{\beta},\qquad\langle q'_u,q'_w\rangle= Q_{uw} - \frac{Q_{uv}Q_{wv}}{\beta}. ⟨ p u ′ , p w ′ ⟩ = P u w − β P uv P w v , ⟨ q u ′ , q w ′ ⟩ = Q u w − β Q uv Q w v .
The vertices u , w ∈ S ( v ) u,w \in S(v) u , w ∈ S ( v ) are not adjacent to v v v , so P u v = Q u v P_{uv} = Q_{uv} P uv = Q uv and P w v = Q w v P_{wv} = Q_{wv} P w v = Q w v by Lemma 3.2 (2). Hence ⟨ p u ′ , p w ′ ⟩ − ⟨ q u ′ , q w ′ ⟩ = P u w − Q u w = A u w \langle p'_u,p'_w\rangle- \langle q'_u,q'_w\rangle= P_{uw}-Q_{uw}=A_{uw} ⟨ p u ′ , p w ′ ⟩ − ⟨ q u ′ , q w ′ ⟩ = P u w − Q u w = A u w . Thus the Gram matrices X X X of ( p u ′ ) (p'_u) ( p u ′ ) and Y Y Y of ( q u ′ ) (q'_u) ( q u ′ ) are positive semidefinite and satisfy X − Y = A ( Γ − N [ v ] ) X-Y=A(\Gamma-N[v]) X − Y = A ( Γ − N [ v ]) . By Lemma 3.1 ,
E ( Γ − N [ v ] ) ≤ tr X + tr Y = ∑ u ∈ S ( v ) ( P u u + Q u u − P u v 2 + Q u v 2 β ) = ∑ u ∈ S ( v ) ( B u u − B u v 2 B v v ) . \mathcal{E}(\Gamma-N[v]) \le\operatorname{tr}X+\operatorname{tr}Y
= \sum_{u\in S(v)}\left(P_{uu}+Q_{uu}-\frac{P_{uv}^{2}+Q_{uv}^{2}}{\beta}\right)
= \sum_{u\in S(v)}\left(B_{uu}-\frac{B_{uv}^{2}}{B_{vv}}\right). E ( Γ − N [ v ]) ≤ tr X + tr Y = u ∈ S ( v ) ∑ ( P uu + Q uu − β P uv 2 + Q uv 2 ) = u ∈ S ( v ) ∑ ( B uu − B v v B uv 2 ) .
where the last step uses P u v = Q u v = 1 2 B u v P_{uv}=Q_{uv}=\frac{1}{2}B_{uv} P uv = Q uv = 2 1 B uv and P u u + Q u u = B u u P_{uu}+Q_{uu}=B_{uu} P uu + Q uu = B uu .
Lemma 3.7. Let Γ \Gamma Γ be a signed graph with no isolated vertices. For vertices u , v u,v u , v write x v = B v v x_v=B_{vv} x v = B v v and z u v = B u v z_{uv}=B_{uv} z uv = B uv . By Lemma 3.5 , x v > 0 x_v>0 x v > 0 for every v v v . For an edge u v uv uv put
F u v = ( x u − 1 ) 2 − z u v 2 x u + ( x v − 1 ) 2 − z u v 2 x v . F_{uv}=\frac{(x_u-1)^2-z_{uv}^{2}}{x_u}+\frac{(x_v-1)^2-z_{uv}^{2}}{x_v}. F uv = x u ( x u − 1 ) 2 − z uv 2 + x v ( x v − 1 ) 2 − z uv 2 . Then
∑ v E ( Γ − N [ v ] ) ≤ n E ( Γ ) − 4 m − ∑ u v ∈ E F u v . \sum_v \mathcal{E}(\Gamma-N[v]) \le n\mathcal{E}(\Gamma)-4m-\sum_{uv\in E}F_{uv}. v ∑ E ( Γ − N [ v ]) ≤ n E ( Γ ) − 4 m − uv ∈ E ∑ F uv .
Proof. Summing Lemma 3.6 over all vertices v v v gives ∑ v E ( Γ − N [ v ] ) ≤ T 1 − T 2 \sum_v \mathcal{E}(\Gamma-N[v])\le T_1-T_2 ∑ v E ( Γ − N [ v ]) ≤ T 1 − T 2 , where
T 1 = ∑ v ∑ u ∈ S ( v ) x u and T 2 = ∑ v 1 x v ∑ u ∈ S ( v ) z u v 2 . T_1=\sum_v\sum_{u\in S(v)}x_u
\qquad\text{and}\qquad
T_2=\sum_v\frac{1}{x_v}\sum_{u\in S(v)}z_{uv}^2. T 1 = v ∑ u ∈ S ( v ) ∑ x u and T 2 = v ∑ x v 1 u ∈ S ( v ) ∑ z uv 2 .
For a fixed vertex u u u , we have u ∈ S ( v ) u\in S(v) u ∈ S ( v ) for exactly n − 1 − d u n-1-d_u n − 1 − d u vertices v v v . Since ∑ u x u = tr B = E ( Γ ) \sum_u x_u=\operatorname{tr}B=\mathcal{E}(\Gamma) ∑ u x u = tr B = E ( Γ ) , this gives
T 1 = ∑ u ( n − 1 − d u ) x u = n E ( Γ ) − ∑ u ( d u + 1 ) x u . T_1=\sum_u(n-1-d_u)x_u=n\mathcal{E}(\Gamma)-\sum_u(d_u+1)x_u. T 1 = u ∑ ( n − 1 − d u ) x u = n E ( Γ ) − u ∑ ( d u + 1 ) x u .
By Lemma 3.2 (3), splitting the sum according to whether u = v u=v u = v , u ∈ N ( v ) u\in N(v) u ∈ N ( v ) or u ∈ S ( v ) u\in S(v) u ∈ S ( v ) , we get
d v = ∑ u B u v 2 = x v 2 + ∑ u ∼ v z u v 2 + ∑ u ∈ S ( v ) z u v 2 . d_v=\sum_u B_{uv}^2=x_v^2+\sum_{u\sim v}z_{uv}^2+\sum_{u\in S(v)}z_{uv}^2. d v = u ∑ B uv 2 = x v 2 + u ∼ v ∑ z uv 2 + u ∈ S ( v ) ∑ z uv 2 .
Therefore
T 2 = ∑ v ( d v x v − x v − ∑ u ∼ v z u v 2 x v ) . T_2=\sum_v\left(\frac{d_v}{x_v}-x_v-\sum_{u\sim v}\frac{z_{uv}^2}{x_v}\right). T 2 = v ∑ ( x v d v − x v − u ∼ v ∑ x v z uv 2 ) .
The terms ± x v \pm x_v ± x v cancel in T 1 − T 2 T_1-T_2 T 1 − T 2 , and
T 1 − T 2 = n E ( Γ ) − ∑ v ( d v ( x v + 1 x v ) − ∑ u ∼ v z u v 2 x v ) . T_1-T_2=n\mathcal{E}(\Gamma)-\sum_v\left(d_v\left(x_v+\frac{1}{x_v}\right)-\sum_{u\sim v}\frac{z_{uv}^2}{x_v}\right). T 1 − T 2 = n E ( Γ ) − v ∑ ( d v ( x v + x v 1 ) − u ∼ v ∑ x v z uv 2 ) .
Each edge u v uv uv is counted once at u u u and once at v v v . Hence, with h ( x , z ) = x + 1 x − z 2 x h(x,z)=x+\frac{1}{x}-\frac{z^2}{x} h ( x , z ) = x + x 1 − x z 2 ,
T 1 − T 2 = n E ( Γ ) − ∑ u v ∈ E ( h ( x u , z u v ) + h ( x v , z u v ) ) . T_1-T_2=n\mathcal{E}(\Gamma)-\sum_{uv\in E}\left(h(x_u,z_{uv})+h(x_v,z_{uv})\right). T 1 − T 2 = n E ( Γ ) − uv ∈ E ∑ ( h ( x u , z uv ) + h ( x v , z uv ) ) .
Finally, h ( x , z ) − 2 = ( x − 1 ) 2 − z 2 x h(x,z)-2=\frac{(x-1)^2-z^2}{x} h ( x , z ) − 2 = x ( x − 1 ) 2 − z 2 , so the last sum equals 4 m + ∑ u v ∈ E F u v 4m+\sum_{uv\in E}F_{uv} 4 m + ∑ uv ∈ E F uv .
Lemma 3.8. For every edge u v uv uv we have F u v ≥ 0 F_{uv}\ge0 F uv ≥ 0 , with equality if and only if x u = x v = 1 + ∣ z u v ∣ x_u=x_v=1+|z_{uv}| x u = x v = 1 + ∣ z uv ∣ .
Proof. Write x = x u x=x_u x = x u , y = x v y=x_v y = x v and z = z u v z=z_{uv} z = z uv . Since ( x − 1 ) 2 − z 2 x = x − 2 + 1 − z 2 x \frac{(x-1)^2-z^2}{x}=x-2+\frac{1-z^2}{x} x ( x − 1 ) 2 − z 2 = x − 2 + x 1 − z 2 , a direct computation gives
F u v = ( x + y ) + ( 1 − z 2 ) ( 1 x + 1 y ) − 4 = ( x + y ) ( x y + 1 − z 2 ) x y − 4. F_{uv}=(x+y)+(1-z^2)\left(\frac{1}{x}+\frac{1}{y}\right)-4=\frac{(x+y)(xy+1-z^2)}{xy}-4. F uv = ( x + y ) + ( 1 − z 2 ) ( x 1 + y 1 ) − 4 = x y ( x + y ) ( x y + 1 − z 2 ) − 4.
By Lemma 3.5 , x y ≥ ( 1 + ∣ z ∣ ) 2 xy\ge(1+|z|)^2 x y ≥ ( 1 + ∣ z ∣ ) 2 , that is, ∣ z ∣ ≤ x y − 1 |z|\le\sqrt{xy}-1 ∣ z ∣ ≤ x y − 1 . Hence
x y + 1 − z 2 ≥ x y + 1 − ( x y − 1 ) 2 = 2 x y > 0. xy+1-z^2\ge xy+1-(\sqrt{xy}-1)^2=2\sqrt{xy}>0. x y + 1 − z 2 ≥ x y + 1 − ( x y − 1 ) 2 = 2 x y > 0.
Together with x + y ≥ 2 x y x+y\ge2\sqrt{xy} x + y ≥ 2 x y , this gives ( x + y ) ( x y + 1 − z 2 ) ≥ 4 x y (x+y)(xy+1-z^2)\ge4xy ( x + y ) ( x y + 1 − z 2 ) ≥ 4 x y , and so F u v ≥ 0 F_{uv}\ge0 F uv ≥ 0 . Since both factors are positive, equality holds if and only if x + y = 2 x y x+y=2\sqrt{xy} x + y = 2 x y and ∣ z ∣ = x y − 1 |z|=\sqrt{xy}-1 ∣ z ∣ = x y − 1 . This means x = y x=y x = y and ∣ z ∣ = x − 1 |z|=x-1 ∣ z ∣ = x − 1 , that is, x = y = 1 + ∣ z ∣ x=y=1+|z| x = y = 1 + ∣ z ∣ .
We can now prove the inequality in Theorem 0.1.
Theorem 3.9. Let Γ \Gamma Γ be a signed graph with vertex cover number τ ( Γ ) \tau(\Gamma) τ ( Γ ) . Then E ( Γ ) ≥ 2 τ ( Γ ) \mathcal{E}(\Gamma)\ge2\tau(\Gamma) E ( Γ ) ≥ 2 τ ( Γ ) .
Proof. We use induction on the number n n n of vertices. For n = 0 n=0 n = 0 both sides are 0 0 0 . Let n ≥ 1 n \ge1 n ≥ 1 , and write α = α ( Γ ) \alpha=\alpha(\Gamma) α = α ( Γ ) and τ = τ ( Γ ) \tau=\tau(\Gamma) τ = τ ( Γ ) .
Case 1: Γ \Gamma Γ has an isolated vertex v v v .
Then A ( Γ ) = A ( Γ − v ) ⊕ ( 0 ) A(\Gamma)=A(\Gamma-v)\oplus(0) A ( Γ ) = A ( Γ − v ) ⊕ ( 0 ) , so E ( Γ ) = E ( Γ − v ) \mathcal{E}(\Gamma)=\mathcal{E}(\Gamma-v) E ( Γ ) = E ( Γ − v ) . Moreover α = α ( Γ − v ) + 1 \alpha=\alpha(\Gamma-v)+1 α = α ( Γ − v ) + 1 , and hence τ = τ ( Γ − v ) \tau=\tau(\Gamma-v) τ = τ ( Γ − v ) . The claim follows from the induction hypothesis applied to Γ − v \Gamma-v Γ − v .
Case 2: Γ \Gamma Γ has no isolated vertex.
Let v v v be a vertex. Adding v v v to an independent set of Γ − N [ v ] \Gamma-N[v] Γ − N [ v ] gives an independent set of Γ \Gamma Γ , so α ( Γ − N [ v ] ) ≤ α − 1 \alpha(\Gamma-N[v])\le\alpha-1 α ( Γ − N [ v ]) ≤ α − 1 . Since Γ − N [ v ] \Gamma-N[v] Γ − N [ v ] has n − 1 − d v n-1-d_v n − 1 − d v vertices,
τ ( Γ − N [ v ] ) = ( n − 1 − d v ) − α ( Γ − N [ v ] ) ≥ τ − d v . \tau(\Gamma-N[v])=(n-1-d_v)-\alpha(\Gamma-N[v])\ge\tau-d_v. τ ( Γ − N [ v ]) = ( n − 1 − d v ) − α ( Γ − N [ v ]) ≥ τ − d v .
By the induction hypothesis, E ( Γ − N [ v ] ) ≥ 2 τ − 2 d v \mathcal{E}(\Gamma-N[v])\ge2\tau-2d_v E ( Γ − N [ v ]) ≥ 2 τ − 2 d v . Summing over all vertices v v v and using ∑ v d v = 2 m \sum_v d_v=2m ∑ v d v = 2 m , we obtain
∑ v E ( Γ − N [ v ] ) ≥ 2 n τ − 4 m . (4) \sum_v \mathcal{E}(\Gamma-N[v])\ge2n\tau-4m. \tag*{(4)} v ∑ E ( Γ − N [ v ]) ≥ 2 n τ − 4 m . (4)
On the other hand, Lemmas 3.7 and 3.8 give ∑ v E ( Γ − N [ v ] ) ≤ n E ( Γ ) − 4 m \sum_v\mathcal{E}(\Gamma-N[v])\le n\mathcal{E}(\Gamma)-4m ∑ v E ( Γ − N [ v ]) ≤ n E ( Γ ) − 4 m . Combining the two inequalities yields n E ( Γ ) ≥ 2 n τ n\mathcal{E}(\Gamma)\ge2n\tau n E ( Γ ) ≥ 2 n τ , and the result follows since n ≥ 1 n\ge1 n ≥ 1 .
Corollary 3.10. Let Γ 1 , … , Γ k \Gamma_1,\ldots,\Gamma_k Γ 1 , … , Γ k be the connected components of Γ \Gamma Γ . Then E ( Γ ) = 2 τ ( Γ ) \mathcal{E}(\Gamma)=2\tau(\Gamma) E ( Γ ) = 2 τ ( Γ ) if and only if E ( Γ i ) = 2 τ ( Γ i ) \mathcal{E}(\Gamma_i)=2\tau(\Gamma_i) E ( Γ i ) = 2 τ ( Γ i ) for every i i i .
Proof. Since A ( Γ ) A(\Gamma) A ( Γ ) is block diagonal, E ( Γ ) = ∑ i E ( Γ i ) \mathcal{E}(\Gamma)=\sum_i\mathcal{E}(\Gamma_i) E ( Γ ) = ∑ i E ( Γ i ) . An independent set of Γ \Gamma Γ is a union of independent sets of the components, so α ( Γ ) = ∑ i α ( Γ i ) \alpha(\Gamma)=\sum_i\alpha(\Gamma_i) α ( Γ ) = ∑ i α ( Γ i ) and τ ( Γ ) = ∑ i τ ( Γ i ) \tau(\Gamma)=\sum_i\tau(\Gamma_i) τ ( Γ ) = ∑ i τ ( Γ i ) . Hence E ( Γ ) − 2 τ ( Γ ) = ∑ i ( E ( Γ i ) − 2 τ ( Γ i ) ) \mathcal{E}(\Gamma)-2\tau(\Gamma)=\sum_i(\mathcal{E}(\Gamma_i)-2\tau(\Gamma_i)) E ( Γ ) − 2 τ ( Γ ) = ∑ i ( E ( Γ i ) − 2 τ ( Γ i )) . By Theorem 3.9 every term of this sum is nonnegative. So the sum is zero if and only if every term is zero.
Characterization of the equality case
In this section we first show that every additive rook graph attains equality in {(0.2)}. We then prove the converse: if a signed graph attains equality, then each of its connected components is switching equivalent to an additive rook graph.
Additive rook graphs attain equality
Theorem 4.1. If Γ \Gamma Γ is switching equivalent to Rook N ( a , b ) \operatorname{Rook}_N(a,b) Rook N ( a , b ) , then E ( Γ ) = 2 τ ( Γ ) \mathcal{E}(\Gamma)=2\tau(\Gamma) E ( Γ ) = 2 τ ( Γ ) .
Proof. Switching changes neither the spectrum nor the underlying graph, so it changes neither E ( Γ ) \mathcal{E}(\Gamma) E ( Γ ) nor τ ( Γ ) \tau(\Gamma) τ ( Γ ) . Hence we may assume that Γ = Rook N ( a , b ) \Gamma=\operatorname{Rook}_N(a,b) Γ = Rook N ( a , b ) . By Corollary 2.9, n = N ℓ n=N\ell n = N ℓ and α ( Γ ) = ℓ = n / N \alpha(\Gamma)=\ell=n/N α ( Γ ) = ℓ = n / N . Put
P ′ = R R T − 1 N J and Q ′ = C C T − 1 N J . P'=RR^{\mathsf T}-\frac{1}{N}J
\qquad\text{and}\qquad
Q'=CC^{\mathsf T}-\frac{1}{N}J. P ′ = R R T − N 1 J and Q ′ = C C T − N 1 J .
For x ∈ R n x \in\mathbb{R}^{n} x ∈ R n let y = R T x ∈ R N y=R^{\mathsf{T}}x \in\mathbb{R}^{N} y = R T x ∈ R N . Since R 1 N = 1 n R1_{N}=1_{n} R 1 N = 1 n , we have 1 n T x = 1 N T y 1_{n}^{\mathsf{T}}x=1_{N}^{\mathsf{T}}y 1 n T x = 1 N T y . The Cauchy–Schwarz inequality ( 1 N T y ) 2 ≤ N ∥ y ∥ 2 (1_{N}^{\mathsf{T}}y)^{2}\leq N\lVert y\rVert^{2} ( 1 N T y ) 2 ≤ N ∥ y ∥ 2 then gives
x T P ′ x = ∥ y ∥ 2 − 1 N ( 1 N T y ) 2 ≥ 0. x^{\mathsf{T}}P'x=\lVert y\rVert^{2}-\frac{1}{N}(1_{N}^{\mathsf{T}}y)^{2}\geq0. x T P ′ x = ∥ y ∥ 2 − N 1 ( 1 N T y ) 2 ≥ 0.
Thus P ′ ⪰ 0 P'\succeq0 P ′ ⪰ 0 , and the same argument with C C C in place of R R R shows Q ′ ⪰ 0 Q'\succeq0 Q ′ ⪰ 0 . By Lemma 2.6 (i), P ′ − Q ′ = R R T − C C T = A ( Γ ) P'-Q'=RR^{\mathsf{T}}-CC^{\mathsf{T}}=A(\Gamma) P ′ − Q ′ = R R T − C C T = A ( Γ ) , and since the diagonal entries of R R T RR^{\mathsf{T}} R R T and C C T CC^{\mathsf{T}} C C T are equal to 1 1 1 ,
tr P ′ = tr Q ′ = n − n N = n − α ( Γ ) = τ ( Γ ) . \operatorname{tr}P'=\operatorname{tr}Q'=n-\frac{n}{N}=n-\alpha(\Gamma)=\tau(\Gamma). tr P ′ = tr Q ′ = n − N n = n − α ( Γ ) = τ ( Γ ) .
Lemma 3.1 now gives E ( Γ ) ≤ tr P ′ + tr Q ′ = 2 τ ( Γ ) \mathcal{E}(\Gamma)\leq\operatorname{tr}P'+\operatorname{tr}Q'=2\tau(\Gamma) E ( Γ ) ≤ tr P ′ + tr Q ′ = 2 τ ( Γ ) , and Theorem 3.9 gives the reverse inequality.
Equality forces additive rook graphs
We now prove the converse of Theorem 4.1 , which is the main part of the article based on several novel ideas.
Theorem 4.2. Let Γ \Gamma Γ be a connected signed graph with n ≥ 2 n\geq2 n ≥ 2 vertices. If E ( Γ ) = 2 τ ( Γ ) \mathcal{E}(\Gamma)=2\tau(\Gamma) E ( Γ ) = 2 τ ( Γ ) , then Γ \Gamma Γ is switching equivalent to an additive rook graph Rook N ( a , b ) \operatorname{Rook}_{N}(a,b) Rook N ( a , b ) for some N ≥ 2 N\geq2 N ≥ 2 and some a , b ∈ Z ≥ 0 N a,b\in\mathbb{Z}_{\geq0}^{N} a , b ∈ Z ≥ 0 N .
Throughout this subsection, Γ \Gamma Γ is a connected signed graph with n ≥ 2 n\geq2 n ≥ 2 vertices and E ( Γ ) = 2 τ ( Γ ) \mathcal{E}(\Gamma)=2\tau(\Gamma) E ( Γ ) = 2 τ ( Γ ) , and A A A , P P P , Q Q Q , B B B , p v p_{v} p v , q v q_{v} q v are as in Lemma 3.2 . We write α = α ( Γ ) \alpha=\alpha(\Gamma) α = α ( Γ ) and τ = τ ( Γ ) \tau=\tau(\Gamma) τ = τ ( Γ ) . Since Γ \Gamma Γ has an edge, α ≥ 1 \alpha\geq1 α ≥ 1 and τ ≥ 1 \tau\geq1 τ ≥ 1 . Put
d : = τ n and e : = α n . d:=\frac{\tau}{n}
\qquad\text{and}\qquad
e:=\frac{\alpha}{n}. d := n τ and e := n α .
Then d + e = 1 d+e=1 d + e = 1 and d , e ∈ ( 0 , 1 ) d,e\in(0,1) d , e ∈ ( 0 , 1 ) . Switching does not change connectivity, n n n , τ \tau τ or the energy. Hence everything below also holds for every signed graph switching equivalent to Γ \Gamma Γ .
For an extremal signed graph Γ \Gamma Γ with n n n vertices, the independent number α ≤ n 2 \alpha\leq\frac{n}{2} α ≤ 2 n is obtained in the next lemma.
Proposition 4.3. The following hold.
(a) B v v = 2 d B_{vv}=2d B v v = 2 d for every vertex v v v .
(b) ∣ B u v ∣ = d − e \lvert B_{uv}\rvert=d-e ∣ B uv ∣ = d − e for every edge u v uv uv .
(c) d ≥ e d\geq e d ≥ e , that is, α ≤ n / 2 \alpha\leq n/2 α ≤ n /2 .
Proof. Since Γ \Gamma Γ is connected and n ≥ 2 n\geq2 n ≥ 2 , it has no isolated vertices. By (4) , Lemma 3.7 and E ( Γ ) = 2 τ \mathcal{E}(\Gamma)=2\tau E ( Γ ) = 2 τ ,
2 n τ − 4 m ≤ ∑ v E ( Γ − N [ v ] ) ≤ n E ( Γ ) − 4 m − ∑ u v ∈ E F u v = 2 n τ − 4 m − ∑ u v ∈ E F u v . 2n\tau-4m\leq\sum_{v}\mathcal{E}(\Gamma-N[v])\leq n\mathcal{E}(\Gamma)-4m-\sum_{uv\in E}F_{uv}=2n\tau-4m-\sum_{uv\in E}F_{uv}. 2 n τ − 4 m ≤ v ∑ E ( Γ − N [ v ]) ≤ n E ( Γ ) − 4 m − uv ∈ E ∑ F uv = 2 n τ − 4 m − uv ∈ E ∑ F uv .
Thus ∑ u v ∈ E F u v ≤ 0 \sum_{uv\in E}F_{uv}\leq0 ∑ uv ∈ E F uv ≤ 0 . By Lemma 3.8, every F u v F_{uv} F uv is zero, and therefore x u = x v = 1 + ∣ z u v ∣ x_{u}=x_{v}=1+\lvert z_{uv}\rvert x u = x v = 1 + ∣ z uv ∣ for every edge u v uv uv . Since Γ \Gamma Γ is connected, all x v x_{v} x v are equal to a common value x x x . Then n x = tr B = E ( Γ ) = 2 τ nx=\operatorname{tr}B=\mathcal{E}(\Gamma)=2\tau n x = tr B = E ( Γ ) = 2 τ , so x = 2 d x=2d x = 2 d . This proves (a). For every edge, ∣ z u v ∣ = x − 1 = 2 d − ( d + e ) = d − e \lvert z_{uv}\rvert=x-1=2d-(d+e)=d-e ∣ z uv ∣ = x − 1 = 2 d − ( d + e ) = d − e , which proves (b). Finally, (c) follows from ∣ z u v ∣ ≥ 0 \lvert z_{uv}\rvert\geq0 ∣ z uv ∣ ≥ 0 .
:::
Lemma 4.4. The following hold.
(1) ∥ p v ∥ 2 = ∥ q v ∥ 2 = d \lVert p_v\rVert^2=\lVert q_v\rVert^2=d ∥ p v ∥ 2 = ∥ q v ∥ 2 = d for every vertex v v v .
(2) For every edge u v uv uv , the pair ( P u v , Q u v ) (P_{uv},Q_{uv}) ( P uv , Q uv ) equals either ( A u v d , − A u v e ) (A_{uv}d,-A_{uv}e) ( A uv d , − A uv e ) or ( A u v e , − A u v d ) (A_{uv}e,-A_{uv}d) ( A uv e , − A uv d ) .
(3) For distinct non-adjacent vertices u , v u,v u , v , P u v = Q u v P_{uv}=Q_{uv} P uv = Q uv .
(4) ∣ P u v ∣ = d \lvert P_{uv}\rvert=d ∣ P uv ∣ = d if and only if p u = ± p v p_u=\pm p_v p u = ± p v , and ∣ Q u v ∣ = d \lvert Q_{uv}\rvert=d ∣ Q uv ∣ = d if and only if q u = ± q v q_u=\pm q_v q u = ± q v .
Proof. (1) follows from Lemma 3.2 (2) and Proposition 4.3 (a).
(2) Let s = A u v ∈ { 1 , − 1 } s=A_{uv}\in\{1,-1\} s = A uv ∈ { 1 , − 1 } . By Proposition 4.3 (b), B u v = ± s ( d − e ) B_{uv}=\pm s(d-e) B uv = ± s ( d − e ) . We use P = 1 2 ( B + A ) P=\frac{1}{2}(B+A) P = 2 1 ( B + A ) , Q = 1 2 ( B − A ) Q=\frac{1}{2}(B-A) Q = 2 1 ( B − A ) and 1 = d + e 1=d+e 1 = d + e . If B u v = s ( d − e ) B_{uv}=s(d-e) B uv = s ( d − e ) , then P u v = s 2 ( d − e + d + e ) = s d P_{uv}=\frac{s}{2}(d-e+d+e)=sd P uv = 2 s ( d − e + d + e ) = s d and Q u v = s 2 ( d − e − d − e ) = − s e Q_{uv}=\frac{s}{2}(d-e-d-e)=-se Q uv = 2 s ( d − e − d − e ) = − se . If B u v = − s ( d − e ) B_{uv}=-s(d-e) B uv = − s ( d − e ) , the same computation gives P u v = s e P_{uv}=se P uv = se and Q u v = − s d Q_{uv}=-sd Q uv = − s d .
(3) This is Lemma 3.2 (2).
(4) This follows from (1) and (F4) with r = d r=\sqrt{d} r = d .
Definition 4.5. Let Γ \Gamma Γ be a signed graph with vertex set V V V , and let P = A ( Γ ) + P=A(\Gamma)_+ P = A ( Γ ) + and Q = A ( Γ ) − Q=A(\Gamma)_- Q = A ( Γ ) − have the Gram representations P u v = ⟨ p u , p v ⟩ P_{uv}=\langle p_u,p_v\rangle P uv = ⟨ p u , p v ⟩ and Q u v = ⟨ q u , q v ⟩ Q_{uv}=\langle q_u,q_v\rangle Q uv = ⟨ q u , q v ⟩ . We define two relations on V V V by
u ≈ P v ⟺ p u = ± p v u\approx_P v\Longleftrightarrow p_u=\pm p_v u ≈ P v ⟺ p u = ± p v and u ≈ Q v ⟺ q u = ± q v u\approx_Q v\Longleftrightarrow q_u=\pm q_v u ≈ Q v ⟺ q u = ± q v .
Both are equivalence relations. Their equivalence classes are called ≈ P \approx_P ≈ P -classes and ≈ Q \approx_Q ≈ Q -classes, respectively. Each of the two families of classes partitions V V V .
By Proposition 4.3 (c), every extremal signed graph satisfies α ≤ n / 2 \alpha\le n/2 α ≤ n /2 . We first treat the boundary case α = n / 2 \alpha=n/2 α = n /2 .
Proposition 4.6. If d = e d=e d = e , that is, α = n / 2 \alpha=n/2 α = n /2 , then n = 2 a n=2a n = 2 a for some a ≥ 1 a\ge1 a ≥ 1 , and Γ \Gamma Γ is switching equivalent to K a , a = Rook 2 ( ( a , 0 ) , ( 0 , 0 ) ) K_{a,a}=\operatorname{Rook}_2((a,0),(0,0)) K a , a = Rook 2 (( a , 0 ) , ( 0 , 0 )) .
Proof. Here d = e = 1 2 d=e=\frac{1}{2} d = e = 2 1 . By Lemma 4.4 (2), ∣ P u v ∣ = 1 2 = d \lvert P_{uv}\rvert=\frac{1}{2}=d ∣ P uv ∣ = 2 1 = d on every edge u v uv uv , so u ≈ P v u\approx_Pv u ≈ P v by Lemma 4.4 (4). Since Γ \Gamma Γ is connected, ≈ P \approx_P ≈ P has only one class. Fix a vertex w w w and write p v = δ v p w p_v=\delta_vp_w p v = δ v p w with δ v ∈ { 1 , − 1 } \delta_v\in\{1,-1\} δ v ∈ { 1 , − 1 } . Let D = diag ( δ v ) D=\operatorname{diag}(\delta_v) D = diag ( δ v ) and Γ ′ = Γ D \Gamma'=\Gamma^D Γ ′ = Γ D . By Lemma 3.2 (4), the vectors δ v p v = p w \delta_vp_v=p_w δ v p v = p w form a Gram representation of P ′ = A ( Γ ′ ) + P'=A(\Gamma')_+ P ′ = A ( Γ ′ ) + , and hence P ′ = 1 2 J P'=\frac{1}{2}J P ′ = 2 1 J . Let q v ′ q'_v q v ′ be Gram vectors of Q ′ = A ( Γ ′ ) − = 1 2 J − A ( Γ ′ ) Q'=A(\Gamma')_-=\frac{1}{2}J-A(\Gamma') Q ′ = A ( Γ ′ ) − = 2 1 J − A ( Γ ′ ) .
By Lemma 4.4 (1) applied to Γ ′ \Gamma' Γ ′ , we have ∥ q v ′ ∥ 2 = 1 2 \lVert q'_v\rVert^2=\frac{1}{2} ∥ q v ′ ∥ 2 = 2 1 . So the Cauchy–Schwarz inequality gives ∣ Q u v ′ ∣ ≤ 1 2 \lvert Q'_{uv}\rvert\le\frac{1}{2} ∣ Q uv ′ ∣ ≤ 2 1 , and therefore A ( Γ ′ ) u v = 1 2 − Q u v ′ ∈ [ 0 , 1 ] A(\Gamma')_{uv}=\frac{1}{2}-Q'_{uv}\in[0,1] A ( Γ ′ ) uv = 2 1 − Q uv ′ ∈ [ 0 , 1 ] for u ≠ v u\ne v u = v . Thus all edges of Γ ′ \Gamma' Γ ′ are positive. By (F4), Q u v ′ = 1 2 Q'_{uv}=\frac{1}{2} Q uv ′ = 2 1 gives q u ′ = q v ′ q'_u=q'_v q u ′ = q v ′ on non-edges, and Q u v ′ = − 1 2 Q'_{uv}=-\frac{1}{2} Q uv ′ = − 2 1 gives q u ′ = − q v ′ q'_u=-q'_v q u ′ = − q v ′ on edges.
Let X = { v : q v ′ = q w ′ } X=\{v:q'_v=q'_w\} X = { v : q v ′ = q w ′ } and Y = { v : q v ′ = − q w ′ } Y=\{v:q'_v=-q'_w\} Y = { v : q v ′ = − q w ′ } . Every vertex lies in exactly one of these sets, and Y ≠ ∅ Y\ne\varnothing Y = ∅ because w w w has a neighbour. Two vertices are adjacent if and only if
they lie in different sets. Hence Γ ′ \Gamma' Γ ′ is the all-positive complete bipartite graph K ∣ X ∣ , ∣ Y ∣ K_{|X|,|Y|} K ∣ X ∣ , ∣ Y ∣ . Since α = max ( ∣ X ∣ , ∣ Y ∣ ) = n / 2 \alpha= \max(|X|, |Y|) = n/2 α = max ( ∣ X ∣ , ∣ Y ∣ ) = n /2 , we get ∣ X ∣ = ∣ Y ∣ = a |X| = |Y| = a ∣ X ∣ = ∣ Y ∣ = a with n = 2 a n = 2a n = 2 a . Finally, Rook 2 ( ( a , 0 ) , ( 0 , 0 ) ) \operatorname{Rook}_2((a,0),(0,0)) Rook 2 (( a , 0 ) , ( 0 , 0 )) has two squares of size a a a in row 1 and no other vertices. They are joined by positive edges, so this graph is exactly K a , a K_{a,a} K a , a .
We now turn to the remaining case α < n / 2 \alpha< n/2 α < n /2 (i.e., e < d e < d e < d ). The next lemma shows that the underlying graph of Γ \Gamma Γ is then the underlying graph of a signed grid graph.
Lemma 4.7. Let Γ \Gamma Γ be a connected signed graph of n n n vertices such that E ( Γ ) = 2 τ ( Γ ) \mathcal{E}(\Gamma) = 2\tau(\Gamma) E ( Γ ) = 2 τ ( Γ ) . Suppose e < d e < d e < d (i.e., α < n / 2 \alpha< n/2 α < n /2 ). Then for distinct vertices u , v u,v u , v ,
u ∼ v ⟺ exactly one of u ≈ P v and u ≈ Q v holds . u \sim v \Longleftrightarrow\text{exactly one of }u \mathrel{\approx_P} v\text{ and }u \mathrel{\approx_Q} v\text{ holds}. u ∼ v ⟺ exactly one of u ≈ P v and u ≈ Q v holds . Consequently, let R 1 , … , R s R_1,\ldots,R_s R 1 , … , R s be the ≈ P \mathrel{\approx_P} ≈ P -classes and C 1 , … , C t C_1,\ldots,C_t C 1 , … , C t the ≈ Q \mathrel{\approx_Q} ≈ Q -classes. Put V i j = R i ∩ C j V_{ij}=R_i\cap C_j V ij = R i ∩ C j and let W W W be the s × t s\times t s × t matrix with entries w i j = ∣ V i j ∣ w_{ij}=|V_{ij}| w ij = ∣ V ij ∣ . Regard Γ [ W ] \Gamma[W] Γ [ W ] as a signed graph on V V V whose square ( i , j ) (i,j) ( i , j ) is V i j V_{ij} V ij . Then Γ \Gamma Γ and Γ [ W ] \Gamma[W] Γ [ W ] have the same edges, and they can differ only in the signs of these edges. Moreover, W W W has no zero row and no zero column, and B ( W ) B(W) B ( W ) is connected.
Proof. Let u v uv uv be an edge. By Lemma 4.4 (2), { ∣ P u v ∣ , ∣ Q u v ∣ } = { d , e } \{|P_{uv}|,|Q_{uv}|\}=\{d,e\} { ∣ P uv ∣ , ∣ Q uv ∣ } = { d , e } , and d ≠ e d\ne e d = e . By Lemma 4.4 (4), exactly one of u ≈ P v u\mathrel{\approx_P}v u ≈ P v and u ≈ Q v u\mathrel{\approx_Q}v u ≈ Q v holds. Now let u ≠ v u\ne v u = v be non-adjacent. Then P u v = Q u v P_{uv}=Q_{uv} P uv = Q uv by Lemma 4.4 (3), so either both relations hold or neither does. This proves the equivalence.
By construction, u ≈ P v u\mathrel{\approx_P}v u ≈ P v means that u u u and v v v lie in the same row, and u ≈ Q v u\mathrel{\approx_Q}v u ≈ Q v means that they lie in the same column. Comparing with Definition 2.1 , we see that Γ \Gamma Γ and Γ [ W ] \Gamma[W] Γ [ W ] have the same edges. Each row and each column is an equivalence class, so it is nonempty. Since Γ \Gamma Γ is connected, so is Γ [ W ] \Gamma[W] Γ [ W ] , and Lemma 2.6 (v) shows that B ( W ) B(W) B ( W ) is connected.
Now we are ready to prove the following key result. By Lemma 4.7 , the underlying graph of an extremal signed graph with e < d e<d e < d (i.e., α < n / 2 \alpha<n/2 α < n /2 ) is the underlying graph of a signed grid graph Γ [ W ] \Gamma[W] Γ [ W ] . The next result shows that the signs are also those of Γ [ W ] \Gamma[W] Γ [ W ] , up to switching.
Proposition 4.8. Let Γ \Gamma Γ be a connected signed graph with E ( Γ ) = 2 τ ( Γ ) \mathcal{E}(\Gamma)=2\tau(\Gamma) E ( Γ ) = 2 τ ( Γ ) and e < d e<d e < d , and let W W W be as in Lemma 4.7 . Then Γ ∼ Γ [ W ] \Gamma\sim\Gamma[W] Γ ∼ Γ [ W ] . More precisely, there is a diagonal matrix D D D with diagonal entries ± 1 \pm1 ± 1 such that
A ( Γ D ) = R R T − C C T , P ( Γ D ) = R R T − e J , Q ( Γ D ) = C C T − e J , A(\Gamma^D)=RR^{\mathsf T}-CC^{\mathsf T},\qquad P(\Gamma^D)=RR^{\mathsf T}-eJ,\qquad Q(\Gamma^D)=CC^{\mathsf T}-eJ, A ( Γ D ) = R R T − C C T , P ( Γ D ) = R R T − e J , Q ( Γ D ) = C C T − e J , where R R R and C C C are the row-incidence and column-incidence matrices of Γ [ W ] \Gamma[W] Γ [ W ] .
Proof. We use two facts throughout. First, by the proof of Lemma 2.6 (i), ( R R T ) u v = 1 (RR^{\mathsf T})_{uv}=1 ( R R T ) uv = 1 if u , v u,v u , v lie in the same row and ( R R T ) u v = 0 (RR^{\mathsf T})_{uv}=0 ( R R T ) uv = 0 otherwise, and similarly for C C T CC^{\mathsf T} C C T and columns. Second, by Lemma 4.7 , two distinct vertices are adjacent if and only if they share exactly one of their row and their column. The proof is divided into eight claims.
Claim 1. After a switching, we may assume that there are vectors p ^ i \hat{p}_i p ^ i and q ^ j \hat{q}_j q ^ j and signs θ v ∈ { 1 , − 1 } \theta_v\in\{1,-1\} θ v ∈ { 1 , − 1 } such that
p v = p ^ r ( v ) and q v = θ v q ^ c ( v ) for every v . p_v=\hat{p}_{r(v)}\qquad\text{and}\qquad q_v=\theta_v\hat{q}_{c(v)}\qquad\text{for every }v. p v = p ^ r ( v ) and q v = θ v q ^ c ( v ) for every v .
Moreover, ∥ p ^ i ∥ 2 = ∥ q ^ j ∥ 2 = d \lVert\hat{p}_i\rVert^2=\lVert\hat{q}_j\rVert^2=d ∥ p ^ i ∥ 2 = ∥ q ^ j ∥ 2 = d .
For each row R i R_i R i pick v i ∈ R i v_i\in R_i v i ∈ R i and put p ^ i = p v i \hat{p}_i=p_{v_i} p ^ i = p v i . Since R i R_i R i is a ≈ P \approx_P ≈ P -class, each v ∈ R i v\in R_i v ∈ R i satisfies p v = δ v p ^ i p_v=\delta_v\hat{p}_i p v = δ v p ^ i for some δ v ∈ { 1 , − 1 } \delta_v\in\{1,-1\} δ v ∈ { 1 , − 1 } . Switch Γ \Gamma Γ by diag ( δ v ) \operatorname{diag}(\delta_v) diag ( δ v ) . By Lemma 3.2 (4), the new Gram vectors are δ v p v = p ^ r ( v ) \delta_vp_v=\hat{p}_{r(v)} δ v p v = p ^ r ( v ) and δ v q v \delta_vq_v δ v q v . Changing the signs of Gram vectors does not change ≈ P \approx_P ≈ P or ≈ Q \approx_Q ≈ Q , so the rows and columns are unchanged. We rename the switched graph Γ \Gamma Γ . For each column C j C_j C j pick w j ∈ C j w_j\in C_j w j ∈ C j and put q ^ j = q w j \hat{q}_j=q_{w_j} q ^ j = q w j . Since C j C_j C j is a ≈ Q \approx_Q ≈ Q -class, q v = θ v q ^ j q_v=\theta_v\hat{q}_j q v = θ v q ^ j with θ v ∈ { 1 , − 1 } \theta_v\in\{1,-1\} θ v ∈ { 1 , − 1 } for each v ∈ C j v\in C_j v ∈ C j . The norms equal d d d by Lemma 4.4 (1).
Claim 2. If u , v u,v u , v lie in the same square, then θ u = θ v \theta_u=\theta_v θ u = θ v .
We may assume u ≠ v u\ne v u = v . Since u , v u,v u , v share both their row and their column, they are non-adjacent, so P u v = Q u v P_{uv}=Q_{uv} P uv = Q uv by Lemma 4.4 (3). By Claim 1, P u v = ∥ p ^ i ∥ 2 = d P_{uv}=\lVert\hat{p}_i\rVert^2=d P uv = ∥ p ^ i ∥ 2 = d and Q u v = θ u θ v ∥ q ^ j ∥ 2 = θ u θ v d Q_{uv}=\theta_u\theta_v\lVert\hat{q}_j\rVert^2=\theta_u\theta_vd Q uv = θ u θ v ∥ q ^ j ∥ 2 = θ u θ v d . As d > 0 d>0 d > 0 , we get θ u θ v = 1 \theta_u\theta_v=1 θ u θ v = 1 .
Claim 3. With Θ = diag ( θ v ) \Theta=\operatorname{diag}(\theta_v) Θ = diag ( θ v ) we have A = R R T − Θ C C T Θ A=RR^{\mathsf{T}}-\Theta CC^{\mathsf{T}}\Theta A = R R T − Θ C C T Θ .
We compare the ( u , v ) (u,v) ( u , v ) entries. If u , v u,v u , v lie in the same square (including u = v u=v u = v ), then A u v = 0 A_{uv}=0 A uv = 0 , and the right-hand side is 1 − θ u θ v = 0 1-\theta_u\theta_v=0 1 − θ u θ v = 0 by Claim 2. If u , v u,v u , v share only a row, then u v uv uv is an edge and the right-hand side is 1 1 1 . Here P u v = ∥ p ^ r ( u ) ∥ 2 = d P_{uv}=\lVert\hat{p}_{r(u)}\rVert^2=d P uv = ∥ p ^ r ( u ) ∥ 2 = d . By Lemma 4.4 (2), P u v ∈ { A u v d , A u v e } P_{uv}\in\{A_{uv}d,A_{uv}e\} P uv ∈ { A uv d , A uv e } , and since e ≠ d e\ne d e = d this gives A u v = 1 A_{uv}=1 A uv = 1 . If u , v u,v u , v share only a column, then u v uv uv is an edge and the right-hand side is − θ u θ v -\theta_u\theta_v − θ u θ v . Here Q u v = θ u θ v d Q_{uv}=\theta_u\theta_vd Q uv = θ u θ v d . By Lemma 4.4 (2), Q u v ∈ { − A u v e , − A u v d } Q_{uv}\in\{-A_{uv}e,-A_{uv}d\} Q uv ∈ { − A uv e , − A uv d } . Since ∣ Q u v ∣ = d ≠ e \lvert Q_{uv}\rvert=d\ne e ∣ Q uv ∣ = d = e , we get Q u v = − A u v d Q_{uv}=-A_{uv}d Q uv = − A uv d , so A u v = − θ u θ v A_{uv}=-\theta_u\theta_v A uv = − θ u θ v . In all other cases u , v u,v u , v are non-adjacent and both sides are 0 0 0 .
We now consider the defect matrix X = R R T − P X=RR^{\mathsf{T}}-P X = R R T − P . It is symmetric. Since P = A + Q P=A+Q P = A + Q , Claim 3 gives X = Θ C C T Θ − Q X=\Theta CC^{\mathsf{T}}\Theta-Q X = Θ C C T Θ − Q . Thus, for all vertices u , v u,v u , v ,
X u v = ( R R T ) u v − P u v and X u v = θ u θ v ( C C T ) u v − Q u v . (5) X_{uv}=(RR^{\mathsf{T}})_{uv}-P_{uv}
\qquad\text{and}\qquad
X_{uv}=\theta_u\theta_v(CC^{\mathsf{T}})_{uv}-Q_{uv}. \tag*{(5)} X uv = ( R R T ) uv − P uv and X uv = θ u θ v ( C C T ) uv − Q uv . (5)
Claim 4. Let v v v be any vertex. If u , u ′ u,u' u , u ′ lie in the same row, then X u v = X u ′ v X_{uv}=X_{u'v} X uv = X u ′ v . If u , u ′ u,u' u , u ′ lie in the same column, then θ u X u v = θ u ′ X u ′ v \theta_uX_{uv}=\theta_{u'}X_{u'v} θ u X uv = θ u ′ X u ′ v .
Let u , u ′ u,u' u , u ′ lie in the same row i i i . Then ( R R T ) u v = ( R R T ) u ′ v (RR^{\mathsf{T}})_{uv}=(RR^{\mathsf{T}})_{u'v} ( R R T ) uv = ( R R T ) u ′ v , and p u = p u ′ = p ^ i p_u=p_{u'}=\hat{p}_i p u = p u ′ = p ^ i by Claim 1, so P u v = P u ′ v P_{uv}=P_{u'v} P uv = P u ′ v . The first formula in (5) gives X u v = X u ′ v X_{uv}=X_{u'v} X uv = X u ′ v .
Let u , u ′ u,u' u , u ′ lie in the same column j j j . Multiplying the second formula in (5) by θ u \theta_u θ u gives θ u X u v = θ v ( C C T ) u v − θ u Q u v \theta_uX_{uv}=\theta_v(CC^{\mathsf{T}})_{uv}-\theta_uQ_{uv} θ u X uv = θ v ( C C T ) uv − θ u Q uv . Here ( C C T ) u v = ( C C T ) u ′ v (CC^{\mathsf{T}})_{uv}=(CC^{\mathsf{T}})_{u'v} ( C C T ) uv = ( C C T ) u ′ v , and by Claim 1 θ u Q u v = θ u 2 ⟨ q ^ j , q v ⟩ = ⟨ q ^ j , q v ⟩ \theta_uQ_{uv}=\theta_u^2\langle\hat{q}_j,q_v\rangle=\langle\hat{q}_j,q_v\rangle θ u Q uv = θ u 2 ⟨ q ^ j , q v ⟩ = ⟨ q ^ j , q v ⟩ . The same holds for u ′ u' u ′ , so θ u X u v = θ u ′ X u ′ v \theta_uX_{uv}=\theta_{u'}X_{u'v} θ u X uv = θ u ′ X u ′ v .
Call two vertices neighbours if they lie in the same row or in the same column.
Claim 5. Any two vertices u , u ′ u,u' u , u ′ are joined by a sequence of vertices in which any two consecutive vertices are neighbours.
If r ( u ) = r ( u ′ ) r(u)=r(u') r ( u ) = r ( u ′ ) , there is nothing to prove. Otherwise, since B ( W ) \mathcal{B}(W) B ( W ) is connected by Lemma 4.7 , it contains a path r ( u ) = i 0 , j 1 , i 1 , j 2 , … , j m , i m = r ( u ′ ) r(u)=i_0,j_1,i_1,j_2,\ldots,j_m,i_m=r(u') r ( u ) = i 0 , j 1 , i 1 , j 2 , … , j m , i m = r ( u ′ ) , in which rows and columns alternate. Each edge of this path is a nonempty square, so the squares ( i 0 , j 1 ) , ( i 1 , j 1 ) , ( i 1 , j 2 ) , … , ( i m , j m ) (i_0,j_1),(i_1,j_1),(i_1,j_2),\ldots,(i_m,j_m) ( i 0 , j 1 ) , ( i 1 , j 1 ) , ( i 1 , j 2 ) , … , ( i m , j m ) are nonempty. Consecutive squares in this list share a row or a column. Choose one vertex in each square, and add u u u at the beginning and u ′ u' u ′ at the end. This gives the required sequence.
Let U U U be the set of vectors y ∈ R V y \in\mathbb{R}^{V} y ∈ R V such that y u = y u ′ y_u=y_{u'} y u = y u ′ whenever u , u ′ u,u' u , u ′ lie in the same row, and θ u y u = θ u ′ y u ′ \theta_u y_u=\theta_{u'}y_{u'} θ u y u = θ u ′ y u ′ whenever u , u ′ u,u' u , u ′ lie in the same column.
Claim 6. U U U is a subspace of R V \mathbb{R}^{V} R V and dim U ≤ 1 \dim U \le1 dim U ≤ 1 .
The conditions defining U U U are linear, so U U U is a subspace. Fix a vertex w w w and let y ∈ U y \in U y ∈ U with y w = 0 y_w=0 y w = 0 . If y u = 0 y_u=0 y u = 0 and u ′ u' u ′ is a neighbour of u u u , then y u ′ = 0 y_{u'}=0 y u ′ = 0 , where in the column case we use θ u ′ = ± 1 \theta_{u'}=\pm1 θ u ′ = ± 1 . By Claim 5, every vertex is reached from w w w through neighbours, so y = 0 y=0 y = 0 . Hence the linear map y ↦ y w y \mapsto y_w y ↦ y w is injective on U U U , and dim U ≤ 1 \dim U \le1 dim U ≤ 1 .
Claim 7. There is a vector s ∈ U s \in U s ∈ U with s v ∈ { 1 , − 1 } s_v \in\{1,-1\} s v ∈ { 1 , − 1 } for every v v v such that X = e s s T X=e ss^{\mathsf{T}} X = es s T . In particular, s u = s u ′ s_u=s_{u'} s u = s u ′ whenever u , u ′ u,u' u , u ′ lie in the same row, and θ u s u = θ u ′ s u ′ \theta_u s_u=\theta_{u'}s_{u'} θ u s u = θ u ′ s u ′ whenever u , u ′ u,u' u , u ′ lie in the same column.
By Claim 4, every column of X X X lies in U U U . Hence the column space of X X X is contained in U U U , and rank X ≤ 1 \operatorname{rank} X \le1 rank X ≤ 1 by Claim 6. On the other hand, X v v = ( R R T ) v v − P v v = 1 − d = e ≠ 0 X_{vv}=(RR^{\mathsf{T}})_{vv}-P_{vv}=1-d=e\ne0 X v v = ( R R T ) v v − P v v = 1 − d = e = 0 for every v v v , so rank X = 1 \operatorname{rank} X=1 rank X = 1 . A symmetric matrix of rank one has the form X = λ y y T X=\lambda yy^{\mathsf{T}} X = λ y y T , where λ ≠ 0 \lambda\ne0 λ = 0 and y y y is a nonzero vector spanning its column space. In particular y ∈ U y \in U y ∈ U . Comparing diagonal entries gives λ y v 2 = e \lambda y_v^2=e λ y v 2 = e for every v v v , so all ∣ y v ∣ \lvert y_v\rvert ∣ y v ∣ are equal and nonzero. Dividing y y y by ∣ y v ∣ \lvert y_v\rvert ∣ y v ∣ , we obtain a vector s ∈ U s \in U s ∈ U with entries ± 1 \pm1 ± 1 and X = e s s T X=e ss^{\mathsf{T}} X = es s T . The last statement is the definition of U U U .
Claim 8. Let D = diag ( s v ) D=\operatorname{diag}(s_v) D = diag ( s v ) . Then D X D = e J DXD=eJ D X D = e J , D R R T D = R R T DRR^{\mathsf{T}}D=RR^{\mathsf{T}} D R R T D = R R T and D Θ C C T Θ D = C C T D\Theta CC^{\mathsf{T}}\Theta D=CC^{\mathsf{T}} D Θ C C T Θ D = C C T .
For every matrix M M M we have ( D M D ) u v = s u s v M u v (DMD)_{uv}=s_us_vM_{uv} ( D M D ) uv = s u s v M uv . By Claim 7, ( D X D ) u v = e s u 2 s v 2 = e (DXD)_{uv}=e s_u^2s_v^2=e ( D X D ) uv = e s u 2 s v 2 = e . Next, ( D R R T D ) u v = s u s v ( R R T ) u v (DRR^{\mathsf{T}}D)_{uv}=s_us_v(RR^{\mathsf{T}})_{uv} ( D R R T D ) uv = s u s v ( R R T ) uv is nonzero only if u , v u,v u , v lie in the same row, and then s u s v = 1 s_us_v=1 s u s v = 1 by Claim 7. Finally, ( D Θ C C T Θ D ) u v = ( θ u s u ) ( θ v s v ) ( C C T ) u v (D\Theta CC^{\mathsf{T}}\Theta D)_{uv}=(\theta_us_u)(\theta_vs_v)(CC^{\mathsf{T}})_{uv} ( D Θ C C T Θ D ) uv = ( θ u s u ) ( θ v s v ) ( C C T ) uv is nonzero only if u , v u,v u , v lie in the same column, and then ( θ u s u ) ( θ v s v ) = 1 (\theta_us_u)(\theta_vs_v)=1 ( θ u s u ) ( θ v s v ) = 1 by Claim 7. ◇
We can now finish the proof. By Lemma 3.2 (4), Claim 3, Claim 8 and P = R R T − X P=RR^{\mathsf{T}}-X P = R R T − X ,
A ( Γ D ) = D A D = R R T − C C T , P ( Γ D ) = D P D = R R T − e J , A(\Gamma^D)=DAD=RR^{\mathsf{T}}-CC^{\mathsf{T}}, \qquad P(\Gamma^D)=DPD=RR^{\mathsf{T}}-eJ, A ( Γ D ) = D A D = R R T − C C T , P ( Γ D ) = D P D = R R T − e J ,
and hence Q ( Γ D ) = P ( Γ D ) − A ( Γ D ) = C C T − e J Q(\Gamma^D)=P(\Gamma^D)-A(\Gamma^D)=CC^{\mathsf{T}}-eJ Q ( Γ D ) = P ( Γ D ) − A ( Γ D ) = C C T − e J . The switching in Claim 1 followed by D D D is again a single switching of the original graph. Finally, A ( Γ D ) = A ( Γ [ W ] ) A(\Gamma^D)=A(\Gamma[W]) A ( Γ D ) = A ( Γ [ W ]) by Lemma 2.6 (i). □
It remains to show that the matrix W W W of Lemma 4.7 has the additive form required in Definition 2.4 . We first bound the size of the board.
Lemma 4.9. Suppose e < d e<d e < d , and let W W W be the s × t s \times t s × t matrix of Lemma 4.7 . Then the board of Γ [ W ] \Gamma[W] Γ [ W ] has at most n / α n/\alpha n / α rows and at most n / α n/\alpha n / α columns, that is,
max ( s , t ) ≤ n α . \max(s,t) \le\frac{n}{\alpha}. max ( s , t ) ≤ α n .
Proof. Choose one vertex in each row, and let x ∈ R V x \in\mathbb{R}^{V} x ∈ R V be the sum of the indicator vectors of these s s s vertices. Then R T x R^{\mathsf{T}}x R T x is the all-ones vector of length s s s , so x T R R T x = s x^{\mathsf{T}}RR^{\mathsf{T}}x=s x T R R T x = s . Also x T J x = s 2 x^{\mathsf{T}}Jx=s^{2} x T J x = s 2 .
By Proposition 4.8, the matrix R R T − e J = P ( Γ D ) RR^{\mathsf{T}}-eJ=P(\Gamma^{D}) R R T − e J = P ( Γ D ) is positive semidefinite. Hence
0 ≤ x T ( R R T − e J ) x = s − e s 2 , 0 \le x^{\mathsf{T}}\left(RR^{\mathsf{T}}-eJ\right)x=s-es^{2}, 0 ≤ x T ( R R T − e J ) x = s − e s 2 ,
which gives s ≤ 1 / e = n / α s \le1/e=n/\alpha s ≤ 1/ e = n / α . The same argument with C C T − e J = Q ( Γ D ) CC^{\mathsf{T}}-eJ=Q(\Gamma^{D}) C C T − e J = Q ( Γ D ) and one vertex in each column gives t ≤ n / α t \le n/\alpha t ≤ n / α .
Lemma 4.10. Suppose e < d e<d e < d , let W W W be the s × t s \times t s × t matrix of Lemma 4.7, and put N = max ( s , t ) N=\max(s,t) N = max ( s , t ) . Then, after adding zero rows or zero columns, W W W becomes an N × N N \times N N × N matrix with entries w i j = a i + b j w_{ij}=a_i+b_j w ij = a i + b j for some a , b ∈ Z ≥ 0 a,b \in\mathbb{Z}_{\ge0} a , b ∈ Z ≥ 0 . Consequently, Γ [ W ] = Rook N ( a , b ) \Gamma[W]=\operatorname{Rook}_{N}(a,b) Γ [ W ] = Rook N ( a , b ) .
Proof. By Lemma 4.7, Γ [ W ] \Gamma[W] Γ [ W ] has the same underlying graph as Γ \Gamma Γ . Hence α ( Γ [ W ] ) = α \alpha(\Gamma[W])=\alpha α ( Γ [ W ]) = α and ∑ i , j w i j = n \sum_{i,j}w_{ij}=n ∑ i , j w ij = n .
Case: s ≤ t s \le t s ≤ t .
By Lemma 2.7(b), α ≥ n / t \alpha\ge n/t α ≥ n / t . By Lemma 4.9, t ≤ n / α t \le n/\alpha t ≤ n / α , that is, α ≤ n / t \alpha\le n/t α ≤ n / t . So α = n / t \alpha=n/t α = n / t , and Lemma 2.7(c),(d) gives two possibilities. If s < t s<t s < t , then w i j = a i w_{ij}=a_i w ij = a i for all i , j i,j i , j . Adding t − s t-s t − s zero rows does not change Γ [ W ] \Gamma[W] Γ [ W ] by Lemma 2.6(iv), and the result is Rook t ( ( a 1 , … , a s , 0 , … , 0 ) , 0 ) \operatorname{Rook}_{t}((a_1,\ldots,a_s,0,\ldots,0),0) Rook t (( a 1 , … , a s , 0 , … , 0 ) , 0 ) .
If s = t s=t s = t , then w i j = a i + b j w_{ij}=a_i+b_j w ij = a i + b j for some integers a i , b j a_i,b_j a i , b j . By Remark 2.8 they may be chosen nonnegative, and so Γ [ W ] = Rook s ( a , b ) \Gamma[W]=\operatorname{Rook}_{s}(a,b) Γ [ W ] = Rook s ( a , b ) .
Case: s > t s>t s > t .
By Lemma 2.6(iii), Γ [ W T ] = − Γ [ W ] \Gamma[W^{\mathsf{T}}]=-\Gamma[W] Γ [ W T ] = − Γ [ W ] has the same underlying graph as Γ \Gamma Γ , and its board has t t t rows and s s s columns. Applying the previous case to W T W^{\mathsf{T}} W T gives w i j = b j w_{ij}=b_j w ij = b j for all i , j i,j i , j . Adding s − t s-t s − t zero columns, we obtain Γ [ W ] = Rook s ( 0 , ( b 1 , … , b t , 0 , … , 0 ) ) \Gamma[W]=\operatorname{Rook}_{s}(0,(b_1,\ldots,b_t,0,\ldots,0)) Γ [ W ] = Rook s ( 0 , ( b 1 , … , b t , 0 , … , 0 )) .
We can now complete the proof of Theorem 4.2.
Proof of Theorem 4.2. If d = e d=e d = e , then Γ ∼ Rook 2 ( ( a , 0 ) , ( 0 , 0 ) ) \Gamma\sim\operatorname{Rook}_{2}((a,0),(0,0)) Γ ∼ Rook 2 (( a , 0 ) , ( 0 , 0 )) by Proposition 4.6. If d > e d>e d > e , then Γ ∼ Γ [ W ] \Gamma\sim\Gamma[W] Γ ∼ Γ [ W ] by Proposition 4.8, and Γ [ W ] = Rook N ( a , b ) \Gamma[W]=\operatorname{Rook}_{N}(a,b) Γ [ W ] = Rook N ( a , b ) by Lemma 4.10. Finally, N ≥ 2 N \ge2 N ≥ 2 , because Γ \Gamma Γ has an edge while Rook 1 ( a , b ) \operatorname{Rook}_{1}(a,b) Rook 1 ( a , b ) has none.
Proof of the main theorem
Proof of Theorem 0.1. The inequality E ( Γ ) ≥ 2 τ ( Γ ) \mathcal{E}(\Gamma) \ge2\tau(\Gamma) E ( Γ ) ≥ 2 τ ( Γ ) is Theorem 3.9. It remains to characterize equality.
Suppose first that every connected component of Γ \Gamma Γ is switching equivalent to an additive rook graph. By Theorem 4.1, every component attains equality, and therefore E ( Γ ) = 2 τ ( Γ ) \mathcal{E}(\Gamma)=2\tau(\Gamma) E ( Γ ) = 2 τ ( Γ ) by Corollary 3.10. Conversely, suppose that E ( Γ ) = 2 τ ( Γ ) \mathcal{E}(\Gamma)=2\tau(\Gamma) E ( Γ ) = 2 τ ( Γ ) . By Corollary 3.10 , every connected component of Γ \Gamma Γ attains equality. A component with one vertex is K 1 = Rook 1 ( ( 1 ) , ( 0 ) ) K_1=\operatorname{Rook}_1((1),(0)) K 1 = Rook 1 (( 1 ) , ( 0 )) . A component with at least two vertices is switching equivalent to an additive rook graph by Theorem 4.2 . Hence every component of Γ \Gamma Γ is switching equivalent to an additive rook graph.
Consequences and limitations
We call a signed graph Γ \Gamma Γ extremal if E ( Γ ) = 2 τ ( Γ ) \mathcal{E}(\Gamma)=2\tau(\Gamma) E ( Γ ) = 2 τ ( Γ ) . In this section we derive some consequences of Theorem 0.1. We compute the basic parameters of a connected extremal signed graph, decide when it is balanced or antibalanced, and recover the characterization of extremal unsigned graphs.
Unsigned graphs
Corollary 6.1. Let Γ \Gamma Γ be a connected extremal signed graph with Γ ∼ Rook N ( a , b ) \Gamma\sim\operatorname{Rook}_N(a,b) Γ ∼ Rook N ( a , b ) . Then
n = N ℓ , α ( Γ ) = ℓ , E ( Γ ) = 2 ( N − 1 ) ℓ . n=N\ell,\qquad\alpha(\Gamma)=\ell,\qquad\mathcal{E}(\Gamma)=2(N-1)\ell. n = N ℓ , α ( Γ ) = ℓ , E ( Γ ) = 2 ( N − 1 ) ℓ . Moreover, every vertex v v v has the same vertex energy ∣ A ( Γ ) ∣ v v = 2 ( N − 1 ) N \lvert A(\Gamma)\rvert_{vv}=\frac{2(N-1)}{N} ∣ A ( Γ ) ∣ v v = N 2 ( N − 1 ) .
Proof. Switching changes neither n n n , α \alpha α nor the energy. So the first three equalities follow from Corollary 2.9 and Theorem 4.1 . If n ≥ 2 n\ge2 n ≥ 2 , then Proposition 4.3 (a) gives ∣ A ( Γ ) ∣ v v = 2 τ ( Γ ) / n = 2 ( N − 1 ) / N \lvert A(\Gamma)\rvert_{vv}=2\tau(\Gamma)/n=2(N-1)/N ∣ A ( Γ ) ∣ v v = 2 τ ( Γ ) / n = 2 ( N − 1 ) / N . If n = 1 n=1 n = 1 , then Γ = K 1 \Gamma=K_1 Γ = K 1 , N = 1 N=1 N = 1 , and both sides are 0.
For an additive rook graph we say that a row or a column of the board is nonempty if it contains at least one vertex.
Theorem 6.2. Let Γ \Gamma Γ be a connected extremal signed graph with Γ ∼ Rook N ( a , b ) \Gamma\sim\operatorname{Rook}_N(a,b) Γ ∼ Rook N ( a , b ) .
(a) The following are equivalent:
(i) Γ \Gamma Γ is balanced;
(ii) the board of Rook N ( a , b ) \operatorname{Rook}_N(a,b) Rook N ( a , b ) has at most two nonempty rows;
(iii) Γ \Gamma Γ is switching equivalent to K 1 K_1 K 1 , to K x , … , x K_{x,\ldots,x} K x , … , x with r ≥ 2 r\ge2 r ≥ 2 parts, or to H r ( x , y ) H_r(x,y) H r ( x , y ) with r ≥ 3 r\ge3 r ≥ 3 .
(b) The following are equivalent:
(i) Γ \Gamma Γ is antibalanced;
(ii) the board of Rook N ( a , b ) \operatorname{Rook}_N(a,b) Rook N ( a , b ) has at most two nonempty columns;
(iii) Γ \Gamma Γ is switching equivalent to K 1 K_1 K 1 , to − K x , … , x -K_{x,\ldots,x} − K x , … , x with r ≥ 2 r\ge2 r ≥ 2 parts, or to − H r ( x , y ) -H_r(x,y) − H r ( x , y ) with r ≥ 3 r\ge3 r ≥ 3 .
(c) If the board has at least three nonempty rows and at least three nonempty columns, then Γ \Gamma Γ is neither balanced nor antibalanced.
Proof. Switching does not change balance or antibalance. Hence we may assume Γ = Rook N ( a , b ) \Gamma= \operatorname{Rook}_N(a,b) Γ = Rook N ( a , b ) .
(a) We first show that (ii) implies (i). If only one row is nonempty, every edge joins two vertices of that row and is positive. If exactly two rows are nonempty, switch at all vertices of one of them. A row edge has both ends switched or neither, so it stays positive. A column edge joins the two nonempty rows, so exactly one of its ends is switched, and it becomes positive. In both cases Γ \Gamma Γ is switching equivalent to an all-positive graph, and so it is balanced.
Next we show that (i) implies (ii). Suppose rows i 1 , i 2 , i 3 i_1,i_2,i_3 i 1 , i 2 , i 3 are nonempty. We claim that some column meets all three of them in nonempty squares. If b j > 0 b_j > 0 b j > 0 for some j j j , then every square of column j j j has a i + b j > 0 a_i+b_j > 0 a i + b j > 0 vertices. If b = 0 b=0 b = 0 , then a i 1 , a i 2 , a i 3 > 0 a_{i_1},a_{i_2},a_{i_3} > 0 a i 1 , a i 2 , a i 3 > 0 , and every square in these three rows is nonempty. Taking one vertex from each of the three squares, we obtain three vertices in the same column and in different rows. They are pairwise joined by negative edges, so they form a negative triangle. Hence Γ \Gamma Γ is not balanced.
It remains to show that (ii) is equivalent to (iii). The graphs listed in (iii) are all-positive, so (iii) implies (i), and hence (ii). Conversely, assume (ii).
Suppose first that b j > 0 b_j > 0 b j > 0 for some j j j . Then every row is nonempty, so N ≤ 2 N \le2 N ≤ 2 . If N = 1 N=1 N = 1 , the graph has no edges, and since it is connected, Γ = K 1 \Gamma= K_1 Γ = K 1 . If N = 2 N=2 N = 2 , switch at the vertices of row 2. As above, every edge becomes positive. Row edges join V 11 V_{11} V 11 with V 12 V_{12} V 12 and V 21 V_{21} V 21 with V 22 V_{22} V 22 , and column edges join V 11 V_{11} V 11 with V 21 V_{21} V 21 and V 12 V_{12} V 12 with V 22 V_{22} V 22 . Hence the switched graph is the complete bipartite graph with parts V 11 ∪ V 22 V_{11} \cup V_{22} V 11 ∪ V 22 and V 12 ∪ V 21 V_{12} \cup V_{21} V 12 ∪ V 21 . Both parts have ℓ \ell ℓ vertices, so Γ ∼ K ℓ , ℓ \Gamma\sim K_{\ell,\ell} Γ ∼ K ℓ , ℓ .
Suppose now that b = 0 b=0 b = 0 , so that w i j = a i w_{ij}=a_i w ij = a i and the nonempty rows are those with a i > 0 a_i > 0 a i > 0 . If only row i i i is nonempty, then Γ \Gamma Γ is the all-positive K a i , … , a i K_{a_i,\ldots,a_i} K a i , … , a i with N N N parts, and connectivity gives either N ≥ 2 N \ge2 N ≥ 2 or Γ = K 1 \Gamma= K_1 Γ = K 1 . If exactly the rows i i i and k k k are nonempty, then switching at the vertices of row k k k gives the unsigned graph H N ( a i , a k ) H_N(a_i,a_k) H N ( a i , a k ) , as in Example 2.5 . For N = 2 N=2 N = 2 this graph is K a i + a k , a i + a k K_{a_i+a_k,a_i+a_k} K a i + a k , a i + a k , and for N ≥ 3 N \ge3 N ≥ 3 it is H N ( a i , a k ) H_N(a_i,a_k) H N ( a i , a k ) with N ≥ 3 N \ge3 N ≥ 3 .
(b) By Lemma 2.6 (iii), − Γ = Rook N ( b , a ) -\Gamma= \operatorname{Rook}_N(b,a) − Γ = Rook N ( b , a ) , and the rows of its board are the columns of the board of Γ \Gamma Γ . Moreover, − Γ -\Gamma − Γ is connected and extremal, since negation changes neither the energy nor the underlying graph. Now apply (a) to − Γ -\Gamma − Γ .
(c) By the proof of (a), at least three nonempty rows give a negative triangle, so Γ \Gamma Γ is not balanced. Similarly, at least three nonempty columns give three vertices in one row and in different columns, which form a positive triangle. This triangle is negative in − Γ -\Gamma − Γ , so Γ \Gamma Γ is not antibalanced.
Remark 6.3. Cases (a) and (b) overlap exactly when the board has at most two nonempty rows and at most two nonempty columns. Up to switching, this happens only for K 1 K_1 K 1 and K x , x K_{x,x} K x , x . These are the connected extremal signed graphs that are both balanced and antibalanced.
Table 1 summarizes Theorem 6.2 .
Table 1. Balance of the connected extremal signed graphs.
Finally, we recover the characterization of extremal unsigned graphs due to Mojallal [31 ] .
Corollary 6.4. An unsigned graph G G G satisfies E ( G ) = 2 τ ( G ) \mathcal{E}(G)=2\tau(G) E ( G ) = 2 τ ( G ) if and only if every connected component of G G G is K 1 K_1 K 1 , a complete multipartite graph K x , … , x K_{x,\ldots,x} K x , … , x with r ≥ 2 r \ge2 r ≥ 2 parts, or a graph H r ( x , y ) H_r(x,y) H r ( x , y ) with r ≥ 3 r \ge3 r ≥ 3 .
Proof. Regard G G G as the all-positive signed graph. Suppose E ( G ) = 2 τ ( G ) \mathcal{E}(G)=2\tau(G) E ( G ) = 2 τ ( G ) . By Corollary 3.10 , every connected component is extremal, and it is balanced because all its edges are positive. By Theorem 0.1, it is switching equivalent to an additive rook graph. By Theorem 6.2 (a), it is therefore switching equivalent to one of the listed graphs. Switching does not change the underlying graph, so the component is isomorphic to that graph. Conversely, each listed graph is switching equivalent to an additive rook graph by Example 2.5 , so it is extremal by Theorem 0.1. Corollary 3.10 then gives E ( G ) = 2 τ ( G ) \mathcal{E}(G)=2\tau(G) E ( G ) = 2 τ ( G ) .
Corollary 6.4 shows that the extremal unsigned graphs are exactly the balanced connected extremal signed graphs, up to switching. The family of extremal signed graphs is strictly larger. In particular, a signed graph can be extremal even when its underlying graph is not extremal as an unsigned graph.
Examples 6.5. Let Γ = Rook 3 ( ( 1 , 1 , 1 ) , 0 ) \Gamma=\operatorname{Rook}_3((1,1,1),\mathbf{0}) Γ = Rook 3 (( 1 , 1 , 1 ) , 0 ) . This is the graph K 3 □ K 3 K_3 \square K_3 K 3 □ K 3 with positive rows and negative columns. By Corollary 2.9 we have τ ( Γ ) = 6 \tau(\Gamma)=6 τ ( Γ ) = 6 . The spectrum of Γ \Gamma Γ is { 3 [ 2 ] , 0 [ 5 ] , ( − 3 ) [ 2 ] } \{3^{[2]},0^{[5]},(-3)^{[2]}\} { 3 [ 2 ] , 0 [ 5 ] , ( − 3 ) [ 2 ] } , so E ( Γ ) = 12 = 2 τ ( Γ ) \mathcal{E}(\Gamma)=12=2\tau(\Gamma) E ( Γ ) = 12 = 2 τ ( Γ ) . On the other hand, the underlying graph K 3 □ K 3 K_3 \square K_3 K 3 □ K 3 has spectrum { 4 [ 1 ] , 1 [ 4 ] , ( − 2 ) [ 4 ] } \{4^{[1]},1^{[4]},(-2)^{[4]}\} { 4 [ 1 ] , 1 [ 4 ] , ( − 2 ) [ 4 ] } and energy 16 = E ( K 3 □ K 3 ) > 2 τ ( K 3 □ K 3 ) = 12 16=\mathcal{E}(K_3 \square K_3)>2\tau(K_3 \square K_3)=12 16 = E ( K 3 □ K 3 ) > 2 τ ( K 3 □ K 3 ) = 12 .
Failure of the bound for T-gain graphs
A complex unit gain graph (or T \mathbb{T} T -gain graph) Ψ = ( G , ψ ) \Psi=(G,\psi) Ψ = ( G , ψ ) assigns to each oriented edge u v → \overrightarrow{uv} uv a complex number ψ ( u v → ) \psi(\overrightarrow{uv}) ψ ( uv ) of modulus one, with ψ ( v u → ) = ψ ( u v → ) ‾ \psi(\overrightarrow{vu})=\overline{\psi(\overrightarrow{uv})} ψ ( v u ) = ψ ( uv ) [33 , 30 , 35 ] . Its adjacency matrix A ( Ψ ) A(\Psi) A ( Ψ ) is the Hermitian matrix with A ( Ψ ) u v = ψ ( u v → ) A(\Psi)_{uv}=\psi(\overrightarrow{uv}) A ( Ψ ) uv = ψ ( uv ) if u ∼ v u\sim v u ∼ v and A ( Ψ ) u v = 0 A(\Psi)_{uv}=0 A ( Ψ ) uv = 0 otherwise. The Hermitian adjacency matrix of a mixed graph [21 , 28 ] is the special case in which every gain is 1 1 1 (undirected edge) or ± i \pm i ± i (arc). Signed graphs are exactly the T \mathbb{T} T -gain graphs with all gains in { 1 , − 1 } \{1,-1\} { 1 , − 1 } . The next example shows that Theorem 0.1 does not extend beyond this case.
Examples 6.6. Let Ψ = ( K 3 , ψ ) \Psi= (K_3,\psi) Ψ = ( K 3 , ψ ) be the T \mathbb{T} T -gain graph on the vertices v 1 , v 2 , v 3 v_1,v_2,v_3 v 1 , v 2 , v 3 with ψ ( v 1 v 2 → ) = ψ ( v 2 v 3 → ) = ψ ( v 3 v 1 → ) = i \psi(\overrightarrow{v_1v_2}) = \psi(\overrightarrow{v_2v_3}) = \psi(\overrightarrow{v_3v_1}) = i ψ ( v 1 v 2 ) = ψ ( v 2 v 3 ) = ψ ( v 3 v 1 ) = i . Then
A ( Ψ ) = [ 0 i − i − i 0 i i − i 0 ] , A(\Psi) =
\begin{bmatrix}
0 & i & -i \\
-i & 0 & i \\
i & -i & 0
\end{bmatrix}, A ( Ψ ) = 0 − i i i 0 − i − i i 0 , which is also the Hermitian adjacency matrix of the directed triangle v 1 → v 2 → v 3 → v 1 v_1 \to v_2 \to v_3 \to v_1 v 1 → v 2 → v 3 → v 1 . Its characteristic polynomial is λ 3 − 3 λ \lambda^3 - 3\lambda λ 3 − 3 λ , so its eigenvalues are − 3 -\sqrt{3} − 3 , 0 0 0 and 3 \sqrt{3} 3 . Since τ ( K 3 ) = 2 \tau(K_3) = 2 τ ( K 3 ) = 2 , we get
E ( Ψ ) = 2 3 < 4 = 2 τ ( K 3 ) . \mathcal{E}(\Psi) = 2\sqrt{3} < 4 = 2\tau(K_3). E ( Ψ ) = 2 3 < 4 = 2 τ ( K 3 ) .
It can be seen that the signed graphs form the largest class of T \mathbb{T} T -gain graphs to which Theorem 0.1 applies in its present form. For T \mathbb{T} T -gain graphs only weaker bounds are known, such as E ( Ψ ) ≥ 2 τ ( G ) − 2 c ( G ) \mathcal{E}(\Psi) \ge2\tau(G) - 2c(G) E ( Ψ ) ≥ 2 τ ( G ) − 2 c ( G ) , where c ( G ) c(G) c ( G ) is the number of odd cycles of G G G [36 ] .
Acknowledgment: Aniruddha Samanta thanks the Birla Institute of Technology, Mesra, for financial support under the Institute Seed Money Scheme (Ref. No. DRIE/SMS/DRIE-10989/2026-27/1977). K. C. Das is supported by the National Research Foundation funded by the Korean government (Grant No. RS-2026-25475577).
Data Availability: Not applicable.
Declaration of competing interest: The authors declare that they have no competing financial interests or personal relationships that could have influenced this work.