On the forced matching numbers of bipartite graphs

Adams, P., Mahdian, M. and Mahmoodian, E. S. (2004) On the forced matching numbers of bipartite graphs. Discrete Mathematics, 281 1-3: 1-12. doi:10.1016/j.disc.2002.10.002

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Adams, P.
Mahdian, M.
Mahmoodian, E. S.
Title On the forced matching numbers of bipartite graphs
Journal name Discrete Mathematics   Check publisher's open access policy
ISSN 0012-365X
Publication date 2004
Sub-type Article (original research)
DOI 10.1016/j.disc.2002.10.002
Volume 281
Issue 1-3
Start page 1
End page 12
Total pages 12
Editor P. L. Hammer
Place of publication Netherlands
Publisher Elsevier BV, North-Holland
Collection year 2004
Language eng
Subject C1
230101 Mathematical Logic, Set Theory, Lattices And Combinatorics
780101 Mathematical sciences
Abstract Let G be a graph that admits a perfect matching. A forcing set for a perfect matching M of G is a subset S of M, such that S is contained in no other perfect matching of G. This notion has arisen in the study of finding resonance structures of a given molecule in chemistry. Similar concepts have been studied for block designs and graph colorings under the name defining set, and for Latin squares under the name critical set. There is some study of forcing sets of hexagonal systems in the context of chemistry, but only a few other classes of graphs have been considered. For the hypercubes Q(n), it turns out to be a very interesting notion which includes many challenging problems. In this paper we study the computational complexity of finding the forcing number of graphs, and we give some results on the possible values of forcing number for different matchings of the hypercube Q(n). Also we show an application to critical sets in back circulant Latin rectangles. (C) 2003 Elsevier B.V. All rights reserved.
Keyword Forcing Number
Matching In Graphs
Unique Matchings
Q-Index Code C1

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 20 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 24 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Wed, 15 Aug 2007, 02:58:36 EST