Graph Likelihood

The likelihood of a simple graph is defined by starting with the set . The following procedure is then iterated to produce a set of graphs of order . At step , randomly pick an integer from the set . Now randomly pick one of the graphs in (keeping the probability that it was constructed in step ) and add a new vertex joined to randomly selected vertices of that graph. Now merge any isomorphic graphs produced by this procedure by totalling their probabilities. The likelihood of a graph on vertices is then defined as the probability that appears in .

The more general sequential-growth process, with an arbitrary distribution of the vertex degree of each new vertex, was studied by Janson and Severini (2013). The graph likelihood arising from the discrete uniform distribution on the possible degrees was introduced by Banerji et al. (2014).

The th iteration of this procedure produces every possible graph on vertices. The results for graphs of orders to 4 are illustrated above. Likelihoods for all simple graphs of order up to 10 have been computed by E. Weisstein (Dec. 23, 2013).

, where is the graph complement of . and are therefore co-likely.

Since the values are probabilities, the sum of likelihoods over all -node graphs is 1 and individual likelihoods satisfy

with holding only for . also satisfies the stronger inequality

where is the order of the automorphism group of (Banerji et al. 2014).

An exact recurrence is obtained by defining

Then , and for a graph on vertices,

where denotes the vertex deletion of from . Equivalently,

Choosing any representative of the isomorphism class of with vertex set , the same exact recurrence gives a subset dynamic program

with and

Thus graph likelihood can be computed exactly either by recursive evaluation of the vertex-deletion recurrence or, after choosing such a representative, by the subset dynamic program above.

The following table summarizes the likelihoods for members of a number of special classes.

Classes with known closed form values include

Here is a complete graph, is an empty graph, is a star graph, is a factorial, and is a subfactorial.

For the ladder rung graph ,

Equivalently, its likelihood has the series-coefficient form

where denotes coefficient notation and is the inverse erf function. Since the cocktail party graph is the graph complement of and , both formulas also hold for it.

In addition, there is a relationship between for a cycle graph and for a path graph given by

(Banerji et al. 2014).

In general, a graph on vertices with isolated edges has likelihood

giving special cases

where is a harmonic number.

Values of for -node graphs are plotted above.

Computations by E. Weisstein in 2013 found that, for all except , 3, and 5, the minimum is attained by the balanced complete multipartite graph when and by the complete bipartite graph when , together with their graph complements. For the three exceptional orders, the minima occur for , , and , respectively. Citing this numerical evidence, Dervovic et al. (2018) conjectured that these complete bipartite graphs and their graph complements give the minima for all larger . The minimum values of for , 2, ... are 1, 1/2, 1/6, 1/36, 1/270, 23/259200, ... (OEIS A234234 and A234235).

The situation for maximum as a function of is less clear, with maxima occurring for , 2, ... for , , , paw graph, dart graph, ... and their complements. The corresponding maximum values are 1, 1/2, 1/3, 13/72, 307/4320, 1927/86400, ... (OEIS A234236 and A234237).