A380461 Number of edge covers of fan graph F_{2,n}.

1, 16, 154, 1289, 10180, 78372, 596337, 4512900, 34064998, 256825009, 1935169456, 14577526976, 109797758833, 826945679592, 6227993359362, 46904386459065, 353244994467916, 2660340755025580, 20035394638446769, 150889230111278492, 1136366561949728110

Offset: 1

Author

Feryal Alayont, Jun 22 2025

Keywords

• nonn
• easy

Comments

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

Examples

			For n = 1, the fan graph F_{2,1} becomes a path with three vertices. There is exactly 1 edge cover.
For n = 2, the base graph P_2 has endpoints v and w, and two added vertices a and b each connect to both v and w. Each of a and b has 3 edge-covering options: use the edge to v, the edge to w, or both. This gives 3 × 3 = 9 combinations. For each, the edge (v,w) from P_2 may be included or not, giving 18 configurations. However, in 2 of these, omitting the edge (v,w) leaves v or w uncovered. Therefore, the number of valid edge covers is 18 - 2 = 16.
		

Links

• Eric Weisstein's World of Mathematics, Fan Graph
• Index entries for linear recurrences with constant coefficients, signature (11,-24,-21,33,34,8).

Formula

a(n) = 11*a(n-1) - 24*a(n-2) - 21*a(n-3) + 33*a(n-4) + 34*a(n-5) + 8*a(n-6), for n >= 7.