EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 17, No. 4, 2024, 3004-3021
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

Relationship Between the Second Largest Adjacency
and Signless Laplacian Eigenvalues of Graphs and

Properties of Planar Graphs

Machasri Manickam1, Kalyani Desikan1,∗

1 Department of Mathematics, School of Advanced Sciences, Vellore Institute of Technology,
Chennai, Tamilnadu, India

Abstract. A graph’s second largest eigenvalue is a significant algebraic characteristic that provides
details on the graph’s expansion, connectivity, and randomness. Bounds for the second largest
eigenvalue of a graph, denoted as λ2 were previously established in the literature in relation to
graph parameters like edge connectivity and vertex connectivity, matching number, independence
number, and edge expansion constant, among others. A graph is planar if it can be drawn in a
plane without graph edges crossing. Determining the planarity of a graph helps in optimizing,
simplifying, and understanding complex systems across various fields. Graph skewness, graph
thickness, and graph crossing number are a few metrics that describe how much a graph deviates
from planarity. In this work, we ascertain the relationship between the graph’s properties, including
graph skewness, thickness, and crossing number, and the graph’s second largest eigenvalues of the
adjacency matrix A(G) and the signless Laplacian matrix Q(G). Based on the skewness, thickness,
and crossing number, we establish a lower bound for the graph’s second largest adjacency and
signless Laplacian eigenvalues. We also determine a lower bound for these graph properties in
terms of the second largest adjacency and signless Laplacian eigenvalues of regular graphs.

2020 Mathematics Subject Classifications: 05C07, 05C10, 05C50

Key Words and Phrases: Second largest eigenvalue, Planar graph, Crossing number, Graph
Thickness, Graph Skewness

1. Introduction

The goal of spectral graph theory, a branch of algebraic graph theory, is to apply ideas
from linear algebra and spectral theory to the study of graph properties. Graphs are rep-
resented as matrices in spectral graph theory, including adjacency, Laplacian and signless
Laplacian matrices. Several structural characteristics and graph properties are analysed
using the eigenvalues and eigenvectors of these matrices. While both the spectral radius

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v17i4.

Email addresses: machasri.m2019@vitstudent.ac.in (M. Machasri),
kalyanidesikan@vit.ac.in (K. Desikan)

https://www.ejpam.com 3004 Copyright: © 2024 The Author(s). (CC BY-NC 4.0)



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3005

and the second largest eigenvalue of a graph are crucial ideas in spectral graph theory,
they signify distinct spectral features of the graph. In network analysis, machine learning,
optimization, and computational science, the graph’s second largest eigenvalue is widely
used and advances our knowledge of graph structures and their functional characteristics.

A graph G is made up of two sets (V,E), where E is the set of unordered pairs of dis-
tinct vertices, known as edges, and V is a finite non-empty set of elements. The vertex set
is denoted as V = {v1, v2, . . . , vn} and the edge set is denoted by E = {e1, e2, . . . , em}. Ba-
sic notations and terminology are based on DB West’s book, Introduction to Graph Theory
[26]. The adjacency matrix A(G) of G is an n×n matrix A = [aij ], where aij = 1 if vi and
vj are adjacent, otherwise it is 0. Let λ1 ≥ λ2 ≥ · · · ≥ λn be the eigenvalues of A known
as the spectrum of G. The Laplacian matrix of G is L(G) = D(G)−A(G) where D(G) is
the diagonal degree matrix. Let µ1 ≥ µ2 ≥ µ3 ≥ · · · ≥ µ(n−1) ≥ µn be the eigenvalues of
the Laplacian matrix. The signless Laplacian matrix of G is Q(G) = D(G) + A(G). Its
eigenvalues are denoted as q1 ≥ q2 ≥ · · · ≥ qn.

The graph planarization problem is to determine a minimum subset of edges to remove
from a non-planar graph to make it planar. The problem has applications in computer sci-
ence with regard to printed circuit board layout and Very-Large Scale Integration (VLSI)
circuit routing.

Beyond the standard graph parameters, we intend to work on the parameters that are
most challenging to compute. So far, no results have been found connecting the second
largest eigenvalue to planarity-related characteristics. Parameters such as graph skewness,
thickness, and crossing number are used to determine how much a graph deviates from
planarity. Computation of these properties are often challenging. As a result, it is helpful
to find bounds for them. In this work, we prove the relation of these graph parameters
with the second largest eigenvalue of the graph. We employ quotient matrix and eigen-
value interlacing technique to arrive at these bounds.

