cp's OEIS Frontend

The fan graph F_{2,n} is the join of the path graph P_n with two isolated vertices. That is, two new vertices are added and each is connected to every vertex in P_n. a(n) is the number of edge covers of F_{2,n}.

Label vertices of F_{n,3} with v1, ..., v_n, a, b, c, with b adjacent to both a and c. An edge cover is a subset of the edges so that each vertex is the endpoint of at least one edge. Each of the n vertices has 7 ways to connect to vertices a, b, c. Once we connect all v_i's, we then have 4 options for the edges ab and bc to exist or not, giving 4*7^m options. But not all of these will be an edge cover. For example, if all v_i's connected to a and b only, we have to add edge bc in the second step. So 5*3^m are removed. But we removed 3 cases where all v_i's connected to only a, or only b, or only c too many times.

For n>1, a(n) is the number of edge covers of a caterpillar graph with spine P_(5n-4), one pendant attached at vertex n counting from the left end of the spine, a second one at 2n-1, a third at 3n-2 and a fourth at 4n-3. The caterpillar graph for n=3 is as follows:

* * * *

| | | |

*--*--*--v1--*--v2--*--v3--*--*--*

Each pendant edge must be included in an edge cover and hence allows the left and right sides of a vertex adjacent to a pendant to be independent. Therefore, the caterpillar can be split into independent paths, two P_4's (ends) and three P_5's (middle). Each P_n has F_{n-1} edge covers, resulting in the a(n) expression.

The sequence also counts number of subsets of {1, 2, ..., 5n-7} which do not contain two numbers whose difference is 5, a special instance of a general result given in Math. Mag. Problem 1854 (see Links). The equivalence to the above description can be seen as follows. Every vertex except v1, v2 and v3 is incident with at least one of the pendant edges. Therefore, if we label the middle eight edges in the spine with numbers 4, 1, 6, 2, 7, 3, 8, 5 (starting from the left), the edges have to be chosen so that both 1,6, both 2,7, and both 3,8 cannot be missing. This corresponds to choosing subsets of {1, 2, ..., 8} which do not contain two numbers whose difference is 5.

a(n) is the number of edge covers of a spider graph with five branches where each branch has n vertices besides the center vertex. The idea is each branch is treated as a path P_(n+2). Each branch acts independently then and has F_(n+1) covers (P_n has F(n-1) covers), hence F_(n+1)^5 total. Except we remove the cases where each branch is missing the connecting edge to the center, which is when that edge cover comes from P_n , hence the minus F_(n-1)^5.

An edge cover of a graph is a subset of edges for which each vertex is incident to at least one edge in the subset.

a(n) is the number of edge covers of a spider graph with four branches where each branch has n vertices besides the center vertex.

An edge cover of a graph is a subset of edges for which each vertex is incident to at least one edge in the subset.

The idea is each branch is treated as a path P_(n+2). Each branch acts independently then and has F(n+1) covers (P_n has F(n-1) covers), hence F(n+1)^4 total. Except we remove the cases where each branch is missing the connecting edge to the center, which is when that edge cover comes from P_n , hence the minus F(n-1)^4.