4
$\begingroup$

An edge cover of a graph $G = (V,E)$ is set $E' \subseteq E$ of edges such that for every vertex $v \in V$ there exists an edge $e \in E'$ such that $v \in e$.

Examples:

  1. E is trivially an edge cover.
  2. $\{\{1,2\},\{3,4\},\{1,5\}\}$ is an edge cover of $K_5$, the complete graph over 5 vertices.

Computing the total number of edge covers for any graph is #P-complete (from here).

I want to know the answer to a specialized version: What is the total number of edge covers of $K_n$, the complete graph on $n$ vertices?

$\endgroup$
4
$\begingroup$

This is a really hard problem for general graphs.

To give a sense, let's look at the behavior of $E(G)$, the number of edge coverings of $G$, on a couple of simple families of graphs.

First consider $A_n$, the connected graph on $n$ vertices in which one vertex has degree $n-1$ and all other vertices have degree $1$.
Of course we have $$E(A_n) = 1$$

Next consider the linear graphs $L_n$, which are the cyclic graphs $C_n$ with one edge removed.
For this family one can show via simple inductive argument that the number of edge coverings is $$E(L_n) = F_{n-1} \sim \frac{\varphi^{n-1}}{\sqrt{5}}$$ where $F_n$ is the $n$th Fibonacci number and $\varphi$ is the golden ratio. (Similarly $E(C_n)$ is the $n$th Lucas number.)

Lastly consider the complete graphs $K_n$, for which one can show that the number of edge coverings are $$E(K_n) = \sum\limits_{j=0}^{n}(-1)^j{n \choose j} 2^{n-j \choose 2} \sim 2^{\frac{n(n-1)}{2}}$$

Note $A_n$ and $L_n$ have the same number of vertices and edges but totally different numbers of edge coverings, showing that we need detailed information about at least the degree sequence of a graph. A degree $0$ (isolated) vertex forces $E(G) = 0$ immediately; a degree $1$ vertex contributes no freedom to the edge covering; but increasing a degree $1$ vertex to degree $2$ more or less doubles the number of edge covers, i.e. the problem is inherently exponential.

$E(K_n)$ gives an upperbound on $E(G)$ for $|G| = n$, if we are considering graphs in which the edge set is not allowed to be a multiset.

You might want to check out this paper: https://cs.uwaterloo.ca/journals/JIS/VOL11/Tauraso/tauraso18.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.