expansion -- returns the expansion of a graph

Synopsis

• Usage:
h=expansion G
• Inputs:
• G, an instance of the type Graph,
• Outputs:
• h, , 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 .