The minimum forcing number for the torus and hypercube

被引：52

作者：

Riddle, ME ^{[1
]}

机构：

[1] Carleton Coll, Dept Math, Northfield, MN 55057 USA

来源：

DISCRETE MATHEMATICS | 2002年 / 245卷 / 1-3期

基金：

美国国家科学基金会;

关键词：

forcing number; perfect matching; torus; hypercube;

D O I：

10.1016/S0012-365X(01)00228-X

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a graph with a perfect matching M. Define the forcing number of M in G to be the smallest size of a subset S subset of M that is in no other perfect matching. In this paper, we present a property of bipartite graphs G that acts as a lower bound on the forcing number of perfect matchings in G. We then apply this to the torus and the hypercube, proving that the minimum forcing number of a perfect matching on a 2m x 2n torus with m greater than or equal to n is 2n, and that the minimum forcing number on an n-dimensional hypercube is 2(n)/4 if n is even. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：283 / 292

页数：10

共 5 条

[1]

ALON N, COMMUNICATION

[2] GRAPHICAL PROPERTIES OF POLYHEXES - PERFECT MATCHING VECTOR AND FORCING [J].