|
|
A374096
|
|
Number of edge covers of fan graph F_{1,n}.
|
|
1
|
|
|
1, 4, 16, 59, 214, 768, 2745, 9792, 34900, 124339, 442906, 1577540, 5618665, 20011452, 71272296, 253840779, 904068526, 3219889720, 11467810393, 40843217384, 145465283884, 518082304131, 1845177508818, 6571697181084, 23405446635913, 83359734391300, 296890096642144
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Fan Graph
|
|
FORMULA
|
a(n) = 4*a(n-1)-5*a(n-3)-2*a(n-4).
G.f.: x/((1 - x - x^2)*(1 - 3*x - 2*x^2)). - Stefano Spezia, Jun 29 2024
|
|
EXAMPLE
|
The fan graph F_{1,2} is the cycle with three vertices and has 4 edge covers.
The graph F_{1,3} is formed by adding a chord to the cycle with four vertices. The cycle C_4 has 7 edge covers, so there are 7 edge covers of F_{1,3} without the chord. If the chord is there, the two endpoints are covered. To cover the remaining two vertices, we need at least one of the two edges on each side of each vertex, giving us 3*3 choices total. So we have 16 edge covers for F_{1,3}.
We interpret F_{1,1} to be the path with two vertices with one edge cover.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|