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
|
The object expansion is a method function.