19 citations · 20 across the 11 of their papers we have counts for
11 papers · 1 filter
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…
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…
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…
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.
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…
Triangle-free graphs with diameter 2
Alice Devillers, Nina Kamčev, Brendan McKay +5
There are finitely many graphs with diameter and girth 5. What if the girth 5 assumption is relaxed? Apart from stars, are there finitely many triangle-free graphs with diamete…
Generating Plane Quadrangulations and Symmetry-preserving Operations on Maps
Heidi Van den Camp, Brendan D. McKay
Lopsp-operations are operations on maps that are applied locally and are guaranteed to preserve all the orientation-preserving symmetries of maps. Well-known examples of such opera…
Cumulant expansion for counting Eulerian orientations
Mikhail Isaev, Brendan D. McKay, Rui-Ray Zhang
An Eulerian orientation is an orientation of the edges of a graph such that every vertex is balanced: its in-degree equals its out-degree. Counting Eulerian orientations correspond…
Sprinkling with random regular graphs
Mikhail Isaev, Brendan D. McKay, Angus Southwell +1
We conjecture that the distribution of the edge-disjoint union of two random regular graphs on the same vertex set is asymptotically equivalent to a random regular graph of the com…
Sandwiching random regular graphs between binomial random graphs
Pu Gao, Mikhail Isaev, Brendan McKay
Kim and Vu made the following conjecture (\textit{Advances in Mathematics}, 2004): if , then the random -regular graph can asymptotically almost s…