Determining the skewness of a non planar graph is the graph-theoretic variant of the
problem. The problem is known to be NP−complete [18]. The concept of skewness is
crucial in optimizing graph layouts, designing efficient algorithms, ensuring network relia-
bility, and advancing theoretical research in graph theory. In Very Large Scale Integration
(VLSI) circuit design, skewness helps in minimizing the complexity of circuit layouts. By
analyzing the skewness of interconnections in a circuit graph, designers can strategically
remove certain connections to create a more planar layout, which is crucial for reducing
interference and improving signal integrity. This application is vital in ensuring that cir-
cuits function efficiently without excessive heat generation or signal degradation.

The thickness of a graph is a valuable measure for simplifying and understanding com-
plex graphs by breaking them into planar components. This concept finds applications
in various fields, enhancing visualization, improving design efficiency, and aiding in the



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3006

development of more effective algorithms and systems. Whether in circuit design, network
optimization, biological research, or software engineering, the ability to work with planar
subgraphs is a powerful tool for tackling complexity. Particularly in computational biol-
ogy, graph thickness can aid in the analysis of biological networks, such as protein-protein
interaction networks. Understanding the thickness of these graphs can help researchers
identify modular structures within biological systems, facilitating insights into cellular
functions and interactions. This application is essential for advancements in fields like
genomics and systems biology, where complex interactions need to be understood and
modeled accurately.

Crossing numbers play a significant role in various practical and theoretical aspects of
graph theory and related disciplines. In network design, such as designing circuit layouts
or communication networks, minimizing crossing numbers can lead to more efficient and
less congested layouts. This optimization can improve the performance and reliability of
the network. In map labeling, graphs are used to represent geographical features and
their relationships. Minimizing crossing numbers in these graphs can lead to clearer and
more informative maps. In transportation networks, such as railway or road systems, the
crossing number can aid the design of routes to minimize intersections, which can im-
prove traffic flow and safety. By analyzing the crossing number of a graph representing a
transportation network, planners can make decisions that reduce congestion and enhance
overall efficiency.

Bounds in graph theory serve as fundamental tools for estimation, algorithm optimiza-
tion, structural analysis, and practical applications across various domains. They not only
facilitate a deeper understanding of graph properties but also enhance computational effi-
ciency in solving complex problems. In the literature, bounds for certain graph parameters
have been determined in relation to other graph parameters. Peter Firby and Julie Havi-
land in [9] established lower bounds for the average distance in terms of the independence
number of the graph. In [4] M.Aouchiche et al. established a sharp upper bound on the
algebraic connectivity of a connected graph in terms of the domination number. Xiaofeng
Gu and Muhuo Liu in [11], proved sharp lower bounds on the matching number of graphs
in terms of the Laplacian eigenvalues. In [2] Nasir Ali et al. explored commutative rings
such as the ring of Gaussian integers, the ring Zn of integers modulo n, and quotient poly-
nomial rings in order to establish general bounds for the multiset dimension in Zero Divisor
graphs (ZD-graphs). Also, they analyzed the behavior of Mdim under algebraic operations
and discussed bounds in terms of diameter and maximum degree. Some general bounds
on the dominating metric dimension (Ddim) of the ZD-graph of R in terms of the maxi-
mum degree, girth, clique number, and diameter were determined by Nasir Ali et al. in [3].

The second largest eigenvalue of a regular graph G has impact on graph’s diameter [6],
covering number [8] and the convergence properties of random walks [10]. In 2006, Stanic
[23] discovered for the first time the star complements for the graphs such as complete
graphs and trees with second largest eigenvalue 1. Ramezani and Tayfeh-Rezaiea [20]



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3007

found the maximal graphs and regular graphs which have Kr,s+ tK1 as a star complement
with second largest eigenvalue 1.

The relationship between the matching number and ∂2(G), the second largest distance
Laplacian eigenvalue of G, was examined by Tian and Wong [24], who also provided lower
bounds for ∂2(G) in terms of m(G). Additionally, all extremal graphs that achieved lower
bounds were described. In 2019, Vladislav Kabanova et al. [14] studied the eigenfunc-
tions of the Star graph Sn with n ≥ 3, where Sn is the Cayley graph on the symmetric
group Symn generated by the set of transpositions {(12), (13), . . . , (1n)} corresponding
to λ2 = n − 2. A characterisation of eigenfunctions with the smallest cardinality of the
support was found for n ≥ 8 and n = 3. They also got the minimal cardinality of the
support of an eigenfunction of Sn corresponding to the second largest eigenvalue. In terms
of the order and matching number of G, Shuchao Li and Wanting Sun [15] set sharp lower
bounds on q2(G). Among the n−vertex connected graphs with fixed connectivity, they
found the one and only graph with the least q2(G).
The maximum number of vertices of a connected k−regular graph with the second largest
eigenvalue at most λ is denoted as v(k, λ). The Alon-Boppana Theorem implies that

