TOPICS
Search

Minimal Cover

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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

Similarly, the minimal covers of {1,2,3} are given by {{1,2,3}}, {{1,2},{1,3}}, {{2},{1,3}}, {{2,3},{1,2}}, {{2,3},{1,3}}, {{2,3},{1}}, {{3},{2},{1}}, and {{3},{1,2}}. The numbers of minimal covers of a fixed labeled n-element set, with unordered cover members, for n=1, 2, ..., are 1, 2, 8, 49, 462, 6424, 129425, ... (OEIS A046165).

Royle (2000) proved that there is a one-to-one correspondence between split graphs on n vertices, considered up to graph isomorphism, and minimal covers of an n-element set up to permutations of its elements.

Let mu(n,k) be the number of minimal covers of {1,...,n} with k members, for positive integers n and 1<=k<=n. Then

mu(n,k)=1/(k!)sum_(m=k)^(alpha_k)(2^k-k-1; m-k)m!s(n,m),

where (n; k) is a binomial coefficient, s(n,m) is a Stirling number of the second kind, and

alpha_k=min(n,2^k-1).

Special cases include mu(n,1)=1 and mu(n,2)=s(n+1,3). The table below gives a triangle of mu(n,k) (OEIS A035348).

nk=1k=2k=3k=4k=5k=6k=7
OEISA000392A003468A016111A046166A046167A057668
11
211
3161
4125221
5190305651
61301341025401711
719663362177350170664201
81302530538220229511298346100814988

See also

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

Explore with Wolfram|Alpha

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."

Referenced on Wolfram|Alpha

Minimal Cover

Cite this as:

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

Subject classifications