Some results on concatenating bipartite graphs

arXiv1908.07453MaRDI QIDQ6323944FDOQ6323944

Authors: Patrick Hompe 

Publication date: 18 August 2019

Abstract: We consider two functions $phi$ and $psi$, defined as follows. Let $x,yin(0,1]$ and let $A,B,C$ be disjoint nonempty subsets of a graph $G$, where every vertex in $A$ has at least $x|B|$ neighbors in $B$, and every vertex in $B$ has at least $y|C|$ neighbors in $C$. We denote by $phi(x,y)$ the maximum $z$ such that, in all such graphs $G$, there is a vertex $vinC$ that is joined to at least $z|A|$ vertices in $A$ by two-edge paths. If in addition we require that every vertex in $B$ has at least $x|A|$ neighbors in $A$, and every vertex in $C$ has at least $y|B|$ neighbors in $C$, we denote by $psi(x,y)$ the maximum $z$ such that, in all such graphs $G$, there is a vertex $vinC$ that is joined to at least $z|A|$ vertices in $A$ by two-edge paths. In their recent paper, M. Chudnovsky, P. Hompe, A. Scott, P. Seymour, and S. Spirkl introduced these functions, proved some general results about them, and analyzed when they are greater than or equal to $1/2,2/3,$ and $1/3$. Here, we extend their results by analyzing when they are greater than or equal to $3/4,2/5,$ and $3/5$.

This page was built for publication: Some results on concatenating bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323944)