Some results on concatenating bipartite graphs
Some results on concatenating bipartite graphs
复制标题
连接二部图的一些结果
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Patrick Hompe
中科院分区：
文献类型：
--
作者：
Patrick Hompe
我们考虑两个函数$Phi$和$Psi$，定义如下。设$X，y在(0，1]$中，且$A，B，C$是图$G$中不相交的非空子集，其中$A$中的每个顶点在$B$中至少有$x|B|$邻居，$B$中的每个顶点在$C$中至少有$y|C|$邻居.我们用$Phi(x，y)$表示最大值$z$，使得在所有这样的图$G$中，C$中有一个顶点$v通过两条边路与$A$中的至少$z|A|$顶点相连。此外，如果我们要求$B$中的每个顶点在$A$中至少有$x|A|$邻居，并且$C$中的每个顶点在$C$中至少有$y|B|$邻居，则我们用$psi(x，y)$表示最大的$z$，使得在所有这样的图$G$中，在C$中有一个顶点$v通过两条边路连接到$A$中的至少$z|A|$顶点。M.Chudnovsky，P.Hompe，A.Scott，P.Seymour和S.Spirkl在他们最近的论文Cite{Our Paper}中引入了这些函数，证明了关于它们的一些一般性结果，并分析了它们大于或等于$1/2，2/3，$和$1/3$的情况。在这里，我们通过分析它们何时大于或等于$3/4、2/5、$和$3/5$来扩展他们的结果。
We consider two functions $phi$ and $psi$, defined as follows. Let $x,y in (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 $v in C$ 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 $v in C$ that is joined to at least $z|A|$ vertices in $A$ by two-edge paths. In their recent paper cite{ourpaper}, 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$.