
Let $x,y\in (0,1]$, and let $A,B,C$ be disjoint nonempty stable subsets of a graph $G$, where every vertex in $A$ has at least $x|B|$ neighbours in $B$, and every vertex in $B$ has at least $y|C|$ neighbours in $C$, and there are no edges between $A,C$. We denote by $\phi(x,y)$ the maximum $z$ such that, in all such graphs $G$, there is a vertex $v\in C$ that is joined to at least $z|A|$ vertices in $A$ by two-edge paths. This function has some interesting properties: we show, for instance, that $\phi(x,y)=\phi(y,x)$ for all $x,y$, and there is a discontinuity in $\phi(x,x)$ when $1/x$ is an integer. For $z=1/2, 2/3,1/3,3/4,2/5,3/5$, we try to find the (complicated) boundary between the set of pairs $(x,y)$ with $\phi(x,y)\ge z$ and the pairs with $\phi(x,y)<z$. We also consider what happens if in addition every vertex in $B$ has at least $x|A|$ neighbours in $A$, and every vertex in $C$ has at least $y|B|$ neighbours in $B$. We raise several questions and conjectures; for instance, it is open whether $\phi(x,x)\ge 1/2$ for all $x>1/3$.
Extremal problems in graph theory, bipartite graphs, Distance in graphs, Graph operations (line graphs, products, etc.), 511, Directed graphs (digraphs), tournaments, tripartite digraphs, 05C69, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), directed bipartite graphs, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
Extremal problems in graph theory, bipartite graphs, Distance in graphs, Graph operations (line graphs, products, etc.), 511, Directed graphs (digraphs), tournaments, tripartite digraphs, 05C69, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), directed bipartite graphs, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
