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 language | English |
---|---|
Article number | 113263 |
Journal | Discrete Mathematics |
Volume | 346 |
Issue number | 3 |
DOIs | |
Publication status | Published - Mar 2023 |
Keywords
- 2-Connected graph
- Matching number
- Maximum degree
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics