TOPICS

# Minimal Cover

A minimal cover is a cover for which removal of any single member destroys the covering property. For example, of the five covers of , namely , , , , and , only and are minimal covers.

Similarly, the minimal covers of are given by , , , , , , , and . The numbers of minimal covers of members for , 2, ..., are 1, 2, 8, 49, 462, 6424, 129425, ... (OEIS A046165).

Royle (2000) proved that there is a one-one correspondence between the split graphs on vertices and the minimal covers of a set of size .

Let be the number of minimal covers of with members. Then

where is a binomial coefficient, is a Stirling number of the second kind, and

Special cases include and . The table below gives the a triangle of (OEIS A035348).

 OEIS A000392 A003468 A016111 A046166 A046167 A057668 1 1 2 1 1 3 1 6 1 4 1 25 22 1 5 1 90 305 65 1 6 1 301 3410 2540 171 1 7 1 966 33621 77350 17066 420 1 8 1 3025 305382 2022951 1298346 100814 988

Cover, Lew k-gram, Minimal Edge Cover, Minimal Vertex Cover, Split Graph, Stirling Number of the Second Kind

## Explore with Wolfram|Alpha

More things to try:

## References

Hearne, T. and Wagner, C. "Minimal Covers of Finite Sets." Disc. Math. 5, 247-251, 1973.Macula, A. J. "Covers of a Finite Set." Math. Mag. 67, 141-144, 1994.Macula, A. J. "Lewis Carroll and the Enumeration of Minimal Covers." Math. Mag. 68, 269-274, 1995.Royle, G. F. "Counting Set Covers and Split Graphs." J. Integer Seq. 3, Article 00.2.6, 2000. https://cs.uwaterloo.ca/journals/JIS/VOL3/ROYLE/royle.html.Sloane, N. J. A. Sequences A000392, A003468, A016111, A035348, A046165, A046166, A046167, A046168, and A057668 in "The On-Line Encyclopedia of Integer Sequences."

Minimal Cover

## Cite this as:

Weisstein, Eric W. "Minimal Cover." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MinimalCover.html