v(k, λ) is finite when k > λ2+4
4 . Jae Young Yang and Jack H. Koolen [27] proved that for

fixed λ ≥ 1, there exists a constant C(λ) such that 2k + 2 ≤ v(k, λ) ≤ 2k + C(λ) when

k > λ2+4
4 . The relationship between the local valency of an edge-regular graph and its λ2

was discovered by Jongyook Park [19]. For some connected sets H, Siemons et al. [21]
calculated the value of λ2(Γ) by looking at the second largest eigenvalue of the Cayley
graph Γ = Cay(G,H) over G = Sn or An.

This paper is organised as follows. We present some fundamental concepts related
to the parameters of planar graphs in section 2. In section 3, we investigate the relation
between the second largest eigenvalue of a graph with the parameters of planar graph such
as skewness, thickness and crossing number. Section 3.1 provides the relation between the
second largest eigenvalue of adjacency and signless Laplacian matrices with the skewness
of the graph sk(G); that is, lower bounds for λ2 and q2 with respect to the skewness of
the graph. Section 3.2 gives the lower bounds for λ2 and q2 with respect to the thickness
of the graph τ(G). Section 3.3 presents the lower bounds for λ2 and q2 with respect to
the crossing number of the graph cr(G). In all the sections lower bounds for the graph
parameters sk(G), τ(G), and cr(G) in terms of the second largest adjacency and signless
Laplacian eigenvalues for regular graphs are also presented.

2. Preliminaries

Planar graph is a graph that can be drawn in such a way that no edges cross each
other [25]. Such a drawing is called a plane graph or planar embedding of the graph.

The skewness of a graph G is the minimum number of edges whose removal results in
a planar graph. It is denoted by sk(G).



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3008

From [7], we have
sk(G) ≥ m− (3n− 6) (1)

where m and n are the size and the order of G, respectively.

Figure 1: Complete graph K6

In Figure 1, if we remove one edge from each red crossing, it will become planar. Skew-
ness of the complete graph K6 is given by sk(K6) = 3.

The thickness τ(G) of a graph G is the minimum number of planar edge-induced sub-
graphs Pi of G needed such that the graph union

⋃
Pi = G [22].

From the definition of thickness of a graph, the graph K6 has 2 planar edge-induced
subgraphs. Therefore, the thickness of K6 is τ(K6) = 2.

A lower bound for the thickness of a graph is given by [22]

τ(G) ≥
⌈

m

3n− 6

⌉
(2)

where m is the number of edges, n ≥ 3 is the number of vertices, and ⌈x⌉ is the ceiling
function. The thickness of the hypercube graph Qn [13] is given by

τ(Qn) =

⌈
n+ 1

4

⌉
.

Figure 2: Thickness of K6



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3009

Figure 3: Planar edge-induced sub-
graph 1 of K6

Figure 4: Planar edge-induced sub-
graph 2 of K6

The crossing number cr(G) of a graph G is the lowest number of edge crossings of
a plane drawing of the graph G. A graph with crossing number 0 is known as a planar
graph. For example, the complete graph K6 illustrated in Figure 1 has crossing number
3. Ajtai et al. (1982) showed that there is an absolute constant c > 0 such that

cr(G) ≥ cm3

n2
.

This inequality is known as crossing number inequality or crossing lemma.
Due to Ackerman [1], the constant c = 1

29 is the best known to date. Therefore,

cr(G) ≥ m3

29n2
. (3)

Definition 1. [5] Consider two sequences of real numbers:
ξ1, ξ2, . . . , ξn and η1, η2, . . . , ηm with m ≤ n. The second sequence is said to interlace the
first one whenever ξi ≤ ηi ≤ ξn−m+i for i = 1, 2, . . . ,m. The interlacing is called tight if
there exists an integer k ∈ [0,m] such that ξi = ηi for 1 ≤ i ≤ k and ξn−m+i = ηi for
k + 1 ≤ i ≤ m.

Definition 2. [16] Let M = (Mi,j)t×t be a real matrix of order n where Mij are the blocks
of M and i, j = 1, 2, . . . , t. Then the Quotient matrix of M is a matrix B(M) = (bij)
where bij is the sum of all entries in Mij divided by the number of rows of Mij.

Lemma 1. [12, 17] Let AQ be the quotient matrix of a symmetric matrix A whose rows
and columns are partitioned according to a partitioning
(X1, X2, . . . , Xm). Then

i. The eigenvalues of AQ interlace the eigenvalues of A.

ii. If the interlacing is tight then the partition is equitable.

3. Main Results

