Perfect Matchings in Claw-free Cubic Graphs

Cited 2 time in webofscience Cited 0 time in scopus
  • Hit : 303
  • Download : 117
Lovasz and Plummer conjectured that there exists a fixed positive constant c such that every cubic n-vertex graph with no cutedge has at least 2(cn) perfect matchings. Their conjecture has been verified for bipartite graphs by Voorhoeve and planar graphs by Chudnovsky and Seymour. We prove that every claw-free cubic n-vertex graph with no cutedge has more than 2(n/12) perfect matchings, thus verifying the conjecture for claw-free graphs.
Publisher
ELECTRONIC JOURNAL OF COMBINATORICS
Issue Date
2011-03
Language
English
Article Type
Article
Citation

ELECTRONIC JOURNAL OF COMBINATORICS, v.18, no.1

ISSN
1077-8926
URI
http://hdl.handle.net/10203/97623
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
18469.pdf(91.59 kB)Download
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 2 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0