We show that certain topologically defined uniform spanning tree probabilities for graphs embedded in an annulus can be computed as linear combinations of Pfaffians of matrices involving the line-bundle Green's function, where the coefficients count cover-inclusive Dyck tilings of skew Young diagrams.

We investigate properties which ensure that a given finite graph is the commuting graph of a group or semigroup. We show that all graphs on at least two vertices such that no vertex is adjacent to all other vertices is the commuting graph of some semigroup. Moreover, we obtain complete classifications of the graphs with an isolated vertex or edge that are the commuting graph of a group and the cycles that are the commuting graph of a centrefree semigroup.

We consider the problem of minimizing the number of triangles in a graph of given order and size, and describe the asymptotic structure of extremal graphs. This is achieved by characterizing the set of flag algebra homomorphisms that minimize the triangle density.

A long-standing conjecture of Richter and Thomassen states that the total number of intersection points between any n simple closed Jordan curves in the plane, so that any pair of them intersect and no three curves pass through the same point, is at least (1−o(1))n 2.

We confirm the above conjecture in several important cases, including the case (1) when all curves are convex, and (2) when the family of curves can be partitioned into two equal classes such that each curve from the first class touches every curve from the second class. (Two closed or open curves are said to be touching if they have precisely one point in common and at this point the two curves do not properly cross.)

An important ingredient of our proofs is the following statement. Let S be a family of n open curves in ℝ2, so that each curve is the graph of a continuous real function defined on ℝ, and no three of them pass through the same point. If there are nt pairs of touching curves in S, then the number of crossing points is $\Omega(nt\sqrt{\log t/\log\log t})$ .

Random increasing k-trees represent an interesting and useful class of strongly dependent graphs that have been studied widely, including being used recently as models for complex networks. In this paper we study an informative notion called BFS-profile and derive, by several analytic means, asymptotic estimates for its expected value, together with the limiting distribution in certain cases; some interesting consequences predicting more precisely the shapes of random k-trees are also given. Our methods of proof rely essentially on a bijection between k-trees and ordinary trees, the resolution of linear systems, and a specially framed notion called Flajolet–Odlyzko admissibility.

We present a sufficient condition for a pair of finite integer sequences to be degree sequences of a bipartite graph, based only on the lengths of the sequences and their largest and smallest elements.

We show that, for each fixed k, an n-vertex graph not containing a cycle of length 2k has at most $80\sqrt{k\log k}\cdot n^{1+1/k}+O(n)$ edges.

A simple graph $G=(V,E)$ admits an $H$-covering if every edge in $E$ belongs to at least one subgraph of $G$ isomorphic to a given graph $H$. Then the graph $G$ is $(a,d)$-$H$-antimagic if there exists a bijection $f:V\cup E\rightarrow \{1,2,\ldots ,|V|+|E|\}$ such that, for all subgraphs $H^{\prime }$ of $G$ isomorphic to $H$, the $H^{\prime }$-weights, $wt_{f}(H^{\prime })=\sum _{v\in V(H^{\prime })}f(v)+\sum _{e\in E(H^{\prime })}f(e)$, form an arithmetic progression with the initial term $a$ and the common difference $d$. When $f(V)=\{1,2,\ldots ,|V|\}$, then $G$ is said to be super $(a,d)$-$H$-antimagic. In this paper, we study super $(a,d)$-$H$-antimagic labellings of a disjoint union of graphs for $d=|E(H)|-|V(H)|$.

Let Qd denote the hypercube of dimension d. Given d ⩾ m, a spanning subgraph G of Qd is said to be (Qd, Qm)-saturated if it does not contain Qm as a subgraph but adding any edge of E(Qd)\E(G) creates a copy of Qm in G. Answering a question of Johnson and Pinto [27], we show that for every fixed m ⩾ 2 the minimum number of edges in a (Qd, Qm)-saturated graph is Θ(2d).

We also study weak saturation, which is a form of bootstrap percolation. A spanning subgraph of Qd is said to be weakly (Qd, Qm)-saturated if the edges of E(Qd)\E(G) can be added to G one at a time so that each added edge creates a new copy of Qm. Answering another question of Johnson and Pinto [27], we determine the minimum number of edges in a weakly (Qd, Qm)-saturated graph for all d ⩾ m ⩾ 1. More generally, we determine the minimum number of edges in a subgraph of the d-dimensional grid Pkd which is weakly saturated with respect to ‘axis aligned’ copies of a smaller grid Prm. We also study weak saturation of cycles in the grid.

If n ⩾ k + 1 and G is a connected n-vertex graph, then one can add $\binom{k}{2}$ edges to G so that the resulting graph contains the complete graph Kk+1. This yields that for any connected graph G with at least k + 1 vertices, one can add $\binom{k}{2}$ edges to G so that the resulting graph has chromatic number > k. A long time ago, Bollobás suggested that for every k ⩾ 3 there exists a k-chromatic graph Gk such that after adding to it any $\binom{k}{2}$ − 1 edges, the chromatic number of the resulting graph is still k. In this note we prove this conjecture.

