一些图的完美匹配多面体的维数

Dimension of Perfect Matching Polytope of Some Graphs

设 G为一个简单图 .G的一条边为容许边 ,如果它属于 G的某个完善匹配 .一个具有完美匹配的图 G是基本的 ,如果由它的容许边所导出的子图是连通的 .G是双因子临界的 ,如果 G至少包含一条边且对 G中任意的两个不同的顶点 x与 y,G- x- y均有完美匹配 .一个双因子临界图是一个砖块 ,如果它是 3-连通的 .称 G是顶点可传递的 ,如果其自同构群是顶点传递的 .G的完美匹配多面体记作 PM(G) .得到以下结果 :(a)设 G是一个连通的顶点可传递图 .如果 |V(G) |为偶数 ,则 G或者是一个基本的二部图 ,或者是一个砖块 .(b)设 G是一个连通的顶点可传递图 .如果 |V(G) |为偶数 ,则当 G是二部图时 ,dim PM(G) =|E(G) |- |V(G) |+1;当 G是一个砖块时 ,dim PM(G) =|E(G) |- |V(G)

Let G be a simple graph. A line of graph G is allowed if it lies in some perfect matching of G . A graph G with a perfect matching is elementary if its allowed lines form a connected subgraph. G is bicritical if G contains a line and G-x-y has a perfect matching for every pair of distinct points x and y in G . A bicritical graph is a brick if it is 3 connected. G is called point transitive if it has a point transitive automorphism group. Let PM(G) denote the perfect matching polytope of the graph G . The following results are obtained: (a) Let G be a connected point transitive graph. If |V(G)| is even, then G is either an elementary bipartite graph or a brick. (b) Let G be a connected point transitive graph. If |V(G)| is even, then: when G is bipartite, dim PM(G)= |E(G)| -|V(G)|+1; when G is a brick, dim PM(G)= |E(G)|-|V(G)| .