We investigate the list packing number of a graph, the least $k$ such that there are always $k$ disjoint proper list-colourings whenever we have lists all of size $k$ associated to the vertices. We are curious how the behaviour of the list packing number contrasts with that of the list chromatic number, particularly in the context of bounded degree graphs. The main question we pursue is whether every graph with maximum degree $\Delta$ has list packing number at most $\Delta +1$. Our results highlight the subtleties of list packing and the barriers to, for example, pursuing a Brooks’-type theorem for the list packing number.

A cycle C of a graph G is dominating if $V(C)$ is a dominating set and $V(G)\backslash V(C)$ is an independent set. Wu et al. [‘Degree sums and dominating cycles’, Discrete Mathematics 344 (2021), Article no. 112224] proved that every longest cycle of a k-connected graph G on $n\geq 3$ vertices with $k\geq 2$ is dominating if the degree sum is more than $(k+1)(n+1)/3$ for any $k+1$ pairwise nonadjacent vertices. They also showed that this bound is sharp. In this paper, we show that the extremal graphs G for this condition satisfy $(n-2)/3K_1\vee (n+1)/3K_2 \subseteq G \subseteq K_{(n-2)/3}\vee (n+1)/3K_2$ or $2K_1\vee 3K_{(n-2)/3}\subseteq G \subseteq K_2\vee 3K_{(n-2)/3}.$

We show that for every $\eta \gt 0$ every sufficiently large $n$-vertex oriented graph $D$ of minimum semidegree exceeding $(1+\eta )\frac k2$ contains every balanced antidirected tree with $k$ edges and bounded maximum degree, if $k\ge \eta n$. In particular, this asymptotically confirms a conjecture of the first author for long antidirected paths and dense digraphs.

Further, we show that in the same setting, $D$ contains every $k$-edge antidirected subdivision of a sufficiently small complete graph, if the paths of the subdivision that have length $1$ or $2$ span a forest. As a special case, we can find all antidirected cycles of length at most $k$.

Finally, we address a conjecture of Addario-Berry, Havet, Linhares Sales, Reed, and Thomassé for antidirected trees in digraphs. We show that this conjecture is asymptotically true in $n$-vertex oriented graphs for all balanced antidirected trees of bounded maximum degree and of size linear in $n$.

In this paper, we propose a novel approach that employs kinetic equations to describe the collective dynamics emerging from graph-mediated pairwise interactions in multi-agent systems. We formally show that for large graphs and specific classes of interactions a statistical description of the graph topology, given in terms of the degree distribution embedded in a Boltzmann-type kinetic equation, is sufficient to capture the collective trends of networked interacting systems. This proves the validity of a commonly accepted heuristic assumption in statistically structured graph models, namely that the so-called connectivity of the agents is the only relevant parameter to be retained in a statistical description of the graph topology. Then, we validate our results by testing them numerically against real social network data.

We study the asymptotic growth rate of the labels of high-degree vertices in weighted recursive graphs (WRGs) when the weights are independent, identically distributed, almost surely bounded random variables, and as a result confirm a conjecture by Lodewijks and Ortgiese (‘The maximal degree in random recursive graphs with random weights’, preprint, 2020). WRGs are a generalisation of the random recursive tree and directed acyclic graph models, in which vertices are assigned vertex-weights and where new vertices attach to $m\in\mathbb{N}$ predecessors, each selected independently with a probability proportional to the vertex-weight of the predecessor. Prior work established the asymptotic growth rate of the maximum degree of the WRG model, and here we show that there exists a critical exponent $\mu_m$ such that the typical label size of the maximum-degree vertex equals $n^{\mu_m(1+o(1))}$ almost surely as n, the size of the graph, tends to infinity. These results extend results on the asymptotic behaviour of the location of the maximum degree, formerly only known for the random recursive tree model, to the more general weighted multigraph case of the WRG model. Moreover, for the weighted recursive tree model, that is, the WRG model with $m=1$, we prove the joint convergence of the rescaled degree and label of high-degree vertices under additional assumptions on the vertex-weight distribution, and also extend results on the growth rate of the maximum degree obtained by Eslava, Lodewijks, and Ortgiese (Stoch. Process. Appl. 158, 2023).

In this paper, we consider the friendship paradox in the context of random walks and paths. Among our results, we give an equality connecting long-range degree correlation, degree variability, and the degree-wise effect of additional steps for a random walk on a graph. Random paths are also considered, as well as applications to acquaintance sampling in the context of core-periphery structure.

