Nordhaus--Gaddum type inequalities for Laplacian and signless Laplacian eigenvalues

preprint2014arXivOpen access

Abstract

Let GG be a graph with nn vertices. We denote the largest signless Laplacian eigenvalue of GG by q1(G)q_1(G) and Laplacian eigenvalues of GG by μ1(G)≥⋯≥μn−1(G)≥μn(G)=0μ_1(G)\ge\cdots\geμ_{n-1}(G)\geμ_n(G)=0. It is a conjecture on Laplacian spread of graphs that μ1(G)−μn−1(G)≤n−1μ_1(G)-μ_{n-1}(G)\le n-1 or equivalently $μ_1(G)+μ_1(\Gb)\le2n-1$. We prove the conjecture for bipartite graphs. Also we show that for any bipartite graph GG, $μ_1(G)μ_1(\Gb)\le 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 GG with nn vertices, $q_1(G)+q_1(\Gb)\le3n-4$ and $q_1(G)q_1(\Gb)\le2n(n-2)$. We prove the former and disprove the latter by constructing a family of graphs HnH_n where $q_1(H_n)q_1(\ov{H_n})$ is about 2.15n2+O(n)2.15n^2+O(n).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.