Modularity of minor‐free graphs

DOI10.1002/JGT.22896MaRDI QIDQ6094045zbMATH OpenOpenAlexFDO

Authors Michał Lasoń, Małgorzata Sulkowska

Publication date 9 October 2023

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

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

zbMATH Keywords

modularityminor-free graphsparse graphCheeger inequalityedge separator

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(4)

• Edge separators for graphs excluding a minor
• Modularity of regular and treelike graphs
• Modularity of some distance graphs
• 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)