In this section, the relation between the second largest eigenvalue of graph with the
parameters of planar graphs such as skewness, thickness and crossing number are discussed.



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3010

3.1. Skewness

The theorems relating the second largest adjacency and signless Laplacian eigenvalues
of a graph and skewness of the graph are presented in this section. We establish lower
bounds for λ2 and q2 in terms of sk(G). Also, lower bounds for the skewness of regular
graphs in terms of λ2 and q2 are obtained.

Theorem 1. Let G be a connected graph with skewness sk(G). Then

λ2 ≥
1

2

{[
δ − 3∆

m− sk(G) + 3

]
−

√[
δ +

3∆

m− sk(G) + 3

]2
+

12∆(∆− δ)

m− sk(G) + 3

}
.

Proof. Let AQ be the quotient matrix of the adjacency matrix A of G with respect to
the partitions P1 and P2 where P1 consists of one vertex of G with maximum degree ∆.
Then, we have |P1| = n1 = 1 and |P2| = n2 = (n− 1). Then

AQ =

[
d′1 − t t

t
(n−1) d′2 − t

(n−1)

]
where d′1, d

′
2 are the average degrees of the two partitions P1, P2 and t is the number of

edges between P1 and P2. The characteristic equation of the above matrix is given by

η2 −

[
d′1 + d′2 − t− t

(n− 1)

]
η +

(
d′1 − t

)(
d′2 −

t

(n− 1)

)
− t2

(n− 1)
= 0.

The roots of the above characteristic equation are

η1 =
1
2

{(
d′1 + d′2 − tn

(n−1)

)
+

√
r

}
and η2 =

1
2

{(
d′1 + d′2 − tn

(n−1)

)
−
√
r

}
where

r =

[(
d′1 − t

)
−

(
d′2 −

t

(n− 1)

)]2
+

4t2

(n− 1)

=

(
d′1 − d′2 − t− t

(n− 1)

)2

+
4t(d′1 − d′2)

(n− 1)
.

Therefore, we have

η2 =
1

2

{(
d′1 + d′2 −

tn

(n− 1)

)
−

√√√√(d′1 − d′2 − t− t

(n− 1)

)2

+
4t(d′1 − d′2)

n2

}
.

Since d′1 = ∆ and d′2 ≥ δ we get,

η2 ≥
1

2

{(
∆+ δ − tn

(n− 1)

)
−

√√√√(∆− δ − t− t

(n− 1)

)2

+
4t(∆− δ)

(n− 1)

}
.



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3011

By eigenvalue interlacing, we have

λ2 ≥
1

2

{(
∆+ δ − tn

(n− 1)

)
−

√(
∆− δ − tn

(n− 1)

)2

+
4t(∆− δ)

(n− 1)

}
.

The above inequality can be rewritten as

λ2 ≥
1

2

{[
∆+ δ − t

(
1 +

1

(n− 1)

)]
−

√[
∆− δ − t

(
1 +

1

(n− 1)

)]2
+

4t(∆− δ)

(n− 1)

}
.

Since t = ∆, the above inequality becomes

λ2 ≥
1

2

{(
δ − ∆

(n− 1)

)
−

√(
δ +

∆

(n− 1)

)2

+
4∆(∆− δ)

(n− 1)

}
.

By making use of inequality (1), the result is obtained.

Theorem 2. Let G be a d−regular graph with n ≥ 3. Then

λ2 ≥
3d

sk(G)−m− 3
.

Proof. Let A be the adjacency matrix of G represented in the following block matrix
form

A =

[
A11 A12

A21 A22

]
.

Let AQ be the quotient matrix of A of G with respect to the partitions P1 and P2. Let
|P1| = n1 = 1 and |P2| = n2 = (n− 1). Then

AQ =

[
d− t t

t
(n−1) d− t

(n−1)

]
where t is the number of edges between P1 and P2.
The characteristic equation of the above matrix is given by[

η −
(
d− t

)][
η −

(
d− t

(n− 1)

)]
− t2

(n− 1)
= 0.

The roots of the above equation are η1 = d and η2 = d− tn
(n−1) .

From eigenvalue interlacing we have,

λ2 ≥ d− tn

(n− 1)
.

Since t = d, the above inequality can be rewritten as

λ2 ≥
d

(1− n)
.

Now, using inequality (1), we get the final result.



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3012

Note 1. If G is a d−regular graph except complete split graph and complete multipartite
graph with n ≥ 3 then

sk(G) ≤ 3d

λ2
+ (m+ 3).

Theorem 3. Let G be a connected graph with skewness sk(G). Then

q2 ≥
1

2

