Forcing matching numbers of fullerene graphs

Heping Zhang; Dong Ye; Wai Chee Shiu

doi:10.1016/j.dam.2009.10.013

Forcing matching numbers of fullerene graphs

Heping Zhang, Dong Ye, Wai Chee Shiu^*

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Journal article › peer-review

41 Citations (Scopus)

Abstract

The forcing number or the degree of freedom of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matchings of G. In this paper we show that the forcing numbers of perfect matchings in a fullerene graph are not less than 3 by applying the 2-extendability and cyclic edge-connectivity 5 of fullerene graphs obtained recently, and Kotzig's classical result about unique perfect matching as well. This lower bound can be achieved by infinitely many fullerene graphs.

Original language	English
Pages (from-to)	573-582
Number of pages	10
Journal	Discrete Applied Mathematics
Volume	158
Issue number	5
DOIs	https://doi.org/10.1016/j.dam.2009.10.013
Publication status	Published - 6 Mar 2010

User-Defined Keywords

Degree of freedom
Forcing number
Fullerene graph
Perfect matching

Access to Document

10.1016/j.dam.2009.10.013

Cite this

@article{d5cabb0b4ed84884b8aa939836eb9bba,

title = "Forcing matching numbers of fullerene graphs",

abstract = "The forcing number or the degree of freedom of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matchings of G. In this paper we show that the forcing numbers of perfect matchings in a fullerene graph are not less than 3 by applying the 2-extendability and cyclic edge-connectivity 5 of fullerene graphs obtained recently, and Kotzig's classical result about unique perfect matching as well. This lower bound can be achieved by infinitely many fullerene graphs.",

keywords = "Degree of freedom, Forcing number, Fullerene graph, Perfect matching",

author = "Heping Zhang and Dong Ye and Shiu, {Wai Chee}",

year = "2010",

month = mar,

day = "6",

doi = "10.1016/j.dam.2009.10.013",

language = "English",

volume = "158",

pages = "573--582",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - Forcing matching numbers of fullerene graphs

AU - Zhang, Heping

AU - Ye, Dong

AU - Shiu, Wai Chee

PY - 2010/3/6

Y1 - 2010/3/6

N2 - The forcing number or the degree of freedom of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matchings of G. In this paper we show that the forcing numbers of perfect matchings in a fullerene graph are not less than 3 by applying the 2-extendability and cyclic edge-connectivity 5 of fullerene graphs obtained recently, and Kotzig's classical result about unique perfect matching as well. This lower bound can be achieved by infinitely many fullerene graphs.

AB - The forcing number or the degree of freedom of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matchings of G. In this paper we show that the forcing numbers of perfect matchings in a fullerene graph are not less than 3 by applying the 2-extendability and cyclic edge-connectivity 5 of fullerene graphs obtained recently, and Kotzig's classical result about unique perfect matching as well. This lower bound can be achieved by infinitely many fullerene graphs.

KW - Degree of freedom

KW - Forcing number

KW - Fullerene graph

KW - Perfect matching

UR - http://www.scopus.com/inward/record.url?scp=75449099058&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2009.10.013

DO - 10.1016/j.dam.2009.10.013

M3 - Journal article

AN - SCOPUS:75449099058

SN - 0166-218X

VL - 158

SP - 573

EP - 582

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 5

ER -

Forcing matching numbers of fullerene graphs

Abstract

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this