BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Matt DeVos contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We prove that every 3-edge-connected graph $G$ has a 3-flow $ϕ$ with the property that $|\mathop{supp}(ϕ)| \ge \frac{5}{6} |E(G)|$. The graph $K_4$ demonstrates that this $\frac{5}{6}$ ratio is best possible; there is an infinite family where $\frac 56$ is tight.
Mantel's Theorem asserts that a simple $n$ vertex graph with more than $\frac{1}{4}n^2$ edges has a triangle (three mutually adjacent vertices). Here we consider a rainbow variant of this problem. We prove that whenever $G_1, G_2, G_3$ are simple graphs on a common set of $n$ vertices and $|E(G_i)| > ( \frac{ 26 - 2 \sqrt{7} }{81})n^2 \approx 0.2557 n^2$ for $1 \le i \le 3$, then there exist distinct vertices $v_1,v_2,v_3$ so that (working with the indices modulo 3) we have $v_i v_{i+1} \in E(G_i)$ for $1 \le i \le 3$. We provide an example to show this bound is best possible. This also answers a question of Diwan and Mubayi. We include a new short proof of Mantel's Theorem we obtained as a byproduct.
Two well-known results in the world of nowhere-zero flows are Jaeger's 4-flow theorem asserting that every 4-edge-connected graph has a nowhere-zero $\mathbb{Z}_2 \times \mathbb{Z}_2$-flow and Seymour's 6-flow theorem asserting that every 2-edge-connected graph has a nowhere-zero $\mathbb{Z}_6$-flow. Dvořák and the last two authors of this paper extended these results by proving the existence of exponentially many nowhere-zero flows under the same assumptions. We revisit this setting and provide extensions and simpler proofs of these results. The concept of a nowhere-zero flow was extended in a significant paper of Jaeger, Linial, Payan, and Tarsi to a choosability-type setting. For a fixed abelian group $Γ$, an oriented graph $G = (V,E)$ is called $Γ$-connected if for every function $f : E \rightarrow Γ$ there is a flow $ϕ: E \rightarrow Γ$ with $ϕ(e) \neq f(e)$ for every $e \in E$ (note that taking $f = 0$ forces $ϕ$ to be nowhere-zero). Jaeger et al. proved that every oriented 3-edge-connected graph is $Γ$-connected whenever $|Γ| \ge 6$. We prove that there are exponentially many solutions whenever $|Γ| \ge 8$. For the group $\mathbb{Z}_6$ we prove that for every oriented 3-edge-connected $G = (V,E)$ with $\ell = |E| - |V| \ge 11$ and every $f: E \rightarrow \mathbb{Z}_6$, there are at least $2^{ \sqrt{\ell} / \log \ell}$ flows $ϕ$ with $ϕ(e) \neq f(e)$ for every $e \in E$.
Let $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $2$. We prove that $(G,c)$ contains a rainbow cycle of length at most $\lceil \frac{n}{2} \rceil$, which is best possible. Our result settles a special case of a strengthening of the Caccetta-Häggkvist conjecture, due to Aharoni. We also show that the matroid generalization of our main result also holds for cographic matroids, but fails for binary matroids.
The $γ$-graph of a graph $G$ is the graph whose vertices are labelled by the minimum dominating sets of $G$, in which two vertices are adjacent when their corresponding minimum dominating sets (each of size $γ(G)$) intersect in a set of size $γ(G)-1$. We extend the notion of a $γ$-graph from distance-1-domination to distance-$d$-domination, and ask which graphs $H$ occur as $γ$-graphs for a given value of~$d \ge 1$. We show that, for all $d$, the answer depends only on whether the vertices of $H$ admit a labelling consistent with the adjacency condition for a conventional $γ$-graph. This result relies on an explicit construction for a graph having an arbitrary prescribed set of minimum distance-$d$-dominating sets. We then completely determine the graphs that admit such a labelling among the wheel graphs, the fan graphs, and the graphs on at most six vertices. We connect the question of whether a graph admits such a labelling with previous work on induced subgraphs of Johnson graphs.