In this paper, we completely resolve the well-known problem of Erdős and Sauer from 1975 which asks for the maximum number of edges an n-vertex graph can have without containing a k-regular subgraph, for some fixed integer $k\geq 3$. We prove that any n-vertex graph with average degree at least $C_k\log \log n$ contains a k-regular subgraph. This matches the lower bound of Pyber, Rödl and Szemerédi and substantially improves an old result of Pyber, who showed that average degree at least $C_k\log n$ is enough.

Our method can also be used to settle asymptotically a problem raised by Erdős and Simonovits in 1970 on almost regular subgraphs of sparse graphs and to make progress on the well-known question of Thomassen from 1983 on finding subgraphs with large girth and large average degree.

A recent paper of Balogh, Li and Treglown [3] initiated the study of Dirac-type problems for ordered graphs. In this paper, we prove a number of results in this area. In particular, we determine asymptotically the minimum degree threshold for forcing

1. (i) a perfect H-tiling in an ordered graph, for any fixed ordered graph H of interval chromatic number at least $3$ ;

2. (ii) an H-tiling in an ordered graph G covering a fixed proportion of the vertices of G (for any fixed ordered graph H);

3. (iii) an H-cover in an ordered graph (for any fixed ordered graph H).

The first two of these results resolve questions of Balogh, Li and Treglown, whilst (iii) resolves a question of Falgas-Ravry. Note that (i) combined with a result from [3] completely determines the asymptotic minimum degree threshold for forcing a perfect H-tiling. Additionally, we prove a result that, combined with a theorem of Balogh, Li and Treglown, asymptotically determines the minimum degree threshold for forcing an almost perfect H-tiling in an ordered graph (for any fixed ordered graph H). Our work therefore provides ordered graph analogues of the seminal tiling theorems of Kühn and Osthus [Combinatorica 2009] and of Komlós [Combinatorica 2000]. Each of our results exhibits some curious, and perhaps unexpected, behaviour. Our solution to (i) makes use of a novel absorbing argument.

We suggest two related conjectures dealing with the existence of spanning irregular subgraphs of graphs. The first asserts that any $d$ -regular graph on $n$ vertices contains a spanning subgraph in which the number of vertices of each degree between $0$ and $d$ deviates from $\frac{n}{d+1}$ by at most $2$ . The second is that every graph on $n$ vertices with minimum degree $\delta$ contains a spanning subgraph in which the number of vertices of each degree does not exceed $\frac{n}{\delta +1}+2$ . Both conjectures remain open, but we prove several asymptotic relaxations for graphs with a large number of vertices $n$ . In particular we show that if $d^3 \log n \leq o(n)$ then every $d$ -regular graph with $n$ vertices contains a spanning subgraph in which the number of vertices of each degree between $0$ and $d$ is $(1+o(1))\frac{n}{d+1}$ . We also prove that any graph with $n$ vertices and minimum degree $\delta$ contains a spanning subgraph in which no degree is repeated more than $(1+o(1))\frac{n}{\delta +1}+2$ times.

In 1975 Bollobás, Erdős, and Szemerédi asked the following question: given positive integers $n, t, r$ with $2\le t\le r-1$ , what is the largest minimum degree $\delta (G)$ among all $r$ -partite graphs $G$ with parts of size $n$ and which do not contain a copy of $K_{t+1}$ ? The $r=t+1$ case has attracted a lot of attention and was fully resolved by Haxell and Szabó, and Szabó and Tardos in 2006. In this article, we investigate the $r\gt t+1$ case of the problem, which has remained dormant for over 40 years. We resolve the problem exactly in the case when $r \equiv -1 \pmod{t}$ , and up to an additive constant for many other cases, including when $r \geq (3t-1)(t-1)$ . Our approach utilizes a connection to the related problem of determining the maximum of the minimum degrees among the family of balanced $r$ -partite $rn$ -vertex graphs of chromatic number at most $t$ .

We prove the Erdős–Sós conjecture for trees with bounded maximum degree and large dense host graphs. As a corollary, we obtain an upper bound on the multicolour Ramsey number of large trees whose maximum degree is bounded by a constant.

