Modularity of minor-free graphs

被引：3

作者：

Lason, Michal ^{[1
]}

Sulkowska, Malgorzata ^{[2
,3
]}

机构：

[1] Polish Acad Sci, Inst Math, Ul Sniadeckich 8, PL-00656 Warsaw, Poland

[2] Univ Cote Azur, I3S, CNRS, INRIA, Nice, France

[3] Wroclaw Univ Sci & Technol, Dept Fundamentals Comp Sci, Wroclaw, Poland

来源：

JOURNAL OF GRAPH THEORY | 2023年 / 102卷 / 04期

关键词：

Cheeger's inequality; edge separator; minor-free graph; modularity; sparse graph; SEPARATOR THEOREM; EDGE SEPARATORS; PLANAR;

D O I：

10.1002/jgt.22896

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that a class of graphs with excluded minor and with the maximum degree of smaller order than the number of edges is maximally modular, that is, for every epsilon > 0 $\varepsilon \gt 0$, the modularity of any graph in the class with sufficiently many edges is at least 1 - epsilon $1-\varepsilon $.

引用

页码：728 / 736

页数：9

共 24 条

[1]

ALON N, 1990, PROCEEDINGS OF THE TWENTY SECOND ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, P293, DOI 10.1145/100216.100254

[2] LAMBDA-1, ISOPERIMETRIC-INEQUALITIES FOR GRAPHS, AND SUPERCONCENTRATORS [J].

ALON, N ;

MILMAN, VD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 38 (01) :73-88

[3] EIGENVALUES AND EXPANDERS [J].

ALON, N .

COMBINATORICA, 1986, 6 (02) :83-96

[4] Communities and bottlenecks: Trees and treelike networks have high modularity [J].

Bagrow, James P. .

PHYSICAL REVIEW E, 2012, 85 (06)

[5] Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows [J].

Biswal, Punyashloka ;

Lee, James R. ;

Rao, Satish .

JOURNAL OF THE ACM, 2010, 57 (03)

[6] Fast unfolding of communities in large networks [J].

Blondel, Vincent D. ;

Guillaume, Jean-Loup ;

Lambiotte, Renaud ;

Lefebvre, Etienne .

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2008,

[7]

Cheeger J., 1970, Problems in analysis (Papers dedicated to Salomon Bochner, 1969), P195

[8] The modularity of random graphs on the hyperbolic plane [J].

Chellig, Jordan ;

Fountoulakis, Nikolaos ;

Skerman, Fiona .

JOURNAL OF COMPLEX NETWORKS, 2022, 10 (01)

[9]

de Montgolfier F, 2011, LECT NOTES COMPUT SC, V7074, P435, DOI 10.1007/978-3-642-25591-5_45

[10] EDGE SEPARATORS OF PLANAR AND OUTERPLANAR GRAPHS WITH APPLICATIONS [J].

DIKS, K ;

DJIDJEV, HN ;

SYKORA, O ;

VRTO, I .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1993, 14 (02) :258-279

← 1 2 3 →