A generalization of Petersen's matching theorem

Michael A. Henning, Zekhaya B. Shozi

Research output: Contribution to journalArticlepeer-review

Abstract

One of the earliest results in graph theory is Petersen's matching theorem from 1891 which states that every bridgeless cubic graph contains a perfect matching. Since the vertex-connectivity and edge-connectivity in a connected cubic graph are equal, Petersen's theorem can be stated as follows: If G is a 2-connected 3-regular graph of order n, then [Formula presented], where α(G) denotes the matching number of G. We generalize Petersen's theorem and prove that for k≥3 an odd integer, if G is a 2-connected k-regular graph of order n, then [Formula presented]. The case when k is even behaves differently. In this case, for k≥4 even, if G is a 2-connected k-regular graph of order n, then [Formula presented]. For all k≥3, if G is a 2-connected graph of order n and maximum degree k that is not necessarily regular, then we show that [Formula presented]. In all the above bounds, the extremal graphs are characterized.

Original languageEnglish
Article number113263
JournalDiscrete Mathematics
Volume346
Issue number3
DOIs
Publication statusPublished - Mar 2023

Keywords

  • 2-Connected graph
  • Matching number
  • Maximum degree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'A generalization of Petersen's matching theorem'. Together they form a unique fingerprint.

Cite this