On Average Sizes and Enumeration of Minimal Edge Covers

Authors

John Engbers, Marquette UniversityFollow
Aysel Erey, Utah State University

Document Type

Article

Publication Date

8-15-2025

Publisher

Elsevier

Source Publication

Discrete Applied Mathematics

Source ISSN

0166-218X

Original Item ID

DOI: 10.1016/j.dam.2025.04.022

Abstract

An edge cover M of a graph G is a subset of edges such that every vertex G of  is an end-vertex of some edge in M. An edge cover is called a minimal edge cover if it does not properly contain another edge cover. Let mec (G) be the number of minimal edge covers of G, and let mec (G) be the average size of a minimal edge cover of G. We consider the extremal values of mec (G) and mec_av (G) when G is restricted to various families of graphs. In particular, we determine the graphs G which minimize mec (G) among all graphs with fixed order, and among the family of 2-regular graphs with fixed order. We also determine the graphs which maximize mec (G) within the families of trees, of unicyclic graphs with fixed order, and of 2-regular graphs with a fixed order. Finally, we provide a characterization of all extremal graphs for the maximum and minimum values of mec_av (G) among all graphs G with fixed order.

Comments

Accepted version. Discrete Applied Mathematics, Vol. 371 (August 15, 2025): 148-164. DOI. © Elsevier. Used with permission.

Recommended Citation

Engbers, John and Erey, Aysel, "On Average Sizes and Enumeration of Minimal Edge Covers" (2025). Mathematical and Statistical Science Faculty Research and Publications. 148.
https://epublications.marquette.edu/math_fac/148