一个图的匹配数条件

The Matching Number Condition of a Graph

设G是一个简单图,在图G中任意一个最大匹配的基数叫做G的匹配数,记作v(G),在这篇文章中我们获得了下面的结果,(1)设G是连通的和不完全的,则对于x,y∈v(G)和xyE(G),v(G-{x,y}=v(G)-1的充分必要条件是(a)G[A(G)]是完全的和A(G)的每一个点和C(G)的每一个点相邻,(b)c(D(G))=|A(G)|+1,和(c)y∈D(G-x)对于x,y∈C(G)。(2)设G是连通的和不完全的,则v(G-{x,y})=v(G)-2对于x,y∈V(G)和xyE(G)的充分必要条件是GK_(n,n),其中n≥2。

Let G be a simple graph. The size of any largest matching in G is called the matching number of G and is denoted by v(G). In this paper, we obtain the following. (1) Let G be connected and incomplete. Then v(G-{x, y})=v(G)-1 for x,y ∈V(G) with xy(?)E(G) if and only if (a) G[A(G)] is complete and each of A(G) is adjacent to every point of C(G). (b) c(D(G)) =|A(G)| + 1. and (c) y∈D(G-x) for x.y∈C(G). (2) Let G be connected and incomplete. Then v(G-{x,y}) = v(G)-2 for x,y ∈V(G) with xy(?) E(G) if and only if G(?)Kn,n. where n (?) 2.