ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P1.06 / 99–113
https://doi.org/10.26493/1855-3974.2332.749
(Also available at http://amc-journal.eu)
Cospectrality of multipartite graphs*
Alireza Abdollahi , Niloufar Zakeri
Department of Pure Mathematics, Faculty of Mathematics and Statistics,
University of Isfahan, Isfahan 81746-73441, Iran
Received 10 May 2020, accepted 11 June 2021, published online 14 June 2022
Abstract
Let G be a graph on n vertices and consider the adjacency spectrum of G as the or-
dered n-tuple whose entries are eigenvalues of G written decreasingly. Let G and H be
two non-isomorphic graphs on n vertices with spectra S and T , respectively. Define the
distance between the spectra of G and H as the distance of S and T to a norm N of the
n-dimensional vector space over real numbers. Define the cospectrality of G as the min-
imum of distances between the spectrum of G and spectra of all other non-isomorphic n
vertices graphs to the norm N . In this paper we investigate copsectralities of the cocktail
party graph and the complete tripartite graph with parts of the same size to the Euclidean
or Manhattan norms.
Keywords: Spectra of graphs, cospectrality of graphs, adjacency matrix of a graph, Euclidean norm,
Manhattan norm.
Math. Subj. Class. (2020): 05C50, 05C31
1 Introduction and results
All graphs considered here are simple, that is finite and undirected without loops and mul-
tiple edges. Let G be a graph with vertex set {v1, . . . , vn}. The adjacency matrix of G is
an n × n matrix A(G) = [aij ] such that aij = 1 if vi and vj are adjacent, and aij = 0
otherwise. By the eigenvalues of G, we mean those of its adjacency matrix. We denote by
Spec(G) the multiset of the eigenvalues of the graph G.
Richard Brualdi proposed in [24] the following problem:
Problem ([24, Problem AWGS.4]). Let Gn and G′n be two non-isomorphic graphs on n
vertices with spectra
λ1 ≥ λ2 ≥ · · · ≥ λn and λ′1 ≥ λ′2 ≥ · · · ≥ λ′n,
*The authors are grateful to the referee for his/her helpful comments.
E-mail addresses: a.abdollahi@math.ui.ac.ir (Alireza Abdollahi), zakeri@sci.ui.ac.ir (Niloufar Zakeri)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
100 Ars Math. Contemp. 22 (2022) #P1.06 / 99–113
respectively. Define the distance between the spectra of Gn and G′n as
λ(Gn, G
′
n) =
n∑
i=1
(λi − λ′i)2
(
or use
n∑
i=1
|λi − λ′i|
)
.
Define the cospectrality of Gn by
cs(Gn) = min{λ(Gn, G′n) : G′n not isomorphic to Gn}.
Let
csn = max{cs(Gn) : Gn a graph on n vertices}.
This function measures how far apart the spectrum of a graph with n vertices can be from
the spectrum of any other graph with n vertices.
Problem A. Investigate cs(Gn) for special classes of graphs.
Problem B. Find a good upper bound on csn.
In [15], Jovanović et al. studied the spectral distance between certain graphs to the
ℓ1-norm i.e. σ(Gn, G′n) =
∑n
i=1 |λi − λ′i|. In [1], Abdollahi et al. completely answered
Problem B to any ℓp-norm by proving that csn = 2 for all n ≥ 2, whenever 1 ≤ p < ∞
and csn = 1 to the ℓ∞-norm. In [2, 20], the authors studied Problem A to the Euclidean
norm (the ℓ2-norm) and determined the cospectralities of classes of complete graphs and
complete bipartite graphs. In [3] we compute the cospectralities to the ℓ1-norm of complete
graphs and complete bipartite graphs with parts of the same size. In [4, 10, 11, 13, 14, 16,
17, 18], Problems A or B are studied based on different matrix representations. To find
some applications of the cospectrality of graphs, we refer to [6, 25, 27].
In this paper we study Problem A and investigate the cospectralities of CPn and Kn,n,n,
(n ≥ 3), to the ℓ1- and ℓ2-norms i.e. σ(Gn, G′n) =
∑n
i=1 |λi − λ′i| and λ(Gn, G′n) =∑n
i=1(λi − λ′i)2, respectively. We find some conditions for the eigenvalues of a graph H
such that cs(G) = σ(G,H) and G is isomorphic to CPn or Kn,n,n. Also we give some
computational results and conjectures to find cs(CPn) and cs(Kn,n,n).
In the last section we consider cospectralities of null graphs, complete graphs and com-
plete bipartite graphs using the ℓp-norm for p > 2 and we see that similar known conclu-
sions using with ℓ1 and ℓ2-norms (see [2, 3, 11, 20]) hold more or less valid.
Let us first introduce some notations. For a graph G, V (G) and E(G) denote the vertex
set and edge set of G, respectively; By the order of G we mean the number of vertices;
Denote by G the complement of G. The degree of a vertex of a graph is the number of
edges that are incident with the vertex and ∆ is the maximum degree of the vertices. An
r-regular graph is a graph where all vertices have degree r.
For two graphs G and H with disjoint vertex sets, G + H denotes the graph with the
vertex set V (G) ∪ V (H) and the edge set E(G) ∪ E(H), i.e. the disjoint union of two
graphs G and H . The complete product (join) G∇H of graphs G and H is the graph
obtained from G +H by joining every vertex of G with every vertex of H . In particular,
nG denotes G+ · · ·+G︸ ︷︷ ︸
n
and ∇nG denotes G∇ · · ·∇G︸ ︷︷ ︸
n
. The coalescence G·H is obtained
by the disjoint union of two graphs G and H by identifying a vertex u of G with a vertex v
of H .
A. Abdollahi and N. Zakeri: Cospectrality of multipartite graphs 101
For positive integers n1, . . . , nℓ, Kn1,...,nℓ denotes the complete multipartite graph with
ℓ parts of sizes n1, . . . , nℓ. Let Kn denote the complete graph on n vertices, nK1 = Kn
denote the null graph on n vertices and Pn denote the path with n vertices. The cocktail
party graph CPn has 2n vertices and it is a complement of nK2. So for n = 1, CP1 = K1,1
and for n ≥ 2 we have CPn = K2, . . . , 2︸ ︷︷ ︸
n
.
Since CPn and Kn,n,n are regular graphs, by Propositions 3 and 6 of [9], CPn and
Kn,n,n are determined by their spectrum. So we can compute the values of cs(CPn) and
cs(Kn,n,n).
Our main results are as follows.
Theorem 1.1. If n ≥ 2 and cs(CPn) = σ(CPn, H) for some graph H with eigenvalues
λ1 ≥ · · · ≥ λ2n, then
(1) If H is a connected graph, then 2n− 3 ≤ λ1 < 2n− 1. Otherwise 2n− 3 ≤ λ1 <
2n− 2 and H has two connected components such that one of them is K1.
(2) 0 ≤ λ2 ≤ 1,
(3) −1 ≤ λi ≤ 12 , for any integer i, 3 ≤ i ≤ n+ 1, and if n ≥ 13, then 0 ≤ λ3 ≤
1
2 ,
(4) −3 ≤ λn+2 ≤ −1,
(5) −3 ≤ λi ≤ −32 , for any integer i, n+ 3 ≤ i ≤ 2n.
Theorem 1.2. Let n ≥ 4 and cs(Kn,n,n) = σ(Kn,n,n, H) for some graph H with eigen-
values λ1 ≥ · · · ≥ λ3n. For all ε > 0, there exists N ∈ N such that for all n ≥ N , we
have
(1) 2n−
√
3
3 −
ε
2 < λ1 < 2n+
√
3
3 +
ε
2 ,
(2)
√
2−1 < λ2 <
√
3
3 +
ε
2 or λ2 = 0 and H
∼= tK1+Kp,q,r for some positive integers
p, q and r such that at least one of them is greater than 1,
(3) 0 ≤ λ3 <
√
3
6 +
ε
4 ,
(4) −
√
3
3 −
ε
2 < λi <
√
3
6 +
ε
4 , for any integer i, 4 ≤ i ≤ 3n− 2,
(5) −n−
√
3
3 −
ε
2 < λ3n−1 < −n+
√
3
3 +
ε
2 ,
(6) −n−
√
3
3 −
ε
2 < λ3n < −n+
√
3
6 +
ε
4 .
2 Cospectrality of cocktail party graphs
In this section cs(CPn) is investigated to the ℓ1- and ℓ2-norms. We need the following
results in the sequel. The proofs of next two results are similar to those of Lemma 2.2 and
Corollary 2.3 of [18]. We give them here for the reader’s convenience.
Lemma 2.1. Let a1 ≥ a2 ≥ · · · ≥ an and b1 ≥ b2 ≥ · · · ≥ bn be two sequences with∑n
i=1 ai =
∑n
i=1 bi = 0. If there exist some 1 ≤ j ≤ n and a real positive number α such
that |aj − bj | > α, then
∑n
i=1 |ai − bi| > 2α.
102 Ars Math. Contemp. 22 (2022) #P1.06 / 99–113
Proof. Without loss of generality, we may assume that aj − bj > α. Suppose that ai1 ≥
bi1 , . . . , ais ≥ bis and ais+1 ≤ bis+1 , . . . , ain ≤ bin , then
n∑
i=1
|ai − bi| =
s∑
t=1
(ait − bit) +
n∑
t=s+1
(bit − ait)
= 2
s∑
t=1
(ait − bit)
≥ 2(aj − bj)
> 2α.
Corollary 2.2. Let a1 ≥ a2 ≥ · · · ≥ an and b1 ≥ b2 ≥ · · · ≥ bn be two sequences with∑n
i=1 ai =
∑n
i=1 bi = 0. If there exist 1 ≤ j1 ̸= j2 ≤ n and a real positive number α
such that aj1 − bj1 + aj2 − bj2 > α, then
∑n
i=1 |ai − bi| > 2α.
Proof. If either aj1 − bj1 > α or aj2 − bj2 > α, then by Lemma 2.1, the result holds. So
we may assume that 0 < aj1 − bj1 ≤ α and 0 < aj2 − bj2 ≤ α. Let a′j1 = aj1 + aj2 ,
b′j1 = bj1 + bj2 , a
′
i = ai and b
′
i = bi for i ̸= j1, j2. So
∑n
i=1,i̸=j2
a′i =
∑n
i=1,i̸=j2
b′i = 0
and a′j1 − b
′
j1
> α. Thus the result follows from Lemma 2.1.
Theorem 2.3. Let G be a graph with eigenvalues λ1 ≥ · · · ≥ λn. If cs(G) = σ(G,H) for
some graph H with eigenvalues λ′1 ≥ · · · ≥ λ′n, then for all integers i and j, 1 ≤ j < i ≤
n,
(1) |λi − λ′i| ≤ 1,
(2) λi − λ′j ≤ 12 .
Proof. By Theorem 1.1 of [1], csn = 2 for all n ≥ 2, so cs(G) ≤ 2. Now the result follows
from Lemma 2.1 and Corollary 2.2.
Theorem 2.4 ([5, Theorem 1]). Let G be a simple graph of order n without isolated ver-
tices. If λ2(G) is the second largest eigenvalue of G, then
(1) λ2(G) = −1 if and only if G is a complete graph with at least two vertices,
(2) λ2(G) = 0 if and only if G is a complete k-partite graph with 2 ≤ k ≤ n− 1,
(3) there exists no graph G such that −1 < λ2(G) < 0.
Theorem 2.5 ([21, Theorem 3.8]). Let G be a graph of order n. If λ3(G) < 0, then G has
at least n− 12 eigenvalues −1.
Theorem 2.6 ([7, Theorem 3.2.1]). Let λ1 be the greatest eigenvalue of the graph G, and
let d and ∆ be its average degree and maximum degree, respectively. Then
d ≤ λ1 ≤ ∆.
Moreover, d = λ1 if and only if G is regular. For a connected graph G, λ1 = ∆ if and only
if G is regular.
A. Abdollahi and N. Zakeri: Cospectrality of multipartite graphs 103
Proof of Theorem 1.1. Since
Spec(CPn) = {2n− 2, 0, . . . , 0︸ ︷︷ ︸
n
,−2, . . . ,−2︸ ︷︷ ︸
n−1
},
we have
σ(CPn, H) = |2n− 2− λ1|+
n+1∑
i=2
|λi|+
2n∑
i=n+2
|2 + λi|.
If cs(CPn) = σ(CPn, H), then by Theorem 1.1 of [1], cs(CPn) ≤ 2. By Theorems 2.3,
2.4, 2.5 and Corollary 2.2, we obtain (2) – (5) and 2n− 3 ≤ λ1 ≤ 2n− 1.
If H is a connected graph and λ1 = 2n − 1, then by Theorem 2.6, H ∼= K2n, a
contradiction. So 2n − 3 ≤ λ1 < 2n − 1. Now suppose that H is not connected. Let
H1, . . . ,Hk be the connected components of H . There exists an unique i, 1 ≤ i ≤ k,
such that λ1(H) = λ1(Hi). We can assume that λ1(H) = λ1(H1). Thus λ1(Hj) ≤
λ2(H) ≤ 1, for every j, 2 ≤ j ≤ k. So λ1(Hj) = 0 or λ1(Hj) = 1, 2 ≤ j ≤ k.
Since −1 ≤ λ3(H) ≤ 12 , there exists at most one connected component with λ1(Hj) = 1,
2 ≤ j ≤ k. Therefore H ∼= H1 + tK1 or H ∼= H1 +K2 + sK1, for some integers t > 0
and s ≥ 0. By Theorem 2.6, 2n − 3 ≤ λ1(H) = λ1(H1) ≤ ∆ ≤ 2n − 1, where ∆ is the
maximum degree of the vertices of H . If ∆ = 2n− 1, then, by Theorem 2.6, H1 ∼= K2n, a
contradiction. Let ∆ = 2n− 3. Therefore by Theorem 2.6, H1 ∼= K2n−2, a contradiction.
Now suppose that ∆ = 2n− 2. If λ1(H1) = 2n− 2, then by Theorem 2.6, H1 ∼= K2n−1,
a contradiction. Hence we can assume that H ∼= H1 +K1 and 2n− 3 ≤ λ1(H) < 2n− 2.
This completes the proof.
Remark 2.7. Let H be a connected graph with m edges. If cs(CPn) = σ(CPn, H), then,
by Theorem 1.1 and Theorem 1 in [26], it is not hard to see that 2n2 − 5n + 4 ≤ m <
2n2 − n.
Now we find σ(CPn, (CPn−1 ▽ K1) · K2) and λ(CPn, CPn \ e) and propose two
conjectures. We need the following results.
Theorem 2.8 ([7, Theorem 2.1.8]). If G1 is r1-regular with n1 vertices, and G2 is r2-
regular with n2 vertices, then the characteristic polynomial of the join G1 ▽ G2 is given
by
PG1▽G2(x) =
PG1(x)PG2(x)
(x− r1)(x− r2)
((x− r1)(x− r2)− n1n2).
Theorem 2.9 ([7, Theorem 2.2.3]). Let G ·H be the coalescence in which the vertex u of
G is identified with the vertex v of H . Then
PG·H(x) = PG(x)PH−v(x) + PG−u(x)PH(x)− xPG−u(x)PH−v(x).
Lemma 2.10. If (CPn−1 ▽K1) ·K2 is the coalescence of K2 with CPn−1 ▽K1 with its
vertex of maximum degree as distinguished vertex, then for n ≥ 3,
Spec((CPn−1 ▽K1) ·K2) = {x1, x2, 0, . . . , 0︸ ︷︷ ︸
n−1
, x3,−2, · · · ,−2︸ ︷︷ ︸
n−2
},
such that x1 > x2 > 0 > x3 are the roots of the polynomial x3 + (4 − 2n)x2 +
(1− 2n)x+ 2n− 4.
104 Ars Math. Contemp. 22 (2022) #P1.06 / 99–113
Proof. Since PCPn−1(x) = x
n−1(x+ 2)n−2(x− 2n+ 4) and PK1(x) = x, Theorem 2.8
implies that
PCPn−1▽K1(x) = x
n−1(x+ 2)n−2(x2 + (4− 2n)x+ 2− 2n).
Since PK2(x) = x
2 − 1, it follows from Theorem 2.9,
P(CPn−1▽K1)·K2(x) = x
n−1(x+ 2)n−2(x3 + (4− 2n)x2 + (1− 2n)x+ 2n− 4).
Thus (CPn−1 ▽ K1) · K2 has n − 1 and n − 2 eigenvalues 0 and −2, respectively. The
remaining eigenvalues are the roots of the polynomial x3+(4−2n)x2+(1−2n)x+2n−4.
If
a =
(
8n3 − 30n2 + 24n+ 8 + 3(−60n4 + 312n3 − 648n2 + 606n− 237)
1
2
) 1
3
,
b = −4
9
n2 +
10
9
n− 13
9
,
r =
(
(8n3 − 30n2 + 24n+ 8)2 + 540n4 − 2808n3 + 5832n2 − 5454n+ 2133
) 16
,
θ =
1
3
arctan
(
3(60n4 − 312n3 + 648n2 − 606n+ 237)
1
2
8n3 − 30n2 + 24n+ 8
)
.
Then
x1 =
2n
3
− 4
3
+
a
3
− 3b
a
,
x2 =
2n
3
− 4
3
+ (
3b
2r
− r
6
) cos θ −
√
3(
3b
2r
− r
6
) sin θ,
x3 =
2n
3
− 4
3
+ (
3b
2r
− r
6
) cos θ +
√
3(
3b
2r
− r
6
) sin θ.
This completes the proof.
Lemma 2.11. limn−→∞ σ
(
CPn, (CPn−1 ▽K1) ·K2
)
= 2, whenever (CPn−1 ▽K1) ·
K2 is the coalescence of K2 with CPn−1 ▽ K1 with its vertex of maximum degree as
distinguished vertex.
Proof. By Lemma 2.10 and using the symbolic computational software Maple [19] (see
https://data.amc-journal.eu/cospectrality/maplecode1.mw), the result follows.
Theorem 2.12 ([7, Theorem 2.1.5]). Let G, H be graphs with n1, n2 vertices respectively.
The characteristic polynomial of the join G▽H is given by the relation
PG▽H(x) = (−1)n2PG(x)PH(−x− 1) + (−1)
n1PH(x)PG(−x− 1)
− (−1)n1+n2PG(−x− 1)PH(−x− 1).
Lemma 2.13. For n ≥ 3 and any edge e,
Spec(CPn \ e) =
{
x1,
√
5− 1
2
, 0, . . . , 0︸ ︷︷ ︸
n−2
, x2,−
√
5 + 1
2
,−2, . . . ,−2︸ ︷︷ ︸
n−3
, x3
}
,
where x1 > 0 > x2 > x3 are the roots of the polynomial x3 − (2n− 5)x2 − (6n− 9)x−
2n+ 2.
A. Abdollahi and N. Zakeri: Cospectrality of multipartite graphs 105
Proof. For any edge e, CPn \ e = P4 ▽ CPn−2. Let G = P4 and H = CPn−2. Thus
G = G and H = (n− 2)K2. We have
PG(x) = PG(x) = x
4 − 3x2 + 1,
PH(x) = (x− 2n+ 6)xn−2(x+ 2)n−3,
PH(x) = (x
2 − 1)n−2.
Therefore
PCPn\e = PG▽H(x) = x
n−2(x+ 2)
n−3
(x2+x−1)(x3−(2n−5)x2−(6n−9)x−2n+2).
It follows CPn \ e has n− 2 and n− 3 eigenvalues 0 and −2, respectively. The remaining
eigenvalues are
√
5−1
2 , −
√
5+1
2 and the roots of x
3 − (2n− 5)x2 − (6n− 9)x− 2n+ 2. If
a =
(
64n3 − 48n2 − 312n+ 404
+ 12(−240n4 + 528n3 + 396n2 − 1740n+ 1137) 12
) 1
3 ,
b = −4
9
n2 +
2
9
(n+ 1),
r =
(
(64n3 − 48n2 − 312n+ 404)2
+ 34560n4 − 76032n3 − 57024n2 + 250560n− 163728
) 1
6 ,
θ =
1
3
arctan
(
12(240n4 − 528n3 − 396n2 + 1740n− 1137)
1
2
64n3 − 48n2 − 312n+ 404
)
.
Then
x1 =
2n
3
− 5
3
+
a
6
− 6b
a
,
x2 =
2n
3
− 5
3
+ (
3b
r
− r
12
) cos θ −
√
3(
3b
r
− r
12
) sin θ,
x3 =
2n
3
− 5
3
+ (
3b
r
− r
12
) cos θ +
√
3(
3b
r
− r
12
) sin θ,
and we are done.
Lemma 2.14. limn−→∞ λ(CPn, CPn \ e) = 10− 4
√
5.
Proof. By Lemma 2.13 and using the symbolic computational software Maple [19] (see
https://data.amc-journal.eu/cospectrality/maplecode2.mw), the result follows.
We have the following conjectures:
Conjecture 2.15. For every integer n ≥ 2, cs(CPn) = σ(CPn, H) for some graph H if
and only if H ∼= (CPn−1 ▽K1) ·K2, whenever (CPn−1 ▽K1) ·K2 is the coalescence of
K2 with CPn−1 ▽K1 with its vertex of maximum degree as distinguished vertex.
Conjecture 2.16. For every integer n ≥ 4, cs(CPn) = λ(CPn, H) for some graph H if
and only if H ∼= CPn \ e, for any edge e.
For n = 2 and n = 3, cs(CPn) = λ(CPn, H) if and only if H ∼= (CPn−1▽K1) ·K2.
Our computational results confirm Conjectures 2.15 and 2.16 for all graphs of order at most
10.
106 Ars Math. Contemp. 22 (2022) #P1.06 / 99–113
3 Cospectrality of complete tripartite graphs
In this section we investigate cs(Kn,n,n), for n ≥ 3, to the ℓ1- and ℓ2-norms. First we need
the following results.
Theorem 3.1 ([12, Theorem 9.1.1]). Let G be a graph of order n and H be an induced
subgraph of G with order m. Suppose that λ1(G) ≥ · · · ≥ λn(G) and λ1(H) ≥ · · · ≥
λm(H) are the eigenvalues of G and H , respectively. Then for every i, 1 ≤ i ≤ m,
λi(G) ≥ λi(H) ≥ λn−m+i(G).
Theorem 3.2 (See [23] and also [8, Theorem 6.7]). A graph has exactly one positive eigen-
value if and only if its non-isolated vertices form a complete multipartite graph.
Lemma 3.3 ([22, Lemma 7]). λ2((K1 +Kr,s)∇Kq) ≤
√
2− 1 (r ≤ s) if and only if one
of the conditions 1− 10 holds:
(1) r > 1, s ≥ r, q = 1;
(2) r = 1, s ≥ 1, q ≥ 2;
(3) r = 2, s ≥ 2, q = 2;
(4) r = 2, 2 ≤ s ≤ 3, q ≥ 3;
(5) r = 2, s = 4, 3 ≤ q ≤ 7;
(6) r = 2, s = 5, 3 ≤ q ≤ 4;
(7) r = 2, 6 ≤ s ≤ 8, q = 3;
(8) r = 3, s = 3, 2 ≤ q ≤ 4;
(9) r = 3, 4 ≤ s ≤ 7, q = 2;
(10) r = 4, s = 4, q = 2.
Lemma 3.4 ([22, Lemma 8]). λ2((K1 +Kr,s)∇Kp,q) ≤
√
2 − 1 (r ≤ s, p ≤ q) if and
only if one of the conditions 1− 5 holds:
(1) r = 1, s = 1, p ≥ 1, q ≥ p;
(2) r = 1, s = 2, 1 ≤ p ≤ 2, q ≤ p;
(3) r = 1, s = 2, p = 3, 3 ≤ q ≤ 7;
(4) r = 1, s = 2, p = 4, q = 4;
(5) r = 1, s = 3, p = 1, q = 1.
Theorem 3.5 ([22, Theorem]). Let G be a graph without isolated vertices and let λ2(G)
be the second largest eigenvalue of G. Then 0 < λ2(G) ≤
√
2− 1 if and only if one of the
following holds:
(1) G ∼= (∇t(K1 +K2))∇Kn1,...,nm ,
(2) G ∼= (K1 + Kr,s)∇Kq, and parameters q, r and s satisfy one of the conditions
(1) – (10) from Lemma 3.3,
(3) G ∼= (K1 +Kr,s)∇Kp,q, and parameters p, q, r and s satisfy one of the conditions
(1) – (5) from Lemma 3.4.
Lemma 3.6. Let n ≥ 3 and x1 > 0 > x2 > x3 be the roots of the polynomial x3 −
(3n2 − 1)x− 2n3 + 2n. Then
Spec(Kn−1,n,n+1) = {x1, 0, . . . , 0︸ ︷︷ ︸
3n−3
, x2, x3}.
A. Abdollahi and N. Zakeri: Cospectrality of multipartite graphs 107
Proof. Since PKn1,...,nk (x) = x
∑k
i=1 ni−k
(
1−
∑k
i=1
ni
x+ni
)∏k
i=1(x+ ni),
PKn−1,n,n+1(x) = x
3n−3(x3 − (3n2 − 1)x− 2n3 + 2n).
Thus Kn−1,n,n+1 has 3n− 3 eigenvalues 0 and 3 eigenvalues
x1 =
a2 + 9n2 − 3
3a
,
x2 =
(
−r
6
+
1− 3n2
2r
)
cos θ −
√
3
(
−r
6
+
1− 3n2
2r
)
sin θ,
x3 =
(
−r
6
+
1− 3n2
2r
)
cos θ +
√
3
(
−r
6
+
1− 3n2
2r
)
sin θ,
where
a =
(
27n3 − 27n+ 3(−81n4 + 54n2 + 3)
1
2
) 1
3
,
r =
(
(27n3 − 27n)2 + 729n4 − 486n2 − 27
) 1
6
,
θ =
1
3
arctan
(
(81n4 − 54n2 − 3)
1
2
9n3 − 9n
)
.
Lemma 3.7. limn−→∞ σ(Kn,n,n,Kn−1,n,n+1) = 2
√
3
3 .
Proof. Since Spec(Kn,n,n) = {2n, 0, . . . , 0︸ ︷︷ ︸
3n−3
,−n,−n}, by Lemma 3.6 and using the com-
putational software Maple [19] (see https://data.amc-journal.eu/cospectrality/
maplecode3.mw), the result follows.
Proof of Theorem 1.2. Note that
σ(Kn,n,n, H) = |2n− λ1|+
3n−2∑
i=2
|λi|+ |n+ λ3n−1|+ |n+ λ3n|.
By Lemma 3.7, for all ε > 0, there exists N ∈ N such that for all n ≥ N , cs(Kn,n,n) <
2
√
3
3 + ε. By Lemma 2.1, Corollary 2.2, Theorems 2.4 and 2.5, we obtain (1), (3) – (6) and
0 ≤ λ2 <
√
3
3 +
ε
2 . Suppose that 0 < λ2 ≤
√
2− 1. Hence Theorem 3.5 can be applied.
Case 1: H ∼= (∇t(K1 +K2))∇Kn1,...,nm . If t ≥ 2, then (K1 +K2)∇(K1 +K2) is an
induced subgraph of H . Since
Spec((K1 +K2)∇(K1 +K2)) = {3.73205, .41421, .26795,−1,−1,−2.41421},
by Theorem 3.1, λ3n−2 ≤ −1, a contradiction. Now, suppose that t = 1. If m =
1, then H ∼= (K1 + K2)∇K3n−3. We have PH(x) = x3n−4f(x), whenever f(x) =
108 Ars Math. Contemp. 22 (2022) #P1.06 / 99–113
x4 − (9n− 8)x2 − (6n− 6)x+3n− 3. So the non-zero eigenvalues of H are the roots of
f(x) = 0. By computing the roots, it implies that λ3n−1 = −1, a contradiction. Therefore
m ≥ 2. If n1 = · · · = nm = 1, then H ∼= (K1 +K2)∇K3n−3. So (K1 +K2)∇K2 is an
induced subgraph of H . Since
Spec((K1 +K2)∇K2) = {3.32340, .35793,−1,−1,−1.68133},
by Theorem 3.1, λ3n−2 ≤ −1, a contradiction. Now, we can assume that ni ≥ 2, for some
1 ≤ i ≤ m. Thus (K1 +K2)∇K1,2 is an induced subgraph of H . Since
Spec((K1 +K2)∇K1,2) = {4.06779, .36162, 0,−1,−1.24464,−2.18477},
by Theorem 3.1, λ3n−2 ≤ −1, a contradiction.
Case 2: H ∼= (K1 + Kr,s)∇Kq and parameters q, r and s satisfy conditions 1–10 from
Lemma 3.3. We have PH(x) = x3n−4f(x) whenever f(x) = x4− (q+ qr+ qs+ rs)x2−
2qrsx + qrs. The non-zero eigenvalues of H are determined by equation f(x) = 0. By
computing the roots, we have λ1 = −λ3n and λ2 = −λ3n−1, a contradiction.
Case 3: H ∼= (K1 +Kr,s)∇Kp,q , and parameters p, q, r and s satisfy conditions 1–5 from
Lemma 3.4. In this case, H can be isomorphic to one of these graphs: (K1+K1,2)∇K3,5,
(K1 +K1,2)∇K4,4 and (K1 +K1,1)∇Kp,q whenever q ≥ p ≥ 1 and p+ q = 3n− 3. All
of these graphs have (K1 +K1,1)∇K1,2 as an induced subgraph. Since
Spec((K1 +K1,1)∇K1,2) = {4.06779, .36162, 0,−1,−1.24464,−2.18477},
by Theorem 3.1, λ3n−2 ≤ −1, a contradiction.
So
√
2 − 1 < λ2 <
√
3
3 +
ε
2 or λ2 = 0. If λ2 = 0, then, by Theorem 3.2, there are
some positive integers k, n1, . . . , nk and an integer t ≥ 0 such that H ∼= tK1 +Kn1,...,nk .
If k = 1, then H ∼= K3n, a contradiction. If k = 2, then H ∼= tK1 +Kr,s. Since
Spec(H) = {
√
rs, 0, . . . , 0︸ ︷︷ ︸
3n−2
,−
√
rs},
λ3n−1 = 0, a contradiction. Thus k ≥ 3. Suppose that k ≥ 4. If n1 = · · · = nk = 1, then
H ∼= tK1 +K3n−t. We have
Spec(H) = {3n− t− 1, 0, . . . , 0︸ ︷︷ ︸
t
,−1, . . . ,−1︸ ︷︷ ︸
3n−t−1
}.
Hence λ3n = −1, a contradiction. If there exists an unique i, 1 ≤ i ≤ k, such that ni ≥ 2,
then K1,1,1,2 is an induced subgraph of H . Since
Spec(K1,1,1,2) = {3.64575, 0,−1,−1,−1.64575},
by Theorem 3.1, λ3n−2 ≤ −1, a contradiction. Thus there exist i and j such that ni, nj ≥
2. Hence H has K1,1,2,2 as an induced subgraph. We have
Spec(K1,1,2,2) = {4.37228, 0, 0,−1,−1.37228,−2}.
So by Theorem 3.1, λ3n−2 ≤ −1, a contradiction. Therefore we can assume that k = 3 and
H ∼= tK1+Kp,q,r, for some positive integers p, q and r. If p = q = r = 1, then, by similar
argument given in k ≥ 4, we have λ3n = −1, a contradiction. So H ∼= tK1 +Kp,q,r such
that at least one of p, q and r is greater than 1. This completes the proof.
A. Abdollahi and N. Zakeri: Cospectrality of multipartite graphs 109
Lemma 3.8. limn−→∞ λ(Kn,n,n,Kn−1,n,n+1) = 23 .
Proof. By Lemma 3.6 and using the symbolic computational software Maple [19] (see
https://data.amc-journal.eu/cospectrality/maplecode4.mw), the result follows.
The graph H in Figure 1 is the only unique graph such that σ(K3,3,3, H) and λ(K3,3,3,
H) have the minimum possible values. For n ≥ 4, we have the following conjectures:
Conjecture 3.9. For every integer n ≥ 4, cs(Kn,n,n) = σ(Kn,n,n, H) for some graph H
if and only if H ∼= Kn−1,n,n+1.
Conjecture 3.10. For every integer n ≥ 4, cs(Kn,n,n) = λ(Kn,n,n, H) for some graph
H if and only if H ∼= Kn−1,n,n+1.
Figure 1: The graph which is closest to K3,3,3 both in the ℓ1- and ℓ2-norm.
4 Cospectrality of some families of graphs using ℓp-norm for p > 2
Let p > 2 be an arbitrary positive integer. First we determine the cospectrality of the null
graphs on n vertices.
Theorem 4.1. For every integer n ≥ 2, cs(nK1) = 2. Moreover, cs(nK1) = λ(p)(nK1, H)
for some graph H if and only if H ∼= K2 + (n− 2)K1.
Proof. It is not hard to see that λ(p)(nK1,K2 + (n − 2)K1) = 2. Let H be a simple
graph of order n. Thus cs(nK1) = λ(p)(nK1, H) ≤ 2. So |λ1(H)| ≤ p
√
2, where λ1(H)
is the greatest eigenvalue of H . Since the greatest eigenvalue of a graph is always non-
negative and H ≇ nK1, we have 0 < λ1(H) ≤ p
√
2. Moreover, there is no graph whose
greatest eigenvalue lies in the intervals (0, 1) and (1,
√
2). Hence λ1(H) = 1. Thus
H ∼= K2 + (n− 2)K1.
In the following we show that the minimum value of λ(p)(Kn, H) occurs whenever
H ∼= Kn \ e, where Kn \ e is the graph obtaining from Kn by deletion one edge e. First
we need the following results.
110 Ars Math. Contemp. 22 (2022) #P1.06 / 99–113
Lemma 4.2. λ(p)(K2,K2 \ e) = 2 and for every integer n ≥ 3 and every edge e of Kn,
λ(p)(Kn,Kn \ e) < 2.
Proof. It is easy to see that λ(p)(K2,K2 \ e) = 2. By Corollary 3.4 and Lemma 3.6 in [2],
one can obtain the result.
Theorem 4.3. For every integer n ≥ 2, cs(Kn) = λ(p)(Kn, H) for some graph H if and
only if H ∼= Kn\e for any edge e, where Kn\e is the graph obtaining from Kn by deletion
one edge e.
Proof. For n = 2 and n = 3, It is easy to see that cs(Kn) = λ(p)(Kn,Kn \ e). Let n ≥ 4.
We show that if H is not isomorphic to Kn and Kn \ e, then λ(p)(Kn, H) ≥ 2.
Let λ1 ≥ · · · ≥ λn be the eigenvalues of H . Therefore
λ(p)(Kn, H) = |λ1 − n+ 1|p +
n∑
i=2
|λi + 1|p.
One can obtain this if one of the following cases holds, then λ(p)(Kn, H) ≥ 2.
Case 1: λ1 − n+ 1 ≤ − 3
√
2.
Case 2: λ2 + 1 ≥ 3
√
2.
Case 3: λ3 ≥ 0.
Now suppose that none of the above cases occurs. Thus we can assume that λ1 > n− 1−
3
√
2, λ2 <
3
√
2 − 1 and λ3 < 0. If λ2 ≤ 0, then, by Lemma 3.9 in [2], H ∼= Kn−1 +K1
and λ(p)(Kn, H) = 2.
Now suppose that λ2 > 0. Since 0 < λ2 <
3
√
2 − 1 < 13 , by Theorem 2 in [5], there
exists an integer t such that H ∼= tK1 + (K1 +K2)∇Kn−3−t where 0 ≤ t ≤ n− 4.
If n− 3− t > 1, then (K1 +K2)∇K2 is an induced subgraph of H . Since
Spec((K1 +K2)∇K2) = {2.85577, 0.32164, 0,−1,−2.17741},
by Theorem 3.1, λ3 ≥ 0, a contradiction. If n − 3 − t = 1, then H ∼= (n − 4)K1 +
(K1 +K2)∇K1. Since
Spec(H) = {2.17009, 0.31111, 0, . . . , 0︸ ︷︷ ︸
n−4
,−1,−1.48119},
λ(p)(Kn, H) > 2. Therefore by Lemma 4.2, cs(Kn) = λ(p)(Kn,Kn \ e). This completes
the proof.
In the following, we investigate the cospectrality of complete bipartite graphs. The
proofs of Lemmas 2.5 and 2.7 and Theorem 2.8 in [20] are also working for p > 2, an
arbitrary positive integer. First we need the following results, the "ℓp−version" of Lemmas
2.5 and 2.7 in [20].
Lemma 4.4. Let m and n be two positive integers and G be a graph of order m+ n. If G
has K1,1,2 or (K1 +K2)∇K1 as an induced subgraph, then λ(p)(G,Km,n) ≥ 1.
A. Abdollahi and N. Zakeri: Cospectrality of multipartite graphs 111
Lemma 4.5. Let m and n be two positive integers and G be a graph of order m + n.
Suppose that there are no positive integers r, s and a non-negative integer t such that G ∼=
Kr,s + tK1. If λ2(G) ≤
√
2− 1, then λ(p)(G,Km,n) ≥ 1.
Theorem 4.6. Let m and n be two positive integers such that (m,n) ̸= (1, 1). Then
cs(Km,n) = λ(p)(Km,n,Kr,s + tK1),
for some integers r, s ≥ 1 and t ≥ 0 such that r + s + t = m + n and r, s ̸= m,n.
Moreover, if cs(Km,n) = λ(p)(Km,n, H) for some graph H , then H ∼= Ki,j +hK1, where
i, j ≥ 1 and h ≥ 0 are some integers so that i+ j + h = m+ n.
Proof. It is easy to see that cs(K1,2) = λ(p)(K1,2,K1,1 + K1). So we can assume that
m + n ≥ 4. Let i, j ≥ 1 and h ≥ 0 be some integers such that i + j + h = m + n.
Thus λ(p)(Km,n,Ki,j + hK1) = 2|
√
mn −
√
ij|p. By Lemma 2.4 in [20], there are
some positive integers r and s such that r + s ≤ m + n and {r, s} ≠ {m,n} so that
|
√
mn−
√
rs|p < (
√
2−1√
2
)p. Let t = m+ n− r− s. Hence we obtain λ(p)(Km,n,Kr,s +
tK1) < (
√
2 − 1)p. Therefore cs(Km,n) < (
√
2 − 1)p < 1. Now suppose that H is a
graph such that cs(Km,n) = λ(p)(Km,n, H). Thus λ(p)(Km,n, H) < (
√
2 − 1)p. Let
λ2(H) be the second largest eigenvalue of H . So we have |λ2(H)| <
√
2 − 1. Since
λ(p)(Km,n, H) < 1, by Lemma 4.5, there are some integers r, s ≥ 1 and t ≥ 0 such that
H ∼= Kr,s + tK1. This completes the proof.
Theorem 4.7. Let n ≥ 1 be an integer. Then, the following hold:
(1) cs(K1,1) = λ(p)(K1,1, 2K1) = 2,
(2) cs(K1,2) = λ(p)(K1,2,K1,1 +K1) = 2|
√
2− 1|p,
(3) If n ≥ 3 is a prime number, then
cs(K1,n) = λ(p)(K1,n,K2,n+12 +
n− 3
2
K1) = 2|
√
n+ 1−
√
n|p,
(4) If n ≥ 3 is not a prime number, then
cs(K1,n) = λ(p)(K1,n,Kr,s + (n+ 1− r − s)K1) = 0,
where r and s are some positive integers such that r, s < n and n = rs.
Proof. The method is similar to that of Theorem 2.10 in [20].
By Theorem 4.6, one can easily obtain the following results.
Theorem 4.8. For every integer n ≥ 2, cs(Kn,n) = 2|n−
√
n2 − 1|p. Moreover, cs(Kn,n)
= λ(p)(Kn,n, H) for some graph H if and only if H ∼= Kn−1,n+1.
Theorem 4.9. For every integer n ≥ 2, cs(Kn,n+1) = 2|
√
n2 + n −
√
n2 + n− 2|p.
Moreover, cs(Kn,n+1) = λ(p)(Kn,n+1, H) for some graph H if and only if H ∼= Kn−1,n+2.
ORCID iDs
Alireza Abdollahi https://orcid.org/0000-0001-7277-4855
112 Ars Math. Contemp. 22 (2022) #P1.06 / 99–113
References
[1] A. Abdollahi, S. Janbaz and M. R. Oboudi, Distance between spectra of graphs, Linear Algebra
Appl. 466 (2015), 401–408, doi:10.1016/j.laa.2014.10.020.
[2] A. Abdollahi and M. R. Oboudi, Cospectrality of graphs, Linear Algebra Appl. 451 (2014),
169–181, doi:10.1016/j.laa.2014.02.052.
[3] J. Abdollahi, A. and N. Zakeri, ℓ1-cospectrality of graphs, 2019, arXiv:1907.11874
[math.CO].
[4] M. Afkhami, M. Hassankhani and K. Khashyarmanesh, Distance between the spectra of graphs
with respect to normalized Laplacian spectra, Georgian Math. J. 26 (2019), 227–234, doi:
10.1515/gmj-2017-0051.
[5] D. S. Cao and H. Yuan, Graphs characterized by the second eigenvalue, J. Graph Theory 17
(1993), 325–331, doi:10.1002/jgt.3190170307.
[6] H. Choi, H. Lee, Y. Shen and Y. Shi, Comparing large-scale graphs based on quantum proba-
bility theory, Appl. Math. Comput. 358 (2019), 1–15, doi:10.1016/j.amc.2019.03.061.
[7] D. Cvetković, P. Rowlinson and S. Simić, An introduction to the theory of graph spectra, vol-
ume 75 of London Mathematical Society Student Texts, Cambridge University Press, Cam-
bridge, 2010.
[8] D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs, Theory and Application, Aca-
demic Press, Inc., New York, 1979.
[9] E. R. Van Dam and W. H. Haemers, Which graphs are determined by their spectrum?, Linear
Algebra Appl. 373 (2003), 241–272, doi:10.1016/s0024-3795(03)00483-x.
[10] K. C. Das and S. Sun, Distance between the normalized Laplacian spectra of two graphs, Linear
Algebra Appl. 530 (2017), 305–321, doi:10.1016/j.laa.2017.05.025.
[11] M. Ghorbani and M. Hakimi-Nezhaad, Co-spectrality distance of graphs, J. Inf. Optim. Sci. 40
(2019), 1221–1235, doi:10.1080/02522667.2018.1480464.
[12] C. Godsil and G. Royle, Algebraic graph theory, volume 207 of Graduate Texts in Mathematics,
Springer-Verlag, New York, 2001, doi:10.1007/978-1-4613-0163-9.
[13] J. Gu, B. Hua and S. Liu, Spectral distances on graphs, Discrete Appl. Math. 190/191 (2015),
56–74, doi:10.1016/j.dam.2015.04.011.
[14] M. Hakimi-Nezhaad and A. R. Ashrafi, Laplacian and normalized Laplacian spectral distances
of graphs, Southeast Asian Bull. Math. 37 (2013), 731–744.
[15] I. Jovanović and Z. Stanić, Spectral distances of graphs, Linear Algebra Appl. 436 (2012),
1425–1435, doi:10.1016/j.laa.2011.08.019.
[16] I. Jovanović and Z. Stanić, Spectral distances of graphs based on their different matrix repre-
sentations, Filomat 28 (2014), 723–734, doi:10.2298/fil1404723j.
[17] I. M. Jovanović, Some results on spectral distances of graphs, Rev. Un. Mat. Argentina 56
(2015), 95–117.
[18] H. Lin, D. Li and K. C. Das, Distance between distance spectra of graphs, Linear Multilinear
Algebra 65 (2017), 2538–2550, doi:10.1080/03081087.2017.1278737.
[19] a. d. o. W. M. I. Maplesoft, Maple, computer algebra system, https://www.maplesoft.
com/products/maple/.
[20] M. R. Oboudi, Cospectrality of complete bipartite graphs, Linear Multilinear Algebra 64
(2016), 2491–2497, doi:10.1080/03081087.2016.1162133.
A. Abdollahi and N. Zakeri: Cospectrality of multipartite graphs 113
[21] M. R. Oboudi, On the third largest eigenvalue of graphs, Linear Algebra Appl. 503 (2016),
164–179, doi:10.1016/j.laa.2016.03.037.
[22] M. Petrović, On graphs whose second largest eigenvalue does not exceed
√
2 − 1, Univ.
Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 4 (1993), 70–75.
[23] J. H. Smith, Symmetry and multiple eigenvalues of graphs, Glasnik Mat. Ser. III 12(32) (1977),
3–8.
[24] D. Stevanović, Research problems from the Aveiro Workshop on Graph Spectra, Linear Alge-
bra Appl. 423 (2007), 172–181, doi:10.1016/j.laa.2006.11.027.
[25] R. C. Wilson and P. Zhu, A study of graph spectra for comparing graphs and trees, Pattern
Recognition 41 (2008), 2833–2841, doi:https://doi.org/10.1016/j.patcog.2008.03.011.
[26] H. Yuan, A bound on the spectral radius of graphs, Linear Algebra Appl. 108 (1988), 135–139,
doi:10.1016/0024-3795(88)90183-8.
[27] K. Zając and J. Piersa, Eigenvalue spectra of functional networks in fmri data and artificial
models, in: Artificial Intelligence and Soft Computing, Springer Berlin Heidelberg, 2013 doi:
10.1007/978-3-642-38658-9_19.