BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Jessica McDonald 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.
We prove that if $L(G)$ immerses $K_t$ then $L(mG)$ immerses $K_{mt}$, where $mG$ is the graph obtained from $G$ by replacing each edge in $G$ with a parallel edge of multiplicity $m$. This implies that when $G$ is a simple graph, $L(mG)$ satisfies a conjecture of Abu-Khzam and Langston. We also show that when $G$ is a line graph, $G$ has a $K_t$-immersion iff $G$ has a $K_t$-minor whenever $t\leq 4$, but this equivalence fails in both directions when $t \geq 5$.
Robertson and Seymour proved that the relation of graph immersion is well-quasi-ordered for finite graphs. Their proof uses the results of graph minors theory. Surprisingly, there is a very short proof of the corresponding rough structure theorem for graphs without $K_t$-immersions; it is based on the Gomory-Hu theorem. The same proof also works to establish a rough structure theorem for Eulerian digraphs without $\vec{K}_t$-immersions, where $\vec{K}_t$ denotes the bidirected complete digraph of order $t$.
We consider the problem of immersing the complete digraph on t vertices in a simple digraph. For Eulerian digraphs, we show that such an immersion always exists whenever minimum degree is at least t(t-1), and for t at most 4 minimum degree at least t-1 suffices. On the other hand, we show that there exist non-Eulerian digraphs with all vertices of arbitrarily high in- and outdegree which do not contain an immersion of the complete digraph on 3 vertices. As a side result, we obtain a construction of digraphs with large outdegree in which all cycles have odd length, simplifying a former construction of such graphs by Thomassen.
An immersion of a graph $H$ into a graph $G$ is a one-to-one mapping $f:V(H) \to V(G)$ and a collection of edge-disjoint paths in $G$, one for each edge of $H$, such that the path $P_{uv}$ corresponding to edge $uv$ has endpoints $f(u)$ and $f(v)$. The immersion is strong if the paths $P_{uv}$ are internally disjoint from $f(V(H))$. It is proved that for every positive integer $t$, every simple graph of minimum degree at least $200t$ contains a strong immersion of the complete graph $K_t$. For dense graphs one can say even more. If the graph has order $n$ and has $2cn^2$ edges, then there is a strong immersion of the complete graph on at least $c^2 n$ vertices in $G$ in which each path $P_{uv}$ is of length 2. As an application of these results, we resolve a problem raised by Paul Seymour by proving that the line graph of every simple graph with average degree $d$ has a clique minor of order at least $cd^{3/2}$, where $c>0$ is an absolute constant. For small values of $t$, $1\le t\le 7$, every simple graph of minimum degree at least $t-1$ contains an immersion of $K_t$ (Lescure and Meyniel, DeVos et al.). We provide a general class of examples showing that this does not hold when $t$ is large.
The kth power of a simple graph G, denoted G^k, is the graph with vertex set V(G) where two vertices are adjacent if they are within distance k in G. We are interested in finding lower bounds on the average degree of G^k. Here we prove that if G is connected with minimum degree d > 2 and |V(G)| > (8/3)d, then G^4 has average degree at least (7/3)d. We also prove that if G is a connected d-regular graph on n vertices with diameter at least 3k+3, then the average degree of G^{3k+2} is at least (2k+1)(d+1) - k(k+1) (d+1)^2/n - 1. Both of these results are shown to be essentially best possible; the second is best possible even when n/d is arbitrarily large.