An edge-coloured graph $G$ is called properly connected if any two vertices are connected by a properly coloured path. The proper connection number, $pc(G)$, of a graph $G$, is the smallest number of colours that are needed to colour $G$ such that it is properly connected. Let $\unicode[STIX]{x1D6FF}(n)$ denote the minimum value such that $pc(G)=2$ for any 2-connected incomplete graph $G$ of order $n$ with minimum degree at least $\unicode[STIX]{x1D6FF}(n)$. Brause et al. [‘Minimum degree conditions for the proper connection number of graphs’, Graphs Combin.33 (2017), 833–843] showed that $\unicode[STIX]{x1D6FF}(n)>n/42$. In this note, we show that $\unicode[STIX]{x1D6FF}(n)>n/36$.

A set of graphs are called cospectral if their adjacency matrices have the same characteristic polynomial. In this paper we introduce a simple method for constructing infinite families of cospectral regular graphs. The construction is valid for special cases of a property introduced by Schwenk. For the case of cubic (3-regular) graphs, computational results are given which show that the construction generates a large proportion of the cubic graphs, which are cospectral with another cubic graph.

This paper studies the friendship paradox for weighted and directed networks, from a probabilistic perspective. We consolidate and extend recent results of Cao and Ross and Kramer, Cutler and Radcliffe, to weighted networks. Friendship paradox results for directed networks are given; connections to detailed balance are considered.

The long-standing open problem of finding an upper bound for the Wiener index of a graph in terms of its order and diameter is addressed. Sharp upper bounds are presented for the Wiener index, and the related degree distance and Gutman index, for trees of order $n$ and diameter at most $6$.

We consider numbers and sizes of independent sets in graphs with minimum degree at least d. In particular, we investigate which of these graphs yield the maximum numbers of independent sets of different sizes, and which yield the largest random independent sets. We establish a strengthened form of a conjecture of Galvin concerning the first of these topics.

For $\delta \ge 1$ and $n\ge 1$, consider the simplicial complex of graphs on $n$ vertices in which each vertex has degree at most $\delta$; we identify a given graph with its edge set and admit one loop at each vertex. This complex is of some importance in the theory of semigroup algebras. When $\delta =1$, we obtain the matching complex, for which it is known that there is 3-torsion in degree $d$ of the homology whenever $\left( n-4 \right)/3\le d\le \left( n-6 \right)/2$. This paper establishes similar bounds for $\delta \ge 2$. Specifically, there is 3-torsion in degree $d$ whenever

$$\frac{\left( 3\delta -1 \right)n-8}{6}\le d\le \frac{\delta \left( n-1 \right)-4}{2}.$$

The procedure for detecting torsion is to construct an explicit cycle $z$ that is easily seen to have the property that $3z$ is a boundary. Defining a homomorphism that sends $z$ to a non-boundary element in the chain complex of a certain matching complex, we obtain that $z$ itself is a non-boundary. In particular, the homology class of $z$ has order 3.

A perfect Kt-matching in a graph G is a spanning subgraph consisting of vertex-disjoint copies of Kt. A classic theorem of Hajnal and Szemerédi states that if G is a graph of order n with minimum degree δ(G) ≥ (t − 1)n/t and t|n, then G contains a perfect Kt-matching. Let G be a t-partite graph with vertex classes V1, …, Vt each of size n. We show that, for any γ > 0, if every vertex x ∈ Vi is joined to at least $\bigl ((t-1)/t + \gamma \bigr )n$ vertices of Vj for each j ≠ i, then G contains a perfect Kt-matching, provided n is large enough. Thus, we verify a conjecture of Fischer [6] asymptotically. Furthermore, we consider a generalization to hypergraphs in terms of the codegree.

Gibbs fields are constructed and studied which correspond to systems of real-valued spins (e.g. systems of interacting anharmonic oscillators) indexed by the vertices of unbounded degree graphs of a certain type, for which the Gaussian Gibbs fields need not be existing. In these graphs, the vertex degree growth is controlled by a summability requirement formulated with the help of a generalized Randić index. In particular, it is proven that the Gibbs fields obey uniform integrability estimates, which are then used in the study of the topological properties of the set of Gibbs fields. In the second part, a class of graphs is introduced in which the mentioned summability is obtained by assuming that the vertices of large degree are located at large distances from each other. This is a stronger version of the metric property employed in Bassalygo and Dobrushin (1986).

In this paper we focus on the problem of the degree sequence for a random graph process with edge deletion. We prove that, while a specific parameter varies, the limit degree distribution of the model exhibits critical phenomenon.