偶图中过给定独立边集的圈

CIRCUITS INCLUDING A GIVEN SET OF INDEPENDENT EDGES

这里考虑的一切图均为简单的,以V(G),E(G)分别表示图G的节点集和边集。设H是G的子图,x∈V(H),用d_H(x)表示H中与节点x相邻节点的个数。如果e=(x,y)∈E(H),x,y是e的端点,则让d_H(e)=d_H(x)+d_H(y)。设A、B是V(G)的两个节点不交的子集,用E(A:B)表示G中一端在A中另一端在B中边的个数。

The main result in this paper is as follows:Let G=(A,B;E) be abipartite graph with 2n vertices.If x∈A,y∈B,(x,y)∈E,we have d(x)+d(y)≥(4n+3)/3.Then there exists a circuit including S,where S is a set of independent edges.