论文标题
两分图家族中的横向和二轴置
Transversals and bipancyclicity in bipartite graph families
论文作者
论文摘要
如果两分的图包含偶数偶数的循环，则称为双弯曲图。 Schmeichel和Mitchem的一个定理指出，对于$ n \ geq 4 $，每一个平衡的两部分图形$ 2n $顶点上的每个顶点，其中一个颜色类中的每个顶点的学位都大于$ \ frac {n} {2} {2} $，而其他颜色类中的每个顶点至少具有$ \ freac $ \ freac n} $ c {2} $ bip {2}我们在图形横向的设置中证明了该定理的概括。也就是说，我们表明，给定一个家庭$ \ nathcal {g} $ $ 2n $二分之一的图形在公共集合$ x $ $ x $ $ x $ $ x $ $ 2n $的vertices带有共同均衡的两部分，如果每张$ \ nathcal g $的每图都具有最低限度的$ \ frac {n} $ frac {n} $ frac {n} $ frac {n} $ frac {n} $ {在另一个颜色类中，在每个$ x $的$ x $上都存在一个周期，均匀长度$ 4 \ leq \ ell \ ell \ leq 2n $，最多使用$ \ mathcal g $的每个图。我们还表明，鉴于一个$ n $ n $ bipartite图的家庭$ \ MATHCAL g $在公共集合$ x $ 2n $的dertices符合相同度条件下的$ x $ a $ x $，因此在$ x $上存在一个完美的匹配，该$ x $与$ \ nathcal g $的每张图相恰好使用一个优势。
A bipartite graph is called bipancyclic if it contains cycles of every even length from four up to the number of vertices in the graph. A theorem of Schmeichel and Mitchem states that for $n \geq 4$, every balanced bipartite graph on $2n$ vertices in which each vertex in one color class has degree greater than $\frac{n}{2}$ and each vertex in the other color class has degree at least $\frac{n}{2}$ is bipancyclic. We prove a generalization of this theorem in the setting of graph transversals. Namely, we show that given a family $\mathcal{G}$ of $2n$ bipartite graphs on a common set $X$ of $2n$ vertices with a common balanced bipartition, if each graph of $\mathcal G$ has minimum degree greater than $\frac{n}{2}$ in one color class and minimum degree at least $\frac{n}{2}$ in the other color class, then there exists a cycle on $X$ of each even length $4 \leq \ell \leq 2n$ that uses at most one edge from each graph of $\mathcal G$. We also show that given a family $\mathcal G$ of $n$ bipartite graphs on a common set $X$ of $2n$ vertices meeting the same degree conditions, there exists a perfect matching on $X$ that uses exactly one edge from each graph of $\mathcal G$.
