The Colour Refinement procedure and its generalisation to higher dimensions, the Weisfeiler-Leman algorithm, are central subroutines in approaches to the graph isomorphism problem. In an iterative fashion, Colour Refinement computes a colouring of the vertices of its input graph. A trivial upper bound on the iteration number of Colour Refinement on graphs of order n is n-1. We show that this bound is tight. More precisely, we prove via explicit constructions that there are infinitely many graphs G on which Colour Refinement takes |G|-1 iterations to stabilise. Modifying the infinite families that we present, we show that for every natural number n >= 10, there are graphs on n vertices on which Colour Refinement requires at least n-2 iterations to reach stabilisation.

Kim and Vu made the following conjecture (Advances in Mathematics, 2004): if d ≫ log n, then the random d-regular graph (n, d) can asymptotically almost surely be “sandwiched” between (n, p1) and (n, p2) where p1 and p2 are both (1 + o(1))d/n. They proved this conjecture for log n ≪ d ≪ n1/3−o(1), with a defect in the sandwiching: (n, d) contains (n, p1) perfectly, but is not completely contained in (n, p2). Recently, the embedding (n, p1) ⊆ (n, d) was improved by Dudek, Frieze, Ruciński and Šileikis to d = o(n). In this paper, we prove Kim–Vu's sandwich conjecture, with perfect containment on both sides, for all . For , we prove a weaker version of the sandwich conjecture with p2 approximately equal to (d/n) log n, without any defect. In addition to sandwiching regular graphs, our results cover graphs whose degrees are asymptotically equal. The proofs rely on estimates for the probability that a random factor of a pseudorandom graph contains a given edge, which is of independent interest. As applications, we obtain new results on the properties of random graphs with given near-regular degree sequences, including Hamiltonicity and universality in subgraph containment. We also determine several graph parameters in these random graphs, such as the chromatic number, small subgraph counts, the diameter, and the independence number. We are also able to characterise many phase transitions in edge percolation on these random graphs, such as the threshold for the appearance of a giant component.

Answering exact shortest path distance queries is a fundamental task in graph theory. Despite a tremendous amount of research on the subject, there is still no satisfactory solution that can scale to billion-scale complex networks. Labelling-based methods are well-known for rendering fast response time to distance queries; however, existing works can only construct labelling on moderately large networks (million-scale) and cannot scale to large networks (billion-scale) due to their prohibitively large space requirements and very long preprocessing time. In this work, we present novel techniques to efficiently construct distance labelling and process exact shortest path distance queries for complex networks with billions of vertices and billions of edges. Our method is based on two ingredients: (i) a scalable labelling algorithm for constructing minimal distance labelling, and (ii) a querying framework that supports fast distance-bounded search on a sparsified graph. Thus, we first develop a novel labelling algorithm that can scale to graphs at the billion-scale. Then, we formalize a querying framework for exact distance queries, which combines our proposed highway cover distance labelling with distance-bounded searches to enable fast distance computation. To speed up the labelling construction process, we further propose a parallel labelling method that can construct labelling simultaneously for multiple landmarks. We evaluated the performance of the proposed methods on 12 real-world networks. The experiments show that the proposed methods can not only handle networks with billions of vertices, but also be up to 70 times faster in constructing labelling and save up to 90% of labelling space. In particular, our method can answer distance queries on a billion-scale network of around 8B edges in less than 1ms, on average.

The competition graph of an acyclic directed graph $D$ is the undirected graph on the same vertex set as $D$ in which two distinct vertices are adjacent if they have a common out-neighbor in $D$. The competition number of an undirected graph $G$ is the least number of isolated vertices that have to be added to $G$ to make it the competition graph of an acyclic directed graph. We resolve two conjectures concerning competition graphs. First, we prove a conjecture of Opsut by showing that the competition number of every quasi-line graph is at most 2. Recall that a quasi-line graph, also called a locally co-bipartite graph, is a graph for which the neighborhood of every vertex can be partitioned into at most two cliques. To prove this conjecture we devise an alternative characterization of quasi-line graphs to the one by Chudnovsky and Seymour. Second, we prove a conjecture of Kim by showing that the competition number of any graph is at most one greater than the number of holes in the graph. Our methods also allow us to prove a strengthened form of this conjecture recently proposed by Kim et al., showing that the competition number of any graph is at most one greater than the dimension of the subspace of the cycle space spanned by the holes.

