Upper bounds for the average size of maximal matchings in bicyclic graphs

Abstract

For a graph $G$, let avm($G$) denote the average size of its maximal matchings. Engbers and Erey initiated the extremal study of this parameter and asked for extensions from trees and unicyclic graphs to $k$-cyclic graphs. In this paper, we determine the maximum value of avm($G$) over all connected bicyclic graphs with $n$ vertices and $n+1$ edges. If $n\ge 5$ is odd, then \[ \text{avm}(G)\le \frac{n-1}{2}, \] and we characterize all graphs attaining equality. For $n=6$, the maximum value is 13/5, attained uniquely by $\Theta (1,3,3)$. If $n\ge 8$ is even, then \[ \text{avm}(G)\le \frac{n}{2}-1+\frac{2}{n-4}. \] Equality holds precisely for the graph obtained from two copies of $C_4$ joined by an edge by attaching $(n-8)/2$ pendant 2-paths to one endpoint of the joining edge, and, when $n\ge 10$, for the graph obtained from two copies of $C_4$ joined by a path of length 2 by attaching one leaf and $(n-10)/2$ pendant 2-paths to the internal vertex of the joining path. The proofs combine structural characterizations of odd-order extremal graphs with counting and switching arguments based on perfect matchings.

arXiv comment21 pages, 4 figures