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
Svante Janson, Donald E. Knuth, Tomasz Luczak, Boris Pittel, "Birth of the Giant Component", Random Structures and Algorithms, volume 4, 1993, pages 233358. https://arxiv.org/abs/math/9310236, https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240040303
/> 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 bicyclic (and r=2 tricyclic, etc). The cases for r=1 are, up to paths or vertex insertions (so "reduced multigraphs"),
_ _ __ __ __
/ \ / \     / \ excess r=1
 A   AB  AB (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 bicyclic 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 orGraph>new()
.If the graph is directed (the default) then edges are in the addanedge direction between configurations.
HOUSE OF GRAPHS
House of Graphs entries for the trees here include,
1310 N=0, singleton
19655 N=1, path2
500 N=2, star4 claw
33585 N=3
33587 N=4
OEIS
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this tree include
http://oeis.org/A000070 (etc)
A000070 num vertices, cumulative num partitions
A029859 num edges, partitions choose 0,1,2 terms
A000041 num successorless, partitions of N
SEE ALSO
LICENSE
Copyright 2018, 2019 Kevin Ryde
This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.