++ed by:

1 non-PAUSE user.

Kevin Ryde
and 1 contributors

NAME

Graph::Maker::ExcessConfigurations - create ExcessConfigurations graph

SYNOPSIS

`````` use Graph::Maker::ExcessConfigurations;
\$graph = Graph::Maker->new ('excess_configurations', N => 7);``````

DESCRIPTION

`Graph::Maker::ExcessConfigurations` creates `Graph.pm` graphs of the evolution of multigraph excess "configuration"s in the manner of

``````            /---> 0,1 --->  1,1          ( cross connections
0 ---> 1           X                       0,1 and 2
\--->  2  --->  0,0,1           -> 1,1 and 0,0,1 )
\
---->  3``````

The "excess" of a connected component of a multigraph is

``````    excess = number of edges - number of vertices
= -1 for tree (acyclic), 0 for unicyclic, ...``````

Janson et al take the configuration of a multigraph to be the number of components of excess r = 1, 2, 3, etc.

``    [count r=1, count r=2, ...]      vertex name such as "1,0,2"``

In the ExcessConfigurations graph, each vertex is such a configuration. An edge is to a new configuration obtained by adding one edge to the multigraph. Such an edge can increase the excess of an existing component, including raising an r=0 to a new r=1. Or it can join two components r,s together for new combined excess r+s+1. r=0 components doesn't appear in the configuration but are taken to be in unlimited supply.

Janson et al note this is a partial ordering of configurations since total excess increases by 1 each time. Total excess is total of the r>=0 components, so not including tree components.

``    total excess = r1 + 2*r2 + 3*r3 + ...``

Parameter N here is how many evolution steps, so configurations of total excess 0 through N inclusive, and the edges between them. Total excess is sum of component excesses, so those component excesses are a partition of the total. The number of vertices is thus sum over t=total,

``````    num vertices = sum(t=0,N, NumPartitions(t))
= 1, 2, 4, 7, 12, 19, ...  (A000070)``````

Cycles

As a note on terminology, excess r=0 described above is a unicyclic component, meaning it has one cycle and possible acyclic branches hanging off.

Janson et al call r=1 bi-cyclic (and r=2 tri-cyclic, etc). The cases for r=1 are, up to paths or vertex insertions (so "reduced multigraphs"),

``````      _   _      __      __          __
/ \ / \    |  |    |  |        /  \         excess r=1
|   A   |   |  A----B  |       A----B      (Janson et al
\_/ \_/    |__|    |__|        \__/       equation 9.15)

separate loops          three paths``````

The separate loops are clearly 2 cycles. The three paths case would be 3 cycles if all combinations were allowed. Excess r=1 as bi-cyclic is understood as successive cycles using at least one previously unused edge, the way edges are added to the multigraph in forming a cycle.

FUNCTIONS

`\$graph = Graph::Maker->new('excess_configurations', key => value, ...)`

The key/value parameters are

``````    N           =>  integer, number of steps
graph_maker => subr(key=>value) constructor, default Graph->new``````

Other parameters are passed to the constructor, either the `graph_maker` coderef or `Graph->new()`.

If the graph is directed (the default) then edges are in the add-an-edge direction between configurations.

HOUSE OF GRAPHS

House of Graphs entries for the trees here include,

``````    1310    N=0, singleton
19655   N=1, path-2
500     N=2, star-4 claw
33585   N=3
33587   N=4``````

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this tree include

``````    A000070    num vertices, cumulative num partitions
A029859    num edges, partitions choose 0,1,2 terms
A000041    num successorless, partitions of N``````