Meyniel's conjecture holds for random d‐regular graphs

In the game of cops and robber, the cops try to capture a robber moving on the vertices of the graph. The minimum number of cops required to win on a given graph G is called the cop number of G. The biggest open conjecture in this area is the one of Meyniel, which asserts that for some absolute constant C, the cop number of every connected graph G is at most . In a separate paper, we showed that Meyniel's conjecture holds asymptotically almost surely for the binomial random graph. The result was obtained by showing that the conjecture holds for a general class of graphs with some specific expansion‐type properties. In this paper, this deterministic result is used to show that the conjecture holds asymptotically almost surely for random d‐regular graphs when d = d(n) ≥ 3.     

1‐Factor and Cycle Covers of Cubic Graphs

Let G be a bridgeless cubic graph. Consider a list of k 1‐factors of G. Let be the set of edges contained in precisely i members of the k 1‐factors. Let be the smallest over all lists of k 1‐factors of G. Any list of three 1‐factors induces a core of a cubic graph. We use results on the structure of cores to prove sufficient conditions for Berge‐covers and for the existence of three 1‐factors with empty intersection. Furthermore, if , then is an upper bound for the girth of G. We also prove some new upper bounds for the length of shortest cycle covers of bridgeless cubic graphs. Cubic graphs with have a 4‐cycle cover of length and a 5‐cycle double cover. These graphs also satisfy two conjectures of Zhang 18 . We also give a negative answer to a problem stated in 18 .     

Nonvertex‐Balanced Factors in Random Graphs

We prove part of a conjecture by Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28.) regarding threshold functions for the existence of an H‐factor in a random graph . We prove that the conjectured threshold function is correct for any graph H which is not covered by its densest subgraphs. We also demonstrate that the main result of Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28) generalizes to multigraphs, digraphs, and a multipartite model.     

On independent sets in random graphs

The independence number of a sparse random graph G(n,m) of average degree d = 2m/n is well‐known to be with high probability, with in the limit of large d. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size , i.e., about half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with size for any fixed (independent of both d and n). In this paper we prove that the combinatorial structure of the independent set problem in random graphs undergoes a phase transition as the size k of the independent sets passes the point . Roughly speaking, we prove that independent sets of size form an intricately rugged landscape, in which local search algorithms seem to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independent sets. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 436–486, 2015     

Addendum to: “Hamilton-laceable bi-powers of locally finite bipartite graphs” [Discrete Math. 345 (2022) 112777]

In this addendum we give a short and easy negative answer to the two questions raised in the original article.