This paper contributes to the regular covers of a complete bipartite graph minus a matching, denoted $K_{n,n}-nK_{2}$, whose fiber-preserving automorphism group acts 2-arc-transitively. All such covers, when the covering transformation group $K$ is either cyclic or $\mathbb{Z}_{p}^{2}$ with $p$ a prime, have been determined in Xu and Du [‘2-arc-transitive cyclic covers of $K_{n,n}-nK_{2}$’, J. Algebraic Combin.39 (2014), 883–902] and Xu et al. [‘2-arc-transitive regular covers of $K_{n,n}-nK_{2}$ with the covering transformation group $\mathbb{Z}_{p}^{2}$’, Ars. Math. Contemp.10 (2016), 269–280]. Finally, this paper gives a classification of all such covers for $K\cong \mathbb{Z}_{p}^{3}$ with $p$ a prime.

An old conjecture of Z. Tuza says that for any graph G, the ratio of the minimum size, τ3(G), of a set of edges meeting all triangles to the maximum size, ν3(G), of an edge-disjoint triangle packing is at most 2. Here, disproving a conjecture of R. Yuster, we show that for any fixed, positive α there are arbitrarily large graphs G of positive density satisfying τ3(G) > (1 − o(1))|G|/2 and ν3(G) < (1 + α)|G|/4.

We give several results showing that different discrete structures typically gain certain spanning substructures (in particular, Hamilton cycles) after a modest random perturbation. First, we prove that adding linearly many random edges to a dense k-uniform hypergraph ensures the (asymptotically almost sure) existence of a perfect matching or a loose Hamilton cycle. The proof involves an interesting application of Szemerédi's Regularity Lemma, which might be independently useful. We next prove that digraphs with certain strong expansion properties are pancyclic, and use this to show that adding a linear number of random edges typically makes a dense digraph pancyclic. Finally, we prove that perturbing a certain (minimum-degree-dependent) number of random edges in a tournament typically ensures the existence of multiple edge-disjoint Hamilton cycles. All our results are tight.

The 3-uniform tight cycle Cs3 has vertex set ${\mathbb Z}_s$ and edge set {{i, i + 1, i + 2}: i ∈ ${\mathbb Z}_s$}. We prove that for every s ≢ 0 (mod 3) with s ⩾ 16 or s ∈ {8, 11, 14} there is a cs > 0 such that the 3-uniform hypergraph Ramsey number r(Cs3, Kn3) satisfies

$$\begin{equation*} r(C_s^3, K_n^3)< 2^{c_s n \log n}.\ \end{equation*}$$

$2^{n^{1+\epsilon_s}}$

Let G1 × G2 denote the strong product of graphs G1 and G2, that is, the graph on V(G1) × V(G2) in which (u1, u2) and (v1, v2) are adjacent if for each i = 1, 2 we have ui = vi or uivi ∈ E(Gi). The Shannon capacity of G is c(G) = limn → ∞ α(Gn)1/n, where Gn denotes the n-fold strong power of G, and α(H) denotes the independence number of a graph H. The normalized Shannon capacity of G is

$$C(G) = \ffrac {\log c(G)}{\log |V(G)|}.$$

The point-line collinearity graph ${\mathcal{G}}$ of the maximal 2-local geometry for the largest simple Fischer group, $Fi_{24}^{\prime }$, is extensively analysed. For an arbitrary vertex $a$ of ${\mathcal{G}}$, the $i\text{th}$-disc of $a$ is described in detail. As a consequence, it follows that ${\mathcal{G}}$ has diameter $5$. The collapsed adjacency matrix of ${\mathcal{G}}$ is given as well as accompanying computer files which contain a wealth of data about ${\mathcal{G}}$.

Supplementary materials are available with this article.

A graph is called arc-regular if its full automorphism group acts regularly on its arc set. In this paper, we completely determine all the arc-regular Frobenius metacirculants of prime valency.

We introduce a new model of competition on growing networks. This extends the preferential attachment model, with the key property that node choices evolve simultaneously with the network. When a new node joins the network, it chooses neighbours by preferential attachment, and selects its type based on the number of initial neighbours of each type. The model is analysed in detail, and in particular, we determine the possible proportions of the various types in the limit of large networks. An important qualitative feature we find is that, in contrast to many current theoretical models, often several competitors will coexist. This matches empirical observations in many real-world networks.

Recent inapproximability results of Sly (2010), together with an approximation algorithm presented by Weitz (2006), establish a beautiful picture of the computational complexity of approximating the partition function of the hard-core model. Let λc($\mathbb{T}_{\Delta}$) denote the critical activity for the hard-model on the infinite Δ-regular tree. Weitz presented an FPTAS for the partition function when λ < λc($\mathbb{T}_{\Delta}$) for graphs with constant maximum degree Δ. In contrast, Sly showed that for all Δ ⩾ 3, there exists εΔ > 0 such that (unless RP = NP) there is no FPRAS for approximating the partition function on graphs of maximum degree Δ for activities λ satisfying λc($\mathbb{T}_{\Delta}$) < λ < λc($\mathbb{T}_{\Delta}$) + εΔ.

We prove that a similar phenomenon holds for the antiferromagnetic Ising model. Sinclair, Srivastava and Thurley (2014) extended Weitz's approach to the antiferromagnetic Ising model, yielding an FPTAS for the partition function for all graphs of constant maximum degree Δ when the parameters of the model lie in the uniqueness region of the infinite Δ-regular tree. We prove the complementary result for the antiferromagnetic Ising model without external field, namely, that unless RP = NP, for all Δ ⩾ 3, there is no FPRAS for approximating the partition function on graphs of maximum degree Δ when the inverse temperature lies in the non-uniqueness region of the infinite tree $\mathbb{T}_{\Delta}$. Our proof works by relating certain second moment calculations for random Δ-regular bipartite graphs to the tree recursions used to establish the critical points on the infinite tree.