# On Laplacian Equienergetic Signed Graphs

Authors: Qingyun Tao; Lixin Tao
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The Laplacian energy of a signed graph is defined as the sum of the distance of its Laplacian eigenvalues from its average degree. Two signed graphs of the same order are said to be Laplacian equienergetic if their Laplacian energies are equal. In this paper, we present several infinite families of Laplacian equienergetic signed graphs.


---

## Body

## 1. Introduction

A signed graph is an ordered pairΓ=G,σ, where G=V,E is a simple unsigned graph called the underlying graph of Γ, and σ:E⟶+,−, called a signing (or a signature), is a sign function from the edge set E to the set +,− of signs.The sign of a signed graph is defined as the product of signs of its edges. A signed graph is said to be positive (respectively, negative) if its sign is positive (respectively, negative), i.e., it contains an even (respectively, an odd) number of negative edges. A signed graph is said to be all-positive (respectively, all-negative) if all its edges are positive (respectively, negative), denoted byG,+ (respectivelyG,−). A signed graph is said to be balanced if each of its cycles is positive, otherwise unbalanced.LetAG=aijn×n be adjacency matrix of unsigned graph G, where aij=1 whenever vertices i and j are adjacent and aij=0 otherwise. And, let DG be its diagonal matrix of vertices degrees; then, LG=DG−AG and QG=DG+AG are called Laplacian and signless Laplacian matrix of G, respectively.Similarly, for a signed graphΓ=G,σ, its adjacency matrix AΓ=aijn×n is defined as(1)aij=σij,if verticesiandjare adjacent,0,otherwise,and LΓ=DΓ−AΓ is called its Laplacian matrix, where DΓ is the same as DG. Note that LG,+=LG and LG,−=QG.SupposeΓ=G,σ is a signed graph and θ:V⟶+1,−1 is any sign function. Switching Γ by θ means constructing a new signed graph Γθ=G,σθ whose underlying graph is also G, while sign function specified on an edge e=vivj is σθe=θviσeθvj.LetΓ1=G,σ1 and Γ2=G,σ2 be two signed graphs on the same underlying graph G. We call Γ1 and Γ2 are switching equivalent; write Γ1∼Γ2, if there exists a switching function θ such that Γ2=Γ1θ. Actually, switching equivalent signed graphs can be considered as switching isomorphic, and their signatures are thought to be equivalent. Switching leaves many signed-graphic invariant, such as the set of positive cycles.Two matricesM1 and M2 of order n are called signature similar if there exists a signature matrix, i.e., a diagonal matrix S=diags1,…,sn with diagonal entries si=±1 such that M2=SM1S. Notice that two signature similar matrices have the same eigenvalues. From the definitions of switching equivalent and signature similar, we have the following.Lemma 1.
SupposeΓ1=G,σ1 and Γ2=G,σ2 be two signed graphs on the same underlying graph G; then, Γ1∼Γ2 if and only if LΓ1 and LΓ2 are signature similar.Signed graphs were first introduced by HARARY, in [1], in connection with the study of the theory of social balance in social psychology, see [2]. After that, there are many works on signed graph, see [3–5].The energy of unsigned graphG [6–8] is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. The Laplacian energy of a graph G [9] is defined as LEG=∑i=1nλiG−d¯G, where λ1G≥λ2G≥⋯≥λnG=0 are the eigenvalues of Laplacian matrix of G, d¯G=2mG/n is the average degree of G. For its basic properties, see [10–15]. The signless Laplacian energy of a graph G is defined as QEG=∑i=1nqiG−d¯G, where q1G≥q2G≥⋯≥qnG are the eigenvalues of signless Laplacian matrix of G.The Laplacian energy of a signed graphΓ, see [16], is defined similarly as LEΓ=∑i=1nλiΓ−d¯Γ, where λ1Γ≥λ2Γ≥⋯≥λnΓ are the eigenvalues of Laplacian matrix of Γ and d¯Γ is the average degree of Γ, which is the same as that of G, so we will denote it by d¯ simply.Two (signed) graphs of the same order are said to be Laplacian equienergetic if they have the same Laplacian energy. Two (signed) graphs are said to be Laplacian cospectral if they have the same Laplacian eigenvalues. From Lemma1, we know that switching equivalent signed graphs must be Laplacian cospectral and Laplacian equienergetic.Finding Laplacian equienergetic graphs is interesting, and there are so many research works on Laplacian equienergetic unsigned graphs already, see [17–20], for example, but it is very few on signed ones. In this paper, we present several infinite families of Laplacian equienergetic signed graphs which are not Laplacian cospectral.