{[
2δ +∆(1− 3u)

]
−

√[
∆(1− 3u)− 2δ

]2
+ 24∆(∆− δ)u

}
where u = 1

(m−sk(G)+3) .

Proof. Let BQ be the quotient matrix of the signless Laplacian matrix Q of G with
respect to the partitions P1 and P2 where P1 consists of one vertex of G with maximum
degree ∆. We have |P1| = n1 = 1 and |P2| = n2 = (n− 1). Then

BQ =

[
2d′1 − t t

t
(n−1) 2d′2 − t

(n−1)

]
where d′1, d

′
2 are the average degrees of the two partitions P1, P2 and t is the number of

edges between P1 and P2. The characteristic equation of the above matrix is given by

ζ2 −
(
2d

′
1 + 2d

′
2 − t− t

(n− 1)

)
ζ +

(
2d

′
1 − t

)(
2d

′
2 −

t

(n− 1)

)
− t2

(n− 1)
= 0.

The roots of the above characteristic equation are

ζ1 =
1
2

{(
2d′1 + 2d′2 − tn

(n−1)

)
+

√
r

}
and ζ2 =

1
2

{(
2d′1 + 2d′2 − tn

(n−1)

)
−
√
r

}
where

r =

(
2d

′
1 − 2d

′
2 − t+

t

(n− 1)

)2

+
4t2

(n− 1)

=

(
2d

′
1 − 2d

′
2 − t− t

(n− 1)

)2

+
8t(d

′
1 − d

′
2)

(n− 1)
.

Therefore, we have

ζ2 =
1

2

{(
2d

′
1 + 2d

′
2 −

tn

(n− 1)

)
−

√(
2d

′
1 − 2d

′
2 −

tn

(n− 1)

)2

+
8t(d

′
1 − d

′
2)

(n− 1)

}
.

By eigenvalue interlacing, we have

q2 ≥
1

2

{(
2d

′
1 + 2d

′
2 −

tn

(n− 1)

)
−

√(
2d

′
1 − 2d

′
2 −

tn

(n− 1)

)2

+
8t(d

′
1 − d

′
2)

(n− 1)

}
.



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3013

Since d′1 = ∆ and d′2 ≥ δ we get,

q2 ≥
1

2

{(
2∆ + 2δ − tn

(n− 1)

)
−

√(
2∆− 2δ − tn

(n− 1)

)2

+
8t(∆− δ)

(n− 1)

}
.

The above inequality can be rewritten as

q2 ≥
1

2

{[
2∆ + 2δ − t

(
1 +

1

(n− 1)

)]
−

√[
2∆− 2δ − t

(
1 +

1

(n− 1)

)]2
+

8t(∆− δ)

(n− 1)

}
.

Since t = ∆, the above inequality becomes

q2 ≥
1

2

{(
∆+ 2δ − ∆

(n− 1)

)
−

√(
∆− 2δ − ∆

(n− 1)

)2

+
8∆(∆− δ)

(n− 1)

}
.

We obtain the result by making use of inequality (1).

Theorem 4. Let G be a d−regular graph with n ≥ 3. Then

q2 ≥ d

(
1− 3

m− sk(G) + 3

)
.

Proof. Let BQ be the quotient matrix of the signless Laplacian matrix Q of G with
respect to the partitions P1 and P2. Let |P1| = n1 = 1 and |P2| = n2 = (n− 1). Then

BQ =

[
2d− t t

t
(n−1) 2d− t

(n−1)

]
where t is the number of edges between P1 and P2.
The characteristic equation of the above matrix is given by[

ζ −
(
2d− t

)][
ζ −

(
2d− t

(n− 1)

)]
− t2

(n− 1)
= 0.

The roots of the above equation are ζ1 = 2d and ζ2 = d− d
(n−1) .

From eigenvalue interlacing we have,

q2 ≥ d− d

(n− 1)
.

Substituting t = d in the above inequality we have,

q2 ≥ d− d

(n− 1)
.

The result is obtained by applying inequality (1) in the above inequality.



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3014

Note 2. If G is a d−regular graph except complete split graph and complete multipartite
graph then

sk(G) ≤ m− 3q2
(d− q2)

.

Example 1. The graph illustrated in Figure 5 has 8 vertices, 20 edges with ∆ = 7, δ = 3
and λ2 = 0.828. Its skewness is given by sk(G) = 2. Also its crossing number cr(G) = 5.
Lower bound for λ2 from Theorem 1 is λ2 ≥ −1.828.

Figure 5: Graph with sk(G) = 2 and cr(G) = 5.

Example 2. The graph illustrated in Figure 6 has 6 vertices, 9 edges with d = 3, λ2 = 0
and q2 = 3. Also it has sk(G) = 1. Lower bound from Theorem 2 is λ2 ≥ −0.818 and from
Theorem 4 we have q2 ≥ 2.182.

