Nordhaus-Gaddum type inequalities for Laplacian and signless Laplacian eigenvalues

Abstract: Let

G

be a graph with

n

vertices. We denote the largest signless Laplacian eigenvalue of

G

by

q_{1} (G)

and Laplacian eigenvalues of

G

by

m u_{1} (G) g e c d o t s g e m u_{n - 1} (G) g e m u_{n} (G) = 0

. It is a conjecture on Laplacian spread of graphs that

m u_{1} (G) - m u_{n - 1} (G) l e n - 1

or equivalently

m u_{1} (G) + m u_{1} (G b) l e 2 n - 1

. We prove the conjecture for bipartite graphs. Also we show that for any bipartite graph

G

,

m u_{1} (G) m u_{1} (G b) l e n (n - 1)

. Aouchiche and Hansen [A survey of Nordhaus--Gaddum type relations, Discrete Appl. Math. 161 (2013), 466--546] conjectured that %for any graph

G

with

n

vertices,

q_{1} (G) + q_{1} (G b) l e 3 n - 4

and

q_{1} (G) q_{1} (G b) l e 2 n (n - 2)

. We prove the former and disprove the latter by constructing a family of graphs

H_{n}

where

q_{1} (H_{n}) q_{1} (o v H_{n})

is about

2.15 n^{2} + O (n)

.

Full work available at URL: https://arxiv.org/abs/1402.2995

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

Cited In (12)

This page was built for publication: Nordhaus-Gaddum type inequalities for Laplacian and signless Laplacian eigenvalues