## 2. Main Results

It seems more difficult to find Laplacian equienergetic signed graphs than unsigned ones, since we know too little about Laplacian spectrum of signed graphs. It is known that an unsigned graph could be considered as an all-positive signed graph; therefore, two Laplacian equienergetic unsigned graphs is also a pair of Laplacian equienergetic signed ones. And, we will not deal with this case.In the paper, we try to find Laplacian equienergetic signed graph pairs with common underlying graph. That is, we are interested in graphsG which satisfy LEG,σ1=LEG,σ2. At first, we consider graphs which satisfy LEG,+=LEG,−; in other words, we consider graphs which satisfy LEG=QEG. In fact, there are such graphs trivially. It is well known that, for a regular graph, LEG=QEG holds. Besides, for bipartite graphs, the Laplacian spectrum coincides with the signless Laplacian spectrum; obviously, in this case, we have LEG=QEG also. Now, we present two infinite families of connected nonregular and nonbipartite such graphs.LetG1▽G2 denote the join of graphs G1 and G2, obtained from the union of G1 and G2 by joining every vertex of G1 with every vertex of G2. The following lemma is from [21].Lemma 2.
LetG1 and G2 be graphs on n1 and n2 vertices, respectively. Let L1 and L2 be the Laplacian matrices for G1 and G2, respectively, and let L be the Laplacian matrix for G1▽G2. If α1≥α2≥⋯≥αn1=0 and β1≥β2≥⋯≥βn2=0 are the eigenvalues of L1 and L2, respectively, then the eigenvalues of L are n1+n2,n1+β1,n1+β2,…,n1+βn2−1,n2+α1,n2+α2,…,n2+αn1−1,0.The first family of such graphs is from [22].Theorem 3.
For each integerp≥1, unsigned graph G≅K1▽K3∪pK2 satisfying LEG=QEG.The second family of such graphs is as follows.Theorem 4.
For each integerp≥3, unsigned graph G≅K2▽pK2 satisfying LEG=QEG.Proof.
On the one hand, by Lemma2, the Laplacian spectrum of K2▽pK2 is 2p+22,4p,2p−1,0. Noting that its average degree is d¯=5p+1/p+1, it can be easily verified that LEK2▽pK2=42p2−p+1/p+1.
On the other hand, the signless Laplacian matrix ofK2▽pK2 with suitable labeling has the form (with zeros omitted)(2)QK2▽pK2=2p+111⋯⋯1112p+11⋯⋯111131⋮⋮133113⋱⋮⋮311113.
Thus, its signless Laplacian characteristic polynomial isQK2▽pK2−xI=(3)2p+1−x11⋯⋯1112p+1−x1⋯⋯11113−x1⋮⋮13−x3−x113−x⋱⋮⋮3−x11113−x.
PerformingC1−1/4−xC3+⋯+Cn and C2−1/4−xC3+⋯+Cn where Ci is the i-th column of the above determinant, then according to the Laplace theorem, expand the resulting determinant along the first two columns we obtain QK2▽pK2−xI=2p+4−x2p−x4−xp−12−xp+1. Therefore its signless Laplacian spectrum is 2p+4,2p,4p−1,2p+1. By direct computation, we get QEK2▽pK2=42p2−p+1/p+1. Thus, LEK2▽pK2=QEK2▽pK2. This completes the proof.In the sequel, we consider graphs satisfyingLEG,σ=LEG,+. We should point out that, by the definition of Laplacian energy of a (signed) graph, when computing its Laplacian energy, it suffices to know its Laplacian eigenvalues greater than its average degree.Lemma 5.
SupposeΓ has exactly k Laplacian eigenvalues greater than average degree d¯, that is, λ1Γ≥⋯≥λkΓ>d¯≥λk+1Γ≥⋯≥λnΓ; then, LEΓ=2∑i=1kλiΓ−d¯. Besides, if two signed graphs Γ1=G,σ1 and Γ2=G,σ2 both have k Laplacian eigenvalues greater than d¯ and the same sum of first k-greatest Laplacian eigenvalues, then Γ1 and Γ2 are Laplacian equienergetic.Proof.
Notice that∑i=1nλiΓ=2mΓ and d¯=2mΓ/n; by the definition of Laplacian energy,(4)LEΓ=∑i=1nλiΓ−d¯=∑i=1nλiΓ−d¯+∑i=k+1nd¯−λiΓ=∑i=1nλiΓ−d¯+n−kd¯−∑i=k+1nλiΓ=∑i=1nλiΓ−d¯+nd¯−kd¯−2mΓ−∑i=1kλiΓ=2∑i=1nλiΓ−d¯.
The rest of the lemma is obvious.Theorem 6.
For each odd integern=2k+1,k≥2, let G≅K2▽Hk∪k−1K1, where Hk is an arbitrary graph on k vertices (connected or disconnected), the sign function σ specifiess exactly k edges to be negative: the only edge of K2; k−1 edges connect one vertex of K2 to k−1 distinct isolated vertices K1s. And, all remaining edges are positive; then, G satisfies LEG,σ=LEG,+.Proof.
With suitable labeling of vertices ofG,σ, its Laplacian matrix has the form (with zeros omitted)(5)LG,σ=n−111⋯1−1⋯−11n−1−1⋯−1−1⋯−11−12⋮⋮⋱1−12−1−1⋮⋮2Ik+LHk−1−1.
Thus, its Laplacian characteristic polynomial isLG,σ−xI=(6)n−1−x11⋯1−1⋯−11n−1−x−1⋯−1−1⋯−11−12−x⋮⋮⋱1−12−x−1−1⋮⋮2−xIk+LHk−1−1.
Noting that the row sum of2−xIk+LHk is 2−x, performing C1+C2 and C1+2/2−xCk+2+⋯+Cn, where Ci is the ith column of the determinant, and performing C2+1/2−xC3+⋯+Cn, the resulting determinant is(7)n−x−n−12−x1−x2−x1⋯1−1⋯−1n−x−n−12−xn−1−x−n−22−x−1⋯−1−1⋯−1002−x⋮⋮⋱2−x⋮⋮2−xIk+LHk00.
Now, according to the Laplace theorem, expanding the above determinant along the first two columns, we obtain(8)n−x−n−12−x1−x2−xn−x−n−12−xn−1−x−n−22−x×−11+2+1+2×2−xk−1×2−xIk+LHk.
Suppose the Laplacian spectrum ofHk is α1≥α2≥⋯≥αk=0; then, we have 2−xIk+LHk=∏i=1k2+αi−x; thus, we obtain LG,σ−xI=n+1−xn−1−x1−x22−xn−7/2∏i=1k2+αi−x. Therefore, the Laplacian spectrum of G,σ is n+1,n−1,2+α1,…,2+αk−1,2n−5/2,12.
On the contrary, by Lemma2, we can get the Laplacian spectrum of G,+ is n2,2+α1,…,2+αk−1,2k−1,0. Notice that G,+ and G,σ have the same average degree, which is d¯≥4n−6/n>2, and both have i; for some 2≤i≤k+1, Laplacian eigenvalues are greater than d¯ and the same sum of first i-greatest Laplacian eigenvalues; by Lemma 5, we can conclude that LEG,σ=LEG,+. This completes the proof.Theorem 7.
(1)
For each even integern=4k+2,k≥1, let G≅K3▽Hk−1∪3kK1, where Hk−1 is an arbitrary graph on k−1 vertices (connected or disconnected); the sign function σ specifies exactly 3k edges to be negative, where k edges connecting the ith vertex of K3 to k distinct isolated vertices K1s, i=1,2,3, and all remaining edges are positive; then, G satisfies LEG,σ=LEG,+.(2)
For each even integern=4k,k≥2, let G≅K3▽Hk∪3k−3K1, where Hk is an arbitrary graph on k vertices (connected or disconnected), the sign function σ specifies 3k edges to be negative, where k−1 edges connect the ith vertex of K3 to k−1 distinct isolated vertices K1s, i=1,2,3, the 3 edges of K3. And, all remaining edges are positive; then, G satisfies LEG,σ=LEG,+.Proof.
With suitable labeling of vertices ofG,σ, its Laplacian characteristic polynomial is LG,σ−xI=(9)n−1−x−1−1−1⋯−1︷k−1−1⋯−1︷k−1⋯−1︷k1⋯1︷k−1n−1−x−1−1⋯−1−1⋯−11⋯1−1⋯−1−1−1n−1−x−1⋯−11⋯1−1⋯−1−1⋯−1−1−1−1⋮⋮⋮3−xIk−1+LHk−1−1−1−1−1−113−x⋮⋮⋮⋱−1−11−11−1⋮⋮⋮−11−11−1−1⋮⋮⋮⋱1−1−13−x.
Performing, in turn,C1+1/3−xC4+⋯+C3k+2−C3k+3−⋯−Cn, C2+1/3−xC4+⋯+C2k+2−C2k+3−⋯−C3k+2+C3k+3+⋯+Cn, and C3+1/3−xC4+⋯+Ck+2−Ck+3−⋯−C2k+2+C2k+3+⋯+Cn, where Ci is the ith column of the determinant, up to now, except for the first three rows, all elements of the first three columns are simplified to zero. Then, according to the Laplace theorem, expanding the resulting determinant along the first three columns, we obtain(10)n−2−x−4k−23−x2x−43−xx−23−xn−2−x−4k−23−xn−2−x−4k−23−xx−23−x2x−43−xn−2−x−4k−23−xn−1−x−4k−13−x×3−xIk−1+LHk−1×3−x3k.
Noting thatn=4k+2, the above expression can be simplified as n+1−x2n−2−x2−x33−xIk−1+LHk−13−x3k. Suppose the Laplacian spectrum of Hk−1 is α1≥α2≥⋯≥αk−1=0; then, we have 3−xIk−1+LHk−1=∏i=1k−13+αi−x; consequently, the Laplacian spectrum of G,σ is n+12,n−2,3+α1,…,3+αk−1,33k−3,23.
By Lemma2, we can easily get the spectrum of LG,+ is n3,3+α1,…,3+αk−1,33k−1,0. Notice that G,+ and G,σ have the same average degree, which is d¯≥6n−12/n≥4, and both have i; for some 3≤i≤k+2, Laplacian eigenvalues are greater than d¯ and the same sum of first i-greatest Laplacian eigenvalues; by Lemma 5, we can conclude that LEG,σ=LEG,+. Therefore, case (1) holds.
As for the proof of case (2), it is similar to that of case (1). We just present the Laplacian spectrum ofG,σ, which is n+2,n−12,3+α1,…,3+αk,33k−6,23, and the spectrum of LG,+ is n3,3+α1,…,3+αk,33k−4,0, where α1≥α2≥⋯≥αk=0 is the Laplacian spectrum of Hk. And, it is not difficult to verify that LEG,σ=LEG,+ holds.Theorem 8.
For each even integern=2k+2,k≥2, let G≅K4▽Hk−2∪kK1, where Hk−2 is an arbitrary graph on k−2 vertices (connected or disconnected); the sign function σ specifies exactly 2k edges to be negative, where 2k edges connect two vertices of K4 to k distinct isolated vertices K1s, and all remaining edges are positive; then, G satisfies LEG,σ=LEG,+.Proof.
The proof of Theorem8 is similar to that of Theorem 6. We just present the Laplacian spectrum of G,σ, which is n+2,n2,n−2,4+α1,…,4+αk−2,4k−2,22, where α1≥α2≥⋯≥αk−2=0, is the Laplacian spectrum of Hk−2. While the Laplacian spectrum of G,+ is n4,4+α1,…,4+αk−2,4k−1,0, and it is not difficult to verify that LEG,σ=LEG,+ holds.Example 1.
We give four instances with propertyLEG,σ=LEG,+ corresponding to Theorems 6, 7 (1) and (2), and 8, respectively, see Figure 1, where bold lines denote positive edges and dotted lines denote negative edges. G1≅K2▽S3∪2K1, G2≅K3▽K2∪9K1, G3≅K3▽K3∪6K1, and G4≅K4▽S3∪5K1. Their Laplacian spectra are shown in Table 1.Figure 1
Examples in theorems.Table 1
The Laplacian spectra in examples.
G1,σ1:8,6,5,3,2,12G1,+:72,5,3,22,0LE=110/7G2,σ2:152,12,5,37,23G2,+:143,5,39,0LE=366/7G3,σ3:14,112,62,34,23G3,+:123,62,36,0LE=41G4,σ4:14,122,10,7,5,44,22G4,+:124,7,5,45,0LE=130/3



---

*Source: 5029807-2021-10-28.xml*