Figure 6: A 3−regular graph with sk(G) = cr(G) = 1

3.2. Thickness

This section presents the theorems connecting a graph’s thickness τ(G) and second
largest adjacency and signless Laplacian eigenvalues. Lower bounds are established for λ2

and q2 in terms of τ(G). Also, lower bounds for the thickness τ(G) of regular graphs G
are presented in terms of λ2 and q2.

Theorem 5. Let G be a connected graph with thickness τ(G). Then

λ2 ≥
1

2

{[
δ − 3τ∆

m+ 3τ

]
−

√[
δ +

3τ∆

m+ 3τ

]2
+

12τ∆(∆− δ)

m+ 3τ

}
.

Proof. The proof is similar to the proof of Theorem 1. By making use of inequality
(2), we get the result.



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3015

Theorem 6. Let G be a d−regular graph with n ≥ 3.

λ2 ≥
−3τd

m+ 3τ
.

Proof. The proof is on the same lines as the proof of Theorem 2. Inequality (2) is used
to get the final result.

Note 3. If G is a d−regular graph with n ≥ 3 then

τ ≥ −mλ2

3(λ2 + d)
.

Theorem 7. Let G be a connected graph. Then

q2 ≥
1

2

{
[∆(1− 3τu) + 2δ]−

√
[∆(1− 3τu)− 2δ]2 + 24τ∆(∆− δ)u

}
where u = 1

m+3τ .

Proof. The proof is similar to the proof of Theorem 3. By using inequality (2), we get
the result.

Theorem 8. Let G be a d−regular graph with n ≥ 3. Then

q2 ≥
dm

m+ 3τ
.

Proof. The proof is similar to the proof of Theorem 4. By using inequality (2), we get
the result.

Note 4. If G is a d−regular graph except complete split graph and complete multipartite
graph with n ≥ 3 then

τ ≥ m

3

(
d

q2
− 1

)
.

Example 3. The hypercube Q4 is a 4−regular graph on 16 vertices and 32 edges with
thickness τ(G) = 2, λ2 = 2 and q2 = 6. The lower bounds from Theorems 6 and 8 are
given by λ2 ≥ −0.631 and q2 ≥ 3.368.

In Table 1, numerical values of the bounds that we have proved in Theorem 1 and
Theorem 5 are presented for Complete bipartite graph Km.n with m ̸= n. The graphical
illustration of these bounds are given in Figure 7 and Figure 8.



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3016

S.No. Graph λ2 Theorem 1 bound Theorem 5 bound

1 K3,5 0 -1.4494 -2.0717
2 K4,6 0 -1.3042 -1.626
3 K5,7 0 -1.2072 -1.3472
4 K6,8 0 -1.138 -1.138
5 K7,9 0 -1.0863 -1.3931
6 K8,10 0 -1.0466 -1.2303
7 K9,11 0 -1.0151 -1.0982
8 K10,12 0 -0.9895 -0.9896
9 K11,13 0 -0.9683 -1.1714
10 K12,14 0 -0.9503 -1.0702
11 K13,15 0 -0.9355 -0.9938

Table 1: Lower bounds of λ2 for Km,n

Figure 7: Skewness Figure 8: Thickness

Numerical values for the lower bounds of λ2 proved in Theorems 2 and 6 are presented
for Complete bipartite graphs Kn,n in Table 2. The graphical representation of these
bounds are given in Figure 9 and Figure 10.

S.No. Graph λ2 Theorem 2 bound Theorem 6 bound

1 K3,3 0 -0.8181 -1.2
2 K4,4 0 -0.8 -1.0909
3 K5,5 0 -0.7895 -0.9677
4 K6,6 0 -0.783 -0.8571
5 K7,7 0 -0.7778 -1.0862
6 K8,8 0 -0.7742 -0.9863
7 K9,9 0 -0.7714 -0.9
8 K10,10 0 -0.7692 -0.8257
9 K11,11 0 -0.7674 -0.9925
10 K12,12 0 -0.7659 -0.9231

Table 2: Lower bounds of λ2 for Kn,n



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3017

Figure 9: Skewness Figure 10: Thickness

Numerical values of the lower bounds of q2 proved in Theorems 3 and 7 are presented
for Complete bipartite graphs Km,n with m ̸= n in Table 3. The graphical illustration of
these bounds are represented in Figure 11 and Figure 12.

S.No. Graph q2 Theorem 3 bound Theorem 7 bound