Let $J$ and $J^*$ be subsets of $\mathbb{N}$ such that $0,1\in J$ and $0\in J^*$. For infinitely many $n$, let ${\boldsymbol{k}}=(k_1,\ldots, k_n)$ be a vector of nonnegative integers whose sum $M$ is even. We find an asymptotic expression for the number of multigraphs on the vertex set $\{1,\ldots, n\}$ with degree sequence given by ${\boldsymbol{k}}$ such that every loop has multiplicity in $J^*$ and every nonloop edge has multiplicity in $J$. Equivalently, these are symmetric integer matrices with values $J^*$ allowed on the diagonal and $J$ off the diagonal. Our expression holds when the maximum degree $k_{\mathrm{max}}$ satisfies $k_{\mathrm{max}} = o(M^{1/3})$. We prove this result using the switching method, building on an asymptotic enumeration of simple graphs with given degrees [B. D. McKay and N. C. Wormald, Combinatorica, 11 (1991), pp. 369--382]. Our application of the switching method introduces a novel way of combining several different switching operations into a single computation.

We count all latin cubes of order $n\le6$ and latin hypercubes of order $n\le5$ and dimension $d\le5$. We classify these (hyper)cubes into isotopy classes and paratopy classes (main classes). For the same values of n and d we classify all d-ary quasigroups of order n into isomorphism classes and also count them according to the number of identity elements they possess (meaning we have counted the d-ary loops). We also give an exact formula for the number of (isomorphism classes of) d-ary quasigroups of order 3 for every d. Then we give a number of constructions for d-ary quasigroups with a specific number of identity elements. In the process, we prove that no 3-ary loop of order n can have exactly $n-1$ identity elements (but no such result holds in dimensions other than 3). Finally, we give some new examples of latin cuboids which cannot be extended to latin cubes.

MOTIVATION: Maximum-likelihood analysis of nucleotide and amino acid sequences is a powerful approach for inferring phylogenetic relationships and for comparing evolutionary hypotheses. Because it is a computationally demanding and time-consuming process, most algorithms explore only a minute portion of tree-space, with the emphasis on finding the most likely tree while ignoring the less likely, but not significantly worse, trees. However, when such trees exist, it is equally important to identify them to give due consideration to the phylogenetic uncertainty. Consequently, it is necessary to change the focus of these algorithms such that near optimal trees are also identified. RESULTS: This paper presents the Advanced Stepwise Addition Algorithm for exploring tree-space and two algorithms for generating all binary trees on a set of sequences. The Advanced Stepwise Addition Algorithm has been implemented in TrExML, a phylogenetic program for maximum-likelihood analysis of nucleotide sequences. TrExML is shown to be more effective at finding near optimal trees than a similar program, fastDNAml, implying that TrExML offers a better approach to account for phylogenetic uncertainty than has previously been possible. A program, TreeGen, is also described; it generates binary trees on a set of sequences allowing for extensive exploration of tree-space using other programs. AVAILABILITY: TreeGen, TrExML, and the sequence data used to test the programs are available from the following two WWW sites: http://whitetail.bemidji.msus. edu/trexml/and http://jcsmr.anu.edu.au/dmm/humgen.+ ++html.

We establish that every cyclically 4-connected cubic planar graph of order at most 40 is hamiltonian. Furthermore, this bound is determined to be sharp, and we present all nonhamiltonian examples of order 42. In addition we list all nonhamiltonian cyclically 5-connected cubic planar graphs of order at most 52 and all nonhamiltonian 3-connected cubic planar graphs of girth 5 on at most 46 vertices. The fact that all 3-connected cubic planar graphs on at most 176 vertices and with face size at most 6 are hamiltonian is also verified.

An algorithm of Beyer and Hedetniemi [SIAM J. Comput., 9 (1980), pp. 706–712] for generating rooted unlabeled trees is extended to generate unlabeled free trees. All the nonisomorphic trees of a given size are generated, without repetition, in time proportional to the number of trees.