Extremal graphs for average size of maximal matchings in bicyclic graphs
For a graph \(G\), let $avm(G)$ denote the average size of its maximal matchings. This parameter was introduced by Engbers and Erey in the study of extremal problems for maximal matchings, and they asked for extensions from trees and unicyclic graphs to \(k\)-cyclic graphs. In this paper, we solve the first non-unicyclic case by determining the minimum value of $avm(G)$ over all connected bicyclic graphs with \(n\) vertices and \(n+1\) edges. We prove that, for every connected bicyclic graph \(G\) of order \(n\ge 5\), \[ \operatorname{avm}(G)\ge \frac{4n-11}{2n-5}. \] Moreover, equality…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.28033
curl -X POST /api/v1/records/arxiv/2604.28033/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.28033/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'