A GENERALIZATION OF PETERSEN THEOREM

Authors
Citation
Mx. Goemans, A GENERALIZATION OF PETERSEN THEOREM, Discrete mathematics, 115(1-3), 1993, pp. 277-282
Citations number
6
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
ISSN journal
0012365X
Volume
115
Issue
1-3
Year of publication
1993
Pages
277 - 282
Database
ISI
SICI code
0012-365X(1993)115:1-3<277:AGOPT>2.0.ZU;2-J
Abstract
Petersen's theorem asserts that any cubic graph with at most 2 cut edg es has a perfect matching. We generalize this classical result by show ing that any cubic graph G = (V, E) with at most 1 cut edge has a T-jo in of cardinality less than or equal to Absolute value of V/2 for ever y even subset T of vertices. Our result is based on the Edmonds-Johnso n min-max relation for T-joins.