Back to Search Start Over

INDUCED MATCHINGS IN SUBCUBIC GRAPHS.

Authors :
JOOS, FELIX
RAUTENBACH, DIETER
SASSE, THOMAS
Source :
SIAM Journal on Discrete Mathematics. 2014, Vol. 28 Issue 1, p468-473. 6p.
Publication Year :
2014

Abstract

We prove that a cubic graph with m edges has an induced matching with at least M/9 edges. Our result generalizes a result for planar graphs due to Kang, Mnich, and Müller (SIAM J. Discrete Math., 26 (2012), pp. 1383-1411) and solves a conjecture of Henning and Rautenbach. [ABSTRACT FROM AUTHOR]

Subjects

Subjects :
*GRAPH theory
*MATCHING theory
*PLANAR graphs
*NUMBER theory
*ABSTRACT algebra

Details

Language :
English
ISSN :
08954801
Volume :
28
Issue :
1
Database :
Academic Search Index
Journal :
SIAM Journal on Discrete Mathematics
Publication Type :
Academic Journal
Accession number :
108624246
Full Text :
https://doi.org/10.1137/130944424
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details