expansion -- returns the expansion of a graph

Synopsis

Usage:

h=expansion G
Inputs:
- G, a graph,
Outputs:
- h, a rational number, the expansion of a graph G

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.