Abstract: In this paper, we consider the average size of independent edge sets, also called matchings, in a graph. We characterize the extremal graphs for the average size of matchings in general graphs and trees. In addition, we obtain inequalities between the average size of matchings and the number of matchings as well as the matching energy, which is defined as the sum of the absolute values of the zeros of the matching polynomial.
Recommendations
Cites work
- Analytic combinatorics
- Extremal results on average subtree density of series-reduced trees
- Graph energy
- Independent sets, matchings, and occupancy fractions
- Matching theory
- Maximizing the mean subtree order
- Monotonicity of the mean order of subtrees
- On the average number of nodes in a subtree of a tree
- On the local and global means of subtree orders
- The average order of a subtree of a tree
- The average size of independent sets of graphs
- The matching energy of a graph
Cited in
(8)- On the average order of a dominating set of a forest
- The average order of dominating sets of a graph
- Mean value for the matching and dominating polynomial
- Extremal graphs for average sizes of maximal matchings
- The average size of maximal matchings in graphs
- A tight upper bound on the average order of dominating sets of a graph
- Extremal trees with fixed order and diameter for average size of maximal matchings
- On average sizes and enumeration of minimal edge covers
This page was built for publication: The average size of matchings in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175789)
