Macaulay2 » Documentation
Packages » Graphs :: expansion
next | previous | forward | backward | up | index | toc

expansion -- returns the expansion of a graph

Description

The expansion of a subset S of vertices is the ratio of the number of edges leaving S and the size of S. The (edge) expansion of a graph G is the minimal expansion of all not too large subsets of the vertex set. The expansion of a disconnected graph is 0 whereas the expansion of the complete graph on n vertices is ceiling(n/2)

i1 : G = graph({{1, 2}, {1, 3}, {2, 3}, {3, 4}},EntryMode=>"edges");
i2 : expansion G

o2 = 1

o2 : QQ
i3 : expansion pathGraph 7

     1
o3 = -
     3

o3 : QQ

Ways to use expansion:

  • expansion(Graph)

For the programmer

The object expansion is a method function.


The source of this document is in /build/reproducible-path/macaulay2-1.25.06+ds/M2/Macaulay2/packages/Graphs.m2:3624:0.