8 papers
Canonical labelling of random regular graphs
Mikhail Isaev, Tamás Makai, Brendan McKay +3
We prove that whenever and as , then with high probability for any non-trivial initial colouring, the colour refinement algorithm disti…
The Cycle Counts of Graphs
Ryan McCulloch, Brendan D. McKay, Alireza Salahshoori +1
We prove that an inseparable graph can have any positive number of cycles with the six exceptions 2, 4, 5, 8, 9, 16, and that an inseparable cubic graph has the additional exceptio…
On Pauling's residual entropy estimate for regular graphs with growing degree
M. Hasheminezhad, M. Isaev, B. D. McKay +1
In 1935, Pauling proposed an estimate for the number of Eulerian orientations of a graph in the context of the theoretical behaviour of water ice. The logarithm of the number of Eu…
Asymptotic enumeration of graph factors by cumulant expansion
Mikhail Isaev, Brendan D. McKay
Let be a dense graph with good expansion properties and not too close to being bipartite. Let be a graphical degree sequence. Under very weak conditions, we fin…
Correlation between residual entropy and spanning tree entropy of ice-type models on graphs
Mikhail Isaev, Brendan D. McKay, Rui-Ray Zhang
The logarithm of the number of Eulerian orientations, normalised by the number of vertices, is known as the residual entropy in studies of ice-type models on graphs. The spanning t…
Enumeration of regular multipartite hypergraphs
Mikhail Isaev, Tamás Makai, Brendan D. McKay
We determine the asymptotic number of regular multipartite hypergraphs, also known as multidimensional binary contingency tables, for all values of the parameters.