On the lower bound of the sum of the algebraic connectivity of a graph and its complement
type: Item
instance of: scholarly article
title: On the lower bound of the sum of the algebraic connectivity of a graph and its complement
zbMATH Open document ID: 1479.05200
author: Mostafa Einollahzadeh
author: Mohammad Mahdi Karkhaneei
published in: Journal of Combinatorial Theory. Series B
publication date: 2021-09-16T00:00:00Z
review text: Let \(G\) be a simple graph with \(n\) vertices. The Laplacian matrix of \(G\) is defined to be \(L:=D-A\), where \(A\) is the adjacency matrix of \(G\) and \(D\) is the diagonal matrix of vertex degrees. Let \(0=\mu_1(G)\leq\mu_2(G)\leq\cdots\leq\mu_n(G)\) be the eigenvalues of \(L\). The Laplacian spread of a graph \(G\) is defined to be \(\mu_n(G)-\mu_2(G)\). In [\textit{Z. You} and \textit{B. Liu}, Czech. Math. J. 62, No. 1, 155--168 (2012; Zbl 1245.05089); \textit{M. Zhai} et al., Appl. Math. Lett. 24, No. 12, 2097--2101 (2011; Zbl 1234.05156)], it was conjectured that this quantity is at most \(n-1\), or equivalently, \(\mu_2(G)+\mu_2(\overline{G})\) is at least \(1\), where \(\overline{G}\) is the complement of \(G\). This conjecture has been proved for various families of graphs. In this paper, the authors prove this conjecture in the general case. Also, they show that \(\max\{\mu_2(G),\mu_2(\overline{G})\} \geq 1 -O(n^{-\frac{1}{3}})\), where \(n\) is the number of vertices of \(G\).
reviewed by: Xiaogang Liu
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 7396135
zbMATH Keywords: Laplacian eigenvalues of graphs
zbMATH Keywords: Nordhaus-Gaddum type inequalities
zbMATH Keywords: effective resistance
zbMATH Keywords: Laplacian spread
MaRDI profile type: Publication
full work available at URL: j.jctb.2021.06.007
OpenAlex ID: W3176414553
cites work: The algebraic connectivity of a graph and its complement
cites work: Nordhaus-Gaddum type inequalities for Laplacian and signless Laplacian eigenvalues
cites work: The Laplacian spread of unicyclic graphs
cites work: Some results on the Laplacian spread of a graph
cites work: The Laplacian spread of tricyclic graphs
cites work: Effective graph resistance
cites work: Q3877805
cites work: Q3014360
cites work: Q5387732
cites work: Q5396735
cites work: The Laplacian spread of quasi-tree graphs
cites work: The Laplacian spread of graphs
cites work: On the Laplacian spread of graphs
DOI: 10.1016/J.JCTB.2021.06.007
description: scientific article; zbMATH DE number 7396135