An isoperimetric constant for signed graphs

DOI10.1016/J.EXMATH.2015.10.002zbMATH Open1342.05085arXiv1410.5995OpenAlexW2963792261MaRDI QIDQ530367FDOQ530367

Authors: A. Gournay 

Publication date: 29 July 2016

Published in: Expositiones Mathematicae (Search for Journal in Brave)

Abstract: A sign is introduced in the usual Laplacian on graphs and the corresponding analogue of the isoperimetric constant for this Laplacian is presented, i.e. a geometric quantity which enables to bound from above and below the first eigenvalue. The introduction of the sign in the Laplacian is motivated by the study of $2$-lifts of graphs and of the combinatorial Laplacian in higher degree.

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

Recommendations

• The (normalized) Laplacian eigenvalue of signed graphs
• Bounds for the least Laplacian eigenvalue of a signed graph
• On the Laplacian Eigenvalues of Signed Graphs
• On signed graphs whose second largest Laplacian eigenvalue does not exceed 3
• An upper bound for the Laplacian index of a signed graph

zbMATH Keywords

signed graphsgraph connection LaplacianCheeger inequality

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Inequalities involving eigenvalues and eigenvectors (15A42) Signed and weighted graphs (05C22)

Cites Work

• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Balancedness and the least eigenvalue of Laplacian of signed graphs
• Bounds for the least Laplacian eigenvalue of a signed graph
• An introduction to the theory of graph spectra
• Lifts, discrepancy and nearly optimal spectral gap
• On the isoperimetric spectrum of graphs and its approximations
• A characterization of the smallest eigenvalue of a graph
• A Cheeger Inequality for the Graph Connection Laplacian
• Discretization of Riemannian manifolds applied to the Hodge Laplacian

Cited In (2)

• Curvature, diameter and signs of graphs
• Frustration and isoperimetric inequalities for signed graphs

This page was built for publication: An isoperimetric constant for signed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q530367)