A simplified version
Given a complete graph $K_n$ on $[n]$ for some $n \in \mathbb N$, we consider all the possible edge clique covers of $K_n$. Specifically, we aim to use a sequence of pairwise distinct node sets $\mathcal{V} = \{V_1, V_2, \ldots, V_k\}$ such that
- Each node set is a subset of [n], i.e., $V_i \subseteq [n], \forall i$
- Each node set is unique, i.e., $V_i \neq V_j, \forall i \neq j$
- Each edge in $K_n$ is covered, i.e., $\exists V_i$ s.t. $\{ v_1, v_2 \} \subseteq V_i, \forall v_1, v_2 \in [n]$
- The cover is minimum in that we cannot remove any node set while still covering all the edges in $K_n$, i.e., $\nexists \mathcal{V}' \subsetneq \mathcal{V}$ such that $\mathcal{V}'$ also covers all the edges in $K_n$
Question: How many different $\mathcal{V}$'s are there for a given $n$?
Basic analysis: Due to condition (4.), each $V_i$ should contain at least two elements and there must not be $V_j \subsetneq V_i$.
A naive bound: Let $c_n$ be the number of such $\mathcal{V}$'s. Let $S(n, k)$ be the number of different ways to partition $[n]$ into $k$ disjoint non-empty subsets, i.e., the Stirling number of the second kind w.r.t. $n$ and $k$. For each $k$-partition $V = \bigcup_{i = 1}^k V_i$ with $k \geq 3$, we can construct $\mathcal V = \{V_i \cup V_j \mid i \neq j \in [k]\}$ with $|\mathcal V| = \binom{k}{2}$. For $k = 1, 2$, the above $\mathcal V$ would be simply $\mathcal V = \{[n]\}$. Therefore, it is easy to see that $c_n \geq 1 + \sum_{k = 3}^{n} S(n, k)$, which is related to the Bell number $B(n) = \sum_{k = 0}^n S(n, k)$.
Special cases: When $n = 3$, we have the following two cases and the bound is tight.
- $(\{1, 2, 3\})$
- $(\{1, 2\}, \{1, 3\}, \{2, 3\})$
Below is my original question.
Given a complete graph $K_n$ on $[n]$ for some $n \in \mathbb N$, we consider all the possible edge clique covers of $K_n$. Specifically, we aim to use a sequence of pairwise distinct node sets $(V_1, V_2, \ldots, V_k)$ such that (1) $V_i \subseteq [n], \forall i$, (2) each edge in $K_n$ is covered, i.e., $\exists V_i$ s.t. $\{ v_1, v_2 \} \subseteq V_i, \forall v_1, v_2 \in [n]$, and (3) each $V_i$ is effective, covering at least one edge that is not covered by the previous $V_j$'s with $j < i$, i.e., $\exists v_1, v_2 \in [n]$ s.t. $\min_j \{v_1, v_2\} \subseteq V_j = i, \forall i \in [k]$. We can see that the cliques on $V_i$'s form an edge clique cover of $K_n$.
Question: What is the number of equivalent node sets (i.e., edge clique covers) for a given $n$?
We consider the order of node sets and define the equivalence from the perspective of edge partitions. Let me show an example of equivalent node sets with $n = 3$. In our definition, the following two sequences of node sets are equivalent: $(\{1, 2\}, \{1, 3\}, \{2, 3\})$ and $(\{1, 2\}, \{1, 3\}, \{1, 2, 3\})$. This is because $\{1, 2\}$ covers the edge $(1, 2)$, $\{1, 3\}$ covers the edge $(1, 3)$, and after that, the only remaining edge to be covered is $(2, 3)$. Hence, both $\{2, 3\}$ and $\{1, 2, 3\}$ are equally effective after $\{1, 2\}$ and $\{1, 3\}$, and we see $(\{1, 2\}, \{1, 3\}, \{2, 3\})$ and $(\{1, 2\}, \{1, 3\}, \{1, 2, 3\})$ as equivalent node sets. Notably, we do not consider the order of how the edges are covered (see case 5 below).
I managed to enumerate all the possible cases for $n = 3$ as follows:
- $(\{1, 2, 3\})$
- $(\{1, 2\}, \{1, 2, 3\})$
- $(\{1, 3\}, \{1, 2, 3\})$
- $(\{2, 3\}, \{1, 2, 3\})$
- $(\{1, 2\}, \{1, 3\}, \{2, 3\})$ or $(\{1, 2\}, \{1, 3\}, \{1, 2, 3\})$ or $(\{1, 2\}, \{2, 3\}, \{1, 3\})$ or $(\{1, 2\}, \{2, 3\}, \{1, 2, 3\})$ or $(\{1, 3\}, \{1, 2\}, \{2, 3\})$ or $(\{1, 3\}, \{1, 2\}, \{1, 2, 3\})$ or $(\{1, 3\}, \{2, 3\}, \{1, 2\})$ or $(\{1, 3\}, \{2, 3\}, \{1, 2, 3\})$ or $(\{2, 3\}, \{1, 2\}, \{1, 3\})$ or $(\{2, 3\}, \{1, 2\}, \{1, 2, 3\})$ or $(\{2, 3\}, \{1, 3\}, \{1, 2\})$ or $(\{2, 3\}, \{1, 3\}, \{1, 2, 3\})$
How can we find all the possible cases for larger $n$? Even for $n = 4$, I can see the number of cases increases dramatically. I am expecting at least a recursive algorithm via, e.g., induction.