To save content items to your account,
please confirm that you agree to abide by our usage policies.
If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account.
Find out more about saving content to .
To save content items to your Kindle, first ensure no-reply@cambridge.org
is added to your Approved Personal Document E-mail List under your Personal Document Settings
on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part
of your Kindle email address below.
Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations.
‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi.
‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
The game domination numbers $\gamma _{\mathrm {g}}$ and $\gamma _{\mathrm {g}}^\prime $, and the game total domination numbers $\gamma _{\mathrm {{tg}}}$ and $\gamma _{\mathrm {{tg}}}^\prime $ are investigated on Sierpiński graphs $S_p^n$. For the domination game, the trivial bounds arising from the known domination number and the Grundy domination number of $S_p^n$ are significantly improved by proving that $(2p-3)p^{n-2}\leq \gamma _{\mathrm {g}}(S_p^n), \gamma _{\mathrm {g}}^\prime (S_p^n) \leq (2p-2)p^{n-2}$. For the total domination game, the bounds $\gamma _{\mathrm {{tg}}}(S_p^n), \gamma _{\mathrm {{tg}}}^\prime (S_p^n) \geq (2p-2)p^{n-2}$ are established.
Given a permutation group G, the derangement graph of G is defined with vertex set G, where two elements x and y are adjacent if and only if $xy^{-1}$ is a derangement. We establish that if G is transitive with degree exceeding 30, then the derangement graph of G contains a complete subgraph with four vertices. In the process, we determine all transitive groups whose derangement graph does not contain a complete subgraph on four vertices. As a consequence, if G is a normal subgroup of A such that $|A : G| = 3$ and U is a subgroup of G satisfying $G = \bigcup _{a \in A} U^a$, then $|G : U| \leq 10$. This provides support for a conjecture by Neumann and Praeger concerning Kronecker classes.
We establish several new results on the existence of probability distributions on the independent sets in triangle-free graphs where each vertex is present with a given probability. This setting was introduced and studied under the name of “fractional coloring with local demands” by Kelly and Postle and is closely related to the well-studied fractional chromatic number of graphs.
Our first main result strengthens Shearer’s classic bound on independence number, proving that for every triangle-free graph G there exists a distribution over independent sets where each vertex v appears with probability $(1-o(1))\frac {\ln d_G(v)}{d_G(v)}$, resolving a conjecture by Kelly and Postle. This in turn implies new upper bounds on the fractional chromatic number of triangle-free graphs with a prescribed number of vertices or edges, which resolves a conjecture by Cames van Batenburg et al. and addresses yet another one by the same authors.
Our second main result resolves Harris’ conjecture on triangle-free d-degenerate graphs, showing that such graphs have fractional chromatic number at most $(4+o(1))\frac {d}{\ln d}$. As previously observed by various authors, this in turn has several interesting consequences. A notable example is that every triangle-free graph with minimum degree d contains a bipartite induced subgraph of minimum degree $\Omega (\log d)$. This settles a conjecture by Esperet, Kang, and Thomassé.
The main technique employed to obtain our results is the analysis of carefully designed random processes on vertex-weighted triangle-free graphs that preserve weights in expectation. The analysis of these processes yields weighted generalizations of the aforementioned results that may be of independent interest.
The hard-core model has as its configurations the independent sets of some graph instance $G$. The probability distribution on independent sets is controlled by a ‘fugacity’ $\lambda \gt 0$, with higher $\lambda$ leading to denser configurations. We investigate the mixing time of Glauber (single-site) dynamics for the hard-core model on restricted classes of bounded-degree graphs in which a particular graph $H$ is excluded as an induced subgraph. If $H$ is a subdivided claw then, for all $\lambda$, the mixing time is $O(n\log n)$, where $n$ is the order of $G$. This extends a result of Chen and Gu for claw-free graphs. When $H$ is a path, the set of possible instances is finite. For all other $H$, the mixing time is exponential in $n$ for sufficiently large $\lambda$, depending on $H$ and the maximum degree of $G$.
Let $\Gamma $ be a compact Polish group of finite topological dimension. For a countably infinite subset $S\subseteq \Gamma $, a domatic$\aleph _0$-partition (for its Schreier graph on $\Gamma $) is a partial function $f:\Gamma \rightharpoonup \mathbb {N}$ such that for every $x\in \Gamma $, one has $f[S\cdot x]=\mathbb {N}$. We show that a continuous domatic $\aleph _0$-partition exists, if and only if a Baire measurable domatic $\aleph _0$-partition exists, if and only if the topological closure of S is uncountable. A Haar measurable domatic $\aleph _0$-partition exists for all choices of S. We also investigate domatic partitions in the general descriptive graph combinatorial setting.
If G is a graph, then $X\subseteq V(G)$ is a general position set if for every two vertices $v,u\in X$ and every shortest $(u,v)$-path P, no inner vertex of P lies in X. We propose three algorithms to compute a largest general position set in G: an integer linear programming algorithm, a genetic algorithm and a simulated annealing algorithm. These approaches are supported by examples from different areas of graph theory.
We present a short and simple proof of the celebrated hypergraph container theorem of Balogh–Morris–Samotij and Saxton–Thomason. On a high level, our argument utilises the idea of iteratively taking vertices of largest degree from an independent set and constructing a hypergraph of lower uniformity which preserves independent sets and inherits edge distribution. The original algorithms for constructing containers also remove in each step vertices of high degree, which are not in the independent set. Our modified algorithm postpones this until the end, which surprisingly results in a significantly simplified analysis.
A tantalizing open problem, posed independently by Stiebitz in 1995 and by Alon in 1996 and again in 2006, asks whether for every pair of integers $s,t \ge 1$ there exists a finite number $F(s,t)$ such that the vertex set of every digraph of minimum out-degree at least $F(s,t)$ can be partitioned into non-empty parts $A$ and $B$ such that the subdigraphs induced on $A$ and $B$ have minimum out-degree at least $s$ and $t$, respectively.
In this short note, we prove that if $F(2,2)$ exists, then all the numbers $F(s,t)$ with $s,t\ge 1$ exist and satisfy $F(s,t)=\Theta (s+t)$. In consequence, the problem of Alon and Stiebitz reduces to the case $s=t=2$. Moreover, the numbers $F(s,t)$ with $s,t \ge 2$ either all exist and grow linearly, or all of them do not exist.
For a nondegenerate r-graph F, large n, and t in the regime $[0, c_{F} n]$, where $c_F>0$ is a constant depending only on F, we present a general approach for determining the maximum number of edges in an n-vertex r-graph that does not contain $t+1$ vertex-disjoint copies of F. In fact, our method results in a rainbow version of the above result and includes a characterization of the extremal constructions.
Our approach applies to many well-studied hypergraphs (including graphs) such as the edge-critical graphs, the Fano plane, the generalized triangles, hypergraph expansions, the expanded triangles, and hypergraph books. Our results extend old results of Erdős [13], Simonovits [76], and Moon [58] on complete graphs, and can be viewed as a step toward a general density version of the classical Corrádi–Hajnal [10] and Hajnal–Szemerédi [32] theorems.
Our method relies on a novel understanding of the general properties of nondegenerate Turán problems, which we refer to as smoothness and boundedness. These properties are satisfied by a broad class of nondegenerate hypergraphs and appear to be worthy of future exploration.
For each uniformity $k \geq 3$, we construct $k$ uniform linear hypergraphs $G$ with arbitrarily large maximum degree $\Delta$ whose independence polynomial $Z_G$ has a zero $\lambda$ with $\left \vert \lambda \right \vert = O\left (\frac {\log \Delta }{\Delta }\right )$. This disproves a recent conjecture of Galvin, McKinley, Perkins, Sarantis, and Tetali.
Let G and H be two vertex disjoint graphs. The join$G+H$ is the graph with $V(G+H)=V(G)+V(H)$ and $E(G+H)=E(G)\cup E(H)\cup \{xy\;|\; x\in V(G), y\in V(H)\}$. A (finite) linear forest is a graph consisting of (finite) vertex disjoint paths. We prove that for any finite linear forest F and any nonnull graph H, if $\{F, H\}$-free graphs have a $\chi $-binding function $f(\omega )$, then $\{F, K_n+H\}$-free graphs have a $\chi $-binding function $kf(\omega )$ for some constant k.
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 Mathematics344 (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}.$
In an isolate-free graph G, a subset S of vertices is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number of G, denoted by $\gamma _{t2}(G)$, is the minimum cardinality of a semitotal dominating set in G. Goddard, Henning and McPillan [‘Semitotal domination in graphs’, Utilitas Math.94 (2014), 67–81] characterised the trees and graphs of minimum degree 2 with semitotal domination number half their order. In this paper, we characterise all graphs whose semitotal domination number is half their order.
Given a graph $F$, we consider the problem of determining the densest possible pseudorandom graph that contains no copy of $F$. We provide an embedding procedure that improves a general result of Conlon, Fox, and Zhao which gives an upper bound on the density. In particular, our result implies that optimally pseudorandom graphs with density greater than $n^{-1/3}$ must contain a copy of the Peterson graph, while the previous best result gives the bound $n^{-1/4}$. Moreover, we conjecture that the exponent $1/3$ in our bound is tight. We also construct the densest known pseudorandom $K_{2,3}$-free graphs that are also triangle-free. Finally, we give a different proof for the densest known construction of clique-free pseudorandom graphs due to Bishnoi, Ihringer, and Pepe that they have no large clique.
The minimum number of idempotent generators is calculated for an incidence algebra of a finite poset over a commutative ring. This quantity equals either $\lceil \log _2 n\rceil $ or $\lceil \log _2 n\rceil +1$, where n is the cardinality of the poset. The two cases are separated in terms of the embedding of the Hasse diagram of the poset into the complement of the hypercube graph.
In an isolate-free graph G, a subset S of vertices is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number of G, denoted by $\gamma _{t2}(G)$, is the minimum cardinality of a semitotal dominating set in G. Using edge weighting functions on semitotal dominating sets, we prove that if $G\neq N_2$ is a connected claw-free graph of order $n\geq 6$ with minimum degree $\delta (G)\geq 3$, then $\gamma _{t2}(G)\leq \frac{4}{11}n$ and this bound is sharp, disproving the conjecture proposed by Zhu et al. [‘Semitotal domination in claw-free cubic graphs’, Graphs Combin.33(5) (2017), 1119–1130].
The Hoffman ratio bound, Lovász theta function, and Schrijver theta function are classical upper bounds for the independence number of graphs, which are useful in graph theory, extremal combinatorics, and information theory. By using generalized inverses and eigenvalues of graph matrices, we give bounds for independence sets and the independence number of graphs. Our bounds unify the Lovász theta function, Schrijver theta function, and Hoffman-type bounds, and we obtain the necessary and sufficient conditions of graphs attaining these bounds. Our work leads to some simple structural and spectral conditions for determining a maximum independent set, the independence number, the Shannon capacity, and the Lovász theta function of a graph.
We study the locations of complex zeroes of independence polynomials of bounded-degree hypergraphs. For graphs, this is a long-studied subject with applications to statistical physics, algorithms, and combinatorics. Results on zero-free regions for bounded-degree graphs include Shearer’s result on the optimal zero-free disc, along with several recent results on other zero-free regions. Much less is known for hypergraphs. We make some steps towards an understanding of zero-free regions for bounded-degree hypergaphs by proving that all hypergraphs of maximum degree $\Delta$ have a zero-free disc almost as large as the optimal disc for graphs of maximum degree $\Delta$ established by Shearer (of radius $\sim 1/(e \Delta )$). Up to logarithmic factors in $\Delta$ this is optimal, even for hypergraphs with all edge sizes strictly greater than $2$. We conjecture that for $k\ge 3$, $k$-uniform linear hypergraphs have a much larger zero-free disc of radius $\Omega (\Delta ^{- \frac{1}{k-1}} )$. We establish this in the case of linear hypertrees.