Modularity of minor‐free graphs

DOI10.1002/JGT.22896zbMATH Open1522.05459arXiv2102.07253OpenAlexW3133397457MaRDI QIDQ6094045FDOQ6094045

Authors: Michał Lasoń, Małgorzata Sulkowska 

Publication date: 9 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: We prove that a class of graphs with an excluded minor and with the maximum degree sublinear in the number of edges is maximally modular, that is, modularity tends to 1 as the number of edges tends to infinity.

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

Recommendations

• Maximum degree in minor-closed classes of graphs
• Asymptotic modularity of some graph classes
• On the purity of minor-closed classes of graphs
• Maximum modular graphs
• Modularity of regular and treelike graphs

zbMATH Keywords

modularityminor-free graphsparse graphCheeger inequalityedge separator

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Graph minors (05C83)

Cites Work

• Fast unfolding of communities in large networks
• Eigenvalues and expanders
• Title not available (Why is that?)
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• On the Maximum Degree of a Random Planar Graph
• A Separator Theorem for Planar Graphs
• A Separator Theorem for Nonplanar Graphs
• Edge separators for graphs of bounded genus with applications
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Asymptotic modularity of some graph classes
• On nowhere dense graphs
• A separator theorem for graphs of bounded genus
• Finding small simple cycle separators for 2-connected planar graphs
• Edge Separators of Planar and Outerplanar Graphs With Applications
• The modularity of random graphs on the hyperbolic plane
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Modularity of regular and treelike graphs
• Modularity of Erdős-Rényi random graphs
• Treewidth of graphs with balanced separations
• On the modularity of 3‐regular random graphs and random graphs with given degree sequences

Cited In (3)

• Modularity of regular and treelike graphs
• Edge separators for graphs excluding a minor
• Letter graphs and modular decomposition

This page was built for publication: Modularity of minor‐free graphs

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