1 K3,5 5 2.764 2.1045
2 K4,6 6 4.0848 3.6871
3 K5,7 7 5.3086 5.1336
4 K6,8 8 6.4683 6.4684
5 K7,9 9 7.5859 7.2121
6 K8,10 10 8.6749 8.4528
7 K9,11 11 9.7439 9.6445
8 K10,12 12 10.799 10.7989
9 K11,13 13 11.8584 11.6062
10 K12,14 14 12.8802 12.7353

Table 3: Lower bounds of q2 for Km,n

Figure 11: Skewness Figure 12: Thickness

Numerical values of the lower bounds of q2 proved in Theorems 4 and 8 are presented
for Complete bipartite graphs Kn,n in Table 4. Its graphical representations are given in
Figure 13 and Figure 14.



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3018

S.No. Graph q2 Theorem 4 bound Theorem 8 bound

1 K3,3 3 2.1818 1.8
2 K4,4 4 3.2 2.909
3 K5,5 5 4.2105 4.032
4 K6,6 6 5.2174 5.143
5 K7,7 7 6.222 5.914
6 K8,8 8 7.22 7.014
7 K9,9 9 8.2286 8.1
8 K10,10 10 9.2307 9.174
9 K11,11 11 10.2326 10.008
10 K12,12 12 11.234 11.0769

Table 4: Lower bounds of q2 for Kn,n

Figure 13: Skewness Figure 14: Thickness

3.3. Crossing number

This section presents the theorems connecting a graph’s crossing number cr(G) and
second largest adjacency and signless Laplacian eigenvalues. Lower bounds are established
for λ2 and q2 in terms of cr(G) and lower bounds for the crossing number of regular graphs
are determined in terms of λ2 and q2.

Theorem 9. Let G be a connected graph with crossing number cr(G). Then

λ2 ≥
1

2

{
[δ +∆(1− u)]−

√
[δ −∆(1− u)]2 − 4∆(∆− δ)(1− u)

}
where u = m

√
m

m
√
m−

√
29cr

.

Proof. The proof is similar to the proof of Theorem 1. The result is obtained by using
inequality (3).

Theorem 10. Let G be a d−regular graph with n ≥ 3. Then

λ2 ≥ d

(
1− m

√
m

m
√
m−

√
29cr

)
.



M. Machasri, D. Kalyani / Eur. J. Pure Appl. Math, 17 (4) (2024), 3004-3021 3019

Proof. The proof is on the same lines as the proof of Theorem 2. By using inequality
(3), we get the result.

Note 5. If G is a d−regular graph with n ≥ 3 then

cr ≤ m3λ2
2

29(d− λ2)2
.

Theorem 11. Let G be a connected graph. Then

q2 ≥
1

2

{
[2(∆ + δ)−∆u]−

√
[2(∆− δ)−∆u]2 − 8∆(∆− δ)(1− u)

}
where u = m

√
m

m
√
m−

√
29cr

.

Proof. The proof is similar to the proof of Theorem 3. Inequality (3) is used to get
the result.

Theorem 12. Let G be a d−regular graph with n ≥ 3. Then

q2 ≥ 2d− dm
√
m

m
√
m−

√
29cr

.

Proof. The proof is on the same lines as the proof of Theorem 4. Inequality (3) is used
to obtain the result.

Note 6. If G is a d−regular graph with n ≥ 3 then

cr ≤ m3

29

(
d− q2
2d− q2

)2

.

Example 4. For the graph represented in Figure 5 with crossing number cr(G) = 5, the
lower bound from Theorem 9 is given by λ2 ≥ −1.971.

Example 5. For the graph illustrated in Figure 6 with crossing number cr(G) = 1, the
lower bound obtained using Theorem 10 is λ2 ≥ −0.747 and lower bound obtained using
Theorem 12 is q2 ≥ 2.253.

Example 6. Let us consider the Petersen graph. It has n = 10, m = 15, d = 3, λ2 = 1
and q2 = 4. Then the lower bounds from Theorems 10 and 12 are given by λ2 ≥ −0.7844
and q2 ≥ 2.2156.



REFERENCES 3020

4. Conclusion

Planarity is an important field of study in graph theory since it is essential for both the-
oretical understanding and real-world applications. In this work, the relationship between
the parameters associated with planar graphs and a graph’s second largest adjacency,
Laplacian and Signless Laplacian eigenvalues have been determined. Lower bounds on the
second largest adjacency and signless Laplacian eigenvalues of a graph are determined in
terms of skewness sk(G), thickness τ(G), and crossing number cr(G) of graphs. In the
future, we will investigate how the other graph parameters are related with the second
largest adjacency and signless Laplacian eigenvalues of graphs. Furthermore, using λ2, we
will focus on characterising graphs.

References

