The Electronic Journal of Combinatorics · 2014 · 15 citations · 19 references
Natural SciencesMathematicsCombinatoricsEdge ComputingGraph VisualizationEigenvalue ProblemsGraph TheoryEigenvaluesEigenvalues Of The LaplacianGraph Laplacian
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 $\mu_1(G)\ge\cdots\ge\mu_{n-1}(G)\ge\mu_n(G)=0$. It is a conjecture on Laplacian spread of graphs that $\mu_1(G)-\mu_{n-1}(G)\le n-1$ or equivalently $\mu_1(G)+\mu_1(\overline G)\le2n-1$. We prove the conjecture for bipartite graphs. Also we show that for any bipartite graph $G$, $\mu_1(G)\mu_1(\overline G)\le n(n-1)$. Aouchiche and Hansen [Discrete Appl. Math. 2013] conjectured that $q_1(G)+q_1(\overline G)\le3n-4$ and $q_1(G)q_1(\overline G)\le2n(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(\overline{H_n})$ is about $2.15n^2+O(n)$.
19
Algebraic connectivity of graphs
Miroslav Fiedler · Czechoslovak Mathematical Journal · 1973 · 4K citations · Full text
An introduction to the theory of graph spectra
Choice Reviews Online · 2010 · 787 citations
E. A. Nordhaus, J. W. Gaddum · American Mathematical Monthly · 1956 · 444 citations
A survey of Nordhaus–Gaddum type relations
Mustapha Aouchiche, Pierre Hansen · Discrete Applied Mathematics · 2012 · 203 citations