[1] Eyal Ackerman. On topological graphs with at most four crossings per edge. Com-
putational Geometry, 85:101574, 2019.

[2] Nasir Ali, Hafiz Muhammad Afzal Siddiqui, and Muhammad Imran Qureshi. On
certain bounds for multiset dimensions of zero-divisor graphs associated with rings.
arXiv preprint arXiv:2405.06180, 2024.

[3] Nasir Ali, Hafiz Muhammad Afzal Siddiqui, Muhammad Bilal Riaz, Muhammad Im-
ran Qureshi, and Ali Akgül. A graph-theoretic approach to ring analysis: Dominant
metric dimensions in zero-divisor graphs. Heliyon, 10(10), 2024.

[4] Mustapha Aouchiche, Pierre Hansen, and Dragan Stevanović. A sharp upper bound
on algebraic connectivity using domination number. Linear Algebra and its Applica-
tions, 432(11):2879–2893, 2010.

[5] Andries E Brouwer and Willem H Haemers. Spectra of graphs. Springer Science &
Business Media, 2011.

[6] Fan RK Chung. Diameters and eigenvalues. Journal of the American Mathematical
Society, 2(2):187–196, 1989.

[7] Robert J Cimikowski. Graph planarization and skewness. Congressus Numerantium,
pages 21–21, 1992.

[8] Charles Delorme and Patrick Solé. Diameter, covering index, covering radius and
eigenvalues. European Journal of Combinatorics, 12(2):95–108, 1991.

[9] Peter Firby and Julie Haviland. Independence and average distance in graphs. Dis-
crete Applied Mathematics, 75(1):27–37, 1997.

[10] Joel Friedman. On the second eigenvalue and random walks in random d-regular
graphs. Combinatorica, 11(4):331–362, 1991.



REFERENCES 3021

[11] Xiaofeng Gu and Muhuo Liu. A tight lower bound on the matching number of graphs
via laplacian eigenvalues. European Journal of Combinatorics, 101:103468, 2022.

[12] Wilhelmus Hubertus Haemers. Eigenvalue techniques in design and graph theory.
1979.

[13] Frank Harary. Graph theory (on Demand Printing of 02787). CRC Press, 2018.

[14] Vladislav Kabanov, Elena V Konstantinova, Leonid Shalaginov, and Alexandr Va-
lyuzhenich. Minimum supports of eigenfunctions with the second largest eigenvalue
of the star graph. arXiv preprint arXiv:1910.01374, 2019.

[15] Shuchao Li and Wanting Sun. Matching number, connectivity and eigenvalues of
distance signless laplacians. Linear and Multilinear Algebra, 69(1):74–92, 2021.

[16] Chia-an Liu and Chih-wen Weng. Spectral radius of bipartite graphs. Linear Algebra
and its Applications, 474:30–43, 2015.

[17] Huiqing Liu, Mei Lu, and Feng Tian. Edge-connectivity and (signless) laplacian
eigenvalue of graphs. Linear Algebra and Its Applications, 439(12):3777–3784, 2013.

[18] Peter C Liu. On the deletion of nonplanar edges of a graph. In Proc. 10th South-East
Conference on Combinatorics, Graph Theory, and Computing, pages 727–738, 1977.

[19] Jongyook Park. A relationship between the second largest eigenvalue and local valency
of an edge-regular graph. Kyungpook Mathematical Journal, 61(3):671–677, 2021.

[20] Farzaneh Ramezani and Behruz Tayfeh-Rezaie. Graphs with prescribed star comple-
ment for 1 as the second largest eigenvalue. Ars Combinatoria, 116:129–145, 2014.

[21] Johannes Siemons and Alexandre Zalesski. On the second largest eigenvalue of some
cayley graphs of the symmetric group. Journal of Algebraic Combinatorics, pages
1–17, 2022.

[22] Steven Skiena. Combinatorics and graph theory with mathematica. Perseus Books
(Sd), 1990.

[23] Zoran Stanić. On graphs whose second largest eigenvalue equals 1–the star comple-
ment technique. Linear algebra and its applications, 420(2-3):700–710, 2007.

[24] Fenglei Tian and Dein Wong. Relation between the matching number and the second
largest distance laplacian eigenvalue of a graph. Linear Algebra and its Applications,
558:174–185, 2018.

[25] Richard J Trudeau. Introduction to graph theory. Courier Corporation, 2013.

[26] Douglas Brent West et al. Introduction to graph theory, volume 2. Prentice hall Upper
Saddle River, 2001.

[27] Jae Young Yang and Jack H Koolen. On the order of regular graphs with fixed second
largest eigenvalue. Linear Algebra and its Applications, 610:29–39, 2021.