<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{enumitem}
\usepackage{subcaption}
\usepackage{tikz} 

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\DeclareMathOperator{\pc}{PC} 
\DeclareMathOperator{\cat}{Cat}


\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}

\begin{center}
\vskip 1cm{\LARGE\bf 
Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs \\ 
\vskip .1in
}
\vskip 1cm
\large
Feryal Alayont and Evan Henning\\
Department of Mathematics\\
Grand Valley State University \\
Allendale, MI 49401\\
USA\\
\href{mailto:alayontf@gvsu.edu}{\tt alayontf@gvsu.edu}
\href{mailto:henninge@mail.gvsu.edu}{\tt henninge@mail.gvsu.edu}
\end{center}

\vskip .2in


\begin{abstract}

An edge cover of a simple graph is a subset of the edges so that each vertex is incident with at least one edge in the subset. The edge cover polynomial of a graph is the generating polynomial of the number of edge covers of the graph with $k$ edges. The number of edge covers of path graphs form the Fibonacci sequence, while those of cycle graphs form the Lucas numbers. In this paper, we first provide some known and new general results on edge covers and edge cover polynomials. We then apply these results to find the number of edge covers and the edge cover polynomials of caterpillar graphs, cycles with pendants, and spider graphs, which are generalizations of star graphs. The number of edge covers of all these families can be expressed in terms of Fibonacci numbers. We generate new sequences not in the {\it On-Line Encyclopedia of Integer Sequences\/} using these edge covers and provide new combinatorial interpretations of some known sequences. 
\end{abstract}

\section{Introduction}

A \emph{(simple) graph} \(G\) is an ordered pair \((V, E)\) consisting of a finite set of vertices \(V(G) = \{v_{1},v_{2},\ldots,v_{n}\}\) and a finite set of edges \(E(G)=\{e_{1},e_{2},\ldots,e_{m}\}\), where each edge is a set of two distinct vertices. All the graphs we consider are simple, and we will refer to them as graphs for brevity. The \emph{degree} of a vertex is the number of edges that are \emph{incident} with that vertex, i.e., the number of edges that meet at that vertex. An \emph{isolated vertex} has degree 0, and a \emph{pendant} (vertex) has degree 1. An \emph{edge cover} of a graph \(G\) is a subset of \(E(G)\) such that each vertex of \(G\) is incident with at least one edge in this subset. In Figure~\ref{fig:example_edge_cover}, the edges \(e_{3},e_{5},e_{6},e_{7}\) (highlighted in red and dashed) form an edge cover. The remaining edges, \(e_{1},e_{2},e_{4},e_{8}\) also form an edge cover. No graph with at least one isolated vertex has an edge cover. In a graph with no isolated vertices, the set of all edges is an edge cover.

\begin{figure}[ht]
\centering
\begin{tikzpicture}[style = thick, scale = .4]
\foreach \x in {90,162,234,306,18}
\filldraw (\x:5cm) circle (6pt);
\draw (18:5cm)--(90:5cm)--(162:5cm);
\draw (234:5cm)--(306:5cm);
\draw (234:5cm)--(18:5cm);
\draw [red, dashed](162:5cm)--(234:5cm);
\draw [red, dashed](306:5cm)--(18:5cm);
\draw [red, dashed](90:5cm)--(306:5cm)--(162:5cm);
\draw (18:5cm) node[anchor=south west]{\(v_{1}\)};
\draw (90:5cm) node[anchor=south]{\(v_{2}\)};
\draw (162:5cm) node[anchor=south east]{\(v_{3}\)};
\draw (234:5cm) node[anchor=north east]{\(v_{4}\)};
\draw (306:5cm) node[anchor=north west]{\(v_{5}\)};

\draw (54:4cm) node[anchor=south west]{\small\(e_{1}\)};
\draw (126:4cm) node[anchor=south east]{\small\(e_{2}\)};
\draw (198:4cm) [red]node[anchor=north east]{\small\(e_{3}\)};
\draw (270:4cm) node[anchor=north]{\small\(e_{4}\)};
\draw (342:4cm) [red]node[anchor=north west]{\small\(e_{5}\)};
\draw (80:3cm) [red]node[anchor=east]{\(e_{6}\)};
\draw (165:4cm) [red]node[anchor=west]{\(e_{7}\)};
\draw (-.3,-.1) node[anchor=north west, outer ysep=-6pt, outer xsep=-1pt]{\(e_{8}\)};
\end{tikzpicture}
\caption{A graph and two edge covers (red edges and black edges).}
\label{fig:example_edge_cover}
\end{figure}
    
Although research on edge covers often considers minimum edge covers in optimization applications, in this paper, we focus on counting the edge covers. This problem has applications in counting elements at a given location between two given elements in Hausdorff metric geometry \cite{blackburn2009missing}. Honigs \cite{honigs2013missing} showed that the number of edge covers of a bipartite graph representing adjacencies in a finite configuration \([A, B]\) (i.e., two finite sets \(A, B\) in Hausdorff metric geometry with specific Hausdorff metric conditions) is equal to the number of elements at each location between \(A\) and \(B\). Counting edge covers can also be used to estimate the importance of a line in communication networks \cite{ita2010estimating}.

Let \(\#G\) denote the total number of edge covers of \(G\). It can be shown \cite{honigs2013missing} by induction that for path graphs \(P_n\) with \(n\) vertices, \(\# P_n = F_{n-1} \), where \(F_n\) are the Fibonacci numbers with initial values \(F_0=0, F_1=1\), which is the sequence \seqnum{A000045}. By considering cases based on whether there is a fixed edge or not \cite{honigs2013missing}, one can also show that for cycle graphs \(C_n\) with \(n\) vertices \(\#C_n = L_n\) for \(n\geq 3\), where \(L_n\) are the Lucas numbers with initial values \(L_0=2, L_1=1\). The edge cover polynomial, \(E(G,x)\), of a graph \(G\) is defined as 
\[E(G,x)= \sum_{k=1}^{|E(G)|} e(G,k) x^k\, ,\]
where \(e(G,k)\) is the number of edge covers of \(G\) with \(k\) edges. For example, \(P_6\) has one edge cover with five edges, three with four edges, and one with three edges, as shown in Figure~\ref{fig:P_6covers}. Hence, the edge cover polynomial of \(P_6\) is 
\[ E(P_6, x) = x^3 + 3x^4 + x^5 \, .\]
More generally, we have \cite{akbari2013edge}
\[E(P_n,x)=\sum_{i=1}^{n-1} \binom{i-1}{n-i-1} x^i \,.\]
The coefficients of the edge cover polynomials (arranged in descending powers of \(x\)) of path graphs form the entry \seqnum{A011973} in the 
{\it On-Line Encyclopedia of Integer Sequences\/} (OEIS) \cite{oeis}.
\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=1.2]
\foreach \x in {0,1.5,3,4.5,6,7.5}
\filldraw (\x,0) circle (2pt);
\foreach \x in {0,1.5,3,4.5,6,7.5}
\filldraw (\x,-.4) circle (2pt);
\foreach \x in {0,1.5,3,4.5,6,7.5}
\filldraw (\x,-.8) circle (2pt);
\foreach \x in {0,1.5,3,4.5,6,7.5}
\filldraw (\x,-1.2) circle (2pt);
\foreach \x in {0,1.5,3,4.5,6,7.5}
\filldraw (\x,-1.6) circle (2pt);

\draw (0,0)--(1.5,0)--(3,0)--(4.5,0)--(6,0)--(7.5,0);
\draw (0,-.4)--(1.5,-.4)--(3,-.4)(4.5,-.4)--(6,-.4)--(7.5,-.4);
\draw (0,-.8)--(1.5,-.8)(3,-.8)--(4.5,-.8)--(6,-0.8)--(7.5,-.8);
\draw (0,-1.2)--(1.5,-1.2)--(3,-1.2)--(4.5,-1.2)(6,-1.2)--(7.5,-1.2);
\draw (0,-1.6)--(1.5,-1.6)(3,-1.6)--(4.5,-1.6)(6,-1.6)--(7.5,-1.6);
\end{tikzpicture}
\caption{Edge covers of \(P_6\).}
\label{fig:P_6covers}
\end{figure}

This paper focuses on edge covers of path and cycle graphs with pendants and spider graphs. A \emph{spider graph} is a tree (i.e., a connected graph with no cycles) with one vertex of degree greater than or equal to 3 and the rest of degree less than or equal to 2. We calculate the number of edge covers of these graph families and present formulas for their edge cover polynomials. We obtain new sequences not found in the OEIS \cite{oeis} and provide new combinatorial interpretations of some known sequences.

\section{Some general properties of edge covers}

Some known results about the total number of edge covers and edge cover polynomials are 
\begin{theorem} \label{thm:general}
\leavevmode
\begin{enumerate}[label=(\roman*)]
\item Given a graph \(G\) with connected components \(G_1, G_2, \ldots, G_k\), we have \cite{akbari2013edge}
\[ \#G = \prod_{i=1}^k\#G_i \; \text{ and } \; E(G, x) = \prod_{i=1}^k E(G_i, x) \,.\] 
\item Given a graph \(G\) with edge \(uv\), we have 
\[ E(G, x) = (x+1) E(G-uv, x) + x\bigl( E(G-u, x) + E(G-v, x) + E(G-\{u,v\} , x) \bigr), \]
where \(G - uv\) represents the graph with edge \(uv\) removed, and \(G-u, G-v\), and \(G-\{u,v\}\) represent the graphs with the vertex \(u\); vertex \(v\); and both \(u,v\) removed, respectively \cite{akbari2013edge, honigs2013missing}.
\item Given a graph \(G\) with a pendant vertex \(v\) whose neighbor is \(u\), we have \cite{akbari2013edge}
\[ E(G, x) = x E(G-v, x) + xE(G-\{u,v\} , x )\,.\]
\item \label{thm:generaljoin} Suppose \(G = G_1\cdot uv\cdot G_2\) is formed by combining two graphs \(G_1\) and \(G_2\) by identifying the vertex \(u \in G_1\) with the vertex \(v\in G_2\). Then \cite{csikvari2011roots} 
\[E(G, x) = E(G_1, x) E(G_2,x)+ E(G_1-u, x)E(G_2,x)+E(G_1,x)E(G_2-v,x)\, .\]
\end{enumerate}
\end{theorem}

We now prove two new results, the first of which is about 2-sums of graphs, a particular case of \(k\)-sums \cite{belkconnelly2007realizability}. Given two graphs, \(G_1\) and \(G_2\), and an edge from each graph, the \emph{2-sum} \(G_1 \oplus_2 G_2\) is obtained by identifying the two edges. The 2-sum depends on which edges in the graphs are chosen and how they are identified. An example of the 2-sum of two graphs is shown in Figure~\ref{fig:2-sum}.
\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=1.2]
\filldraw (0,0) circle (2pt) (1.5,0) circle (2pt) (3,0) circle (2pt) (3,1.5) circle (2pt) (1.5,1.5) circle (2pt) (0,1.5) circle (2pt) (-1,0.75) circle (2pt);
\draw (0,0)--(0,1.5)--(-1,0.75)--cycle;
\draw (1.5,0)--(1.5,1.5)--(3,1.5)--(3,0)--(1.5,0)--(3,1.5);
\node at (0,1.9) {$u$};
\node at (1.5,1.9) {$u$};
\node at (0,-0.5) {$v$};
\node at (1.5,-0.5) {$v$};
\node at (-0.5,2.3) {$G_1$};
\node at (2.25,2.3) {$G_2$}; 
\node at (5,0.75) {$\longrightarrow$\qquad \text{ }};
\end{tikzpicture}
\begin{tikzpicture}[scale=1.2]
\filldraw (3,0) circle (2pt) (3,1.5) circle (2pt) (1.5,1.5) circle (2pt) (1.5,0) circle (2pt) (0.5,0.75) circle (2pt);
\draw (1.5,0)--(1.5,1.5)--(3,1.5)--(3,0)--(1.5,0)--(3,1.5);
\draw (1.5,0)--(0.5,0.75)--(1.5,1.5);
\node at (1.5,1.9) {$u$};
\node at (1.5,-0.5) {$v$};
\node at (2.2,2.4) {$G_1 \oplus_2 G_2$};
\end{tikzpicture}
\caption{The 2-sum of two graphs.}
\label{fig:2-sum}
\end{figure}

\begin{lemma}[2-sum Lemma] \label{lem:2-sum} Let \(G=G_1 \oplus_2 G_2\) with the common identified edge labeled \(uv\) in \(G\) and \(G_{i}\). Then the set of edge covers of \(G\) that include the edge \(uv\) is in bijection with the cross product of the sets of edge covers of \(G_1'=(G_1 \cup \{uw_1, vw_2\}) - uv\) and \(G_2'=(G_{2} \cup \{uy_1, vy_2\}) - uv\), where \(w_1,w_2\) (respectively \(y_1,y_2\)) are pendant vertices added to \(G_1\) (respectively \(G_2\)).
\end{lemma}

\begin{proof} To clarify the definitions, Figure~\ref{fig:2-sum_lemma} shows how \(G_1'\) and \(G_2'\) would look like using the example of \(G=G_1 \oplus_2 G_2\) shown in Figure~\ref{fig:2-sum}.

\begin{figure}[htb]
\centering
\begin{tikzpicture}[scale=1.2]
\filldraw (3,0) circle (2pt) (3,1.5) circle (2pt) (1.5,1.5) circle (2pt) (1.5,0) circle (2pt) (0.5,0.75) circle (2pt);
\draw (1.5,0)--(1.5,1.5)--(3,1.5)--(3,0)--(1.5,0)--(3,1.5);
\draw (1.5,0)--(0.5,0.75)--(1.5,1.5);
\node at (1.5,1.9) {$u$};
\node at (1.5,-0.5) {$v$};
\node at (2.2,2.4) {$G_1 \oplus_2 G_2$};
\node at (5,0.75) {$\longrightarrow$\qquad \text{ }};
\end{tikzpicture}
\begin{tikzpicture}[scale=1.2]
\filldraw (0,0) circle (2pt) (1.5,0) circle (2pt) (3,0) circle (2pt) (3,1.5) circle (2pt) (1.5,1.5) circle (2pt) (0,1.5) circle (2pt) (-1,0.75) circle (2pt);
\filldraw (-0.5,1.9) circle (2pt) (-0.5,-0.4) circle (2pt) (2,1.9) circle (2pt) (2,-0.4) circle (2pt);
\draw (-0.5,1.9)--(0,1.5)--(-1,0.75)--(0,0);
\draw (2,1.9)--(1.5,1.5)--(3,1.5)--(3,0)--(1.5,0)--(3,1.5);
\draw (0,0)--(-0.5,-0.4);
\draw (1.5,0)--(2,-0.4);
\node at (-0.8, 1.8) {$w_1$};
\node at (0.3, 1.5) {$u$};
\node at (1.2, 1.5) {$u$};
\node at (0.3, 0) {$v$};
\node at (1.2, 0) {$v$};
\node at (-0.5,-1) {$w_2$};
\node at (2,-1) {$y_2$};
\node at (2.4,1.8) {$y_1$};
\node at (-0.5,2.5) {$G_1'$};
\node at (2.25,2.5) {$G_2'$}; 
\end{tikzpicture}
\caption{An example of constructing \(G_1'\) and \(G_2'\) from \(G=G_1 \oplus_2 G_2\).}
\label{fig:2-sum_lemma}
\end{figure}


To prove the lemma, we define a map \(S \rightarrow (S_{1},S_{2})\) where \(S\) is an edge cover of \(G\) that includes \(uv\), and \(S_i\) is an edge cover of \(G_i^\prime\) for \(i=1,2\), and show that the map is a bijection. Let \(S\) be an edge cover of \(G\) that includes \(uv\). Because the edges of \(G\) besides \(uv\) belong either to \(G_1\) or \(G_2\) (but not both), we can label the elements of \(S\) as
\[S = \{uv, e_{1},\ldots,e_{r},e_{r+1},\ldots,e_{s}\},\] 
where \(e_{1},\ldots,e_{r} \in G_{1}\) and \(e_{r+1},\ldots,e_{s} \in G_{2}\). Let \(S_{1} = \{uw_{1},vw_{2},e_{1},\ldots,e_{r}\}\) and \(S_{2} = \{uy_{1},vy_{2},e_{r+1},\ldots,e_{s}\}\). We will show that each \(S_i\) is an edge cover of \(G_i'\).

If \(x \in G_i\) and \(x\neq u, v, w_1, w_2, y_1, y_2\), then \(x\) is also in \(G\) and \(S\) has an edge that is incident with \(x\), which is also in the respective \(S_i\). The pendant vertices \(w_1, w_2, y_1\), and \(y_2\), and vertices \(u,v\) are endpoints of the newly added edges \(uw_{1},vw_{2}, uy_{1}\), and \(vy_{2}\). Therefore, \(S_i\) is an edge cover of \(G_i\).

The map \(S \rightarrow (S_{1},S_{2})\) is one-to-one because if two edge covers agree on the edges restricted to \(G_1'\) and \(G_2'\), they must agree on all but \(uv\). However, the map is defined only on edge covers containing \(uv\). Therefore, the edge covers must agree on all of \(G\).

The map is also onto. Let \(S_{1}\) and \(S_{2}\) be edge covers of \(G_{1}^\prime\) and \(G_{2}^\prime\), respectively. Because \(uw_{1}\) and \(uw_{2}\) are both pendant edges in \(G_{1}^\prime\), we know they will be in \(S_{1}\). The remaining edges in \(S_{1}\) are edges that are in \(G_{1}\). Therefore, we can write \(S_{1} = \{uw_{1},vw_{2},e_{1},\ldots,e_{r}\}\) for some \(e_{i}\) in \(G_{1}\). Similarly, \(S_{2} = \{uy_{1},vy_{2},e_{r+1},\ldots,e_{s}\}\) for some \(e_{i}\) in \(G_{2}\). Define 
\[S = S_{1} \cup S_{2} \cup \{uv\} - \{uw_{1},vw_{2},uy_{1},vy_{2}\}= \{uv, e_{1},\ldots,e_{r},e_{r+1},\ldots,e_{s}\}\,.\]
It is easy to show that \(S\) is an edge cover of \(G\) and maps to \((S_{1},S_{2})\). 

Since the map is one-to-one and onto, it is a bijection, as claimed.
\end{proof}


A direct consequence of the 2-sum lemma is
\begin{corollary} Let \(\#(G;uv)\) denote the number of edge covers of \(G\) that include the edge \(uv\). Suppose \(G=G_1 \oplus_2 G_2\), the common identified edge is labeled \(uv\) in \(G\), and \(G_{i}\) and \(G_i'\) are defined as in the 2-sum lemma. Then 
\[\#(G;uv) = \#G_{1}^\prime \cdot \#G_{2}^\prime \,.\]
\end{corollary}

The 2-sum lemma implies another direct result regarding the edge cover polynomials. Let \(E(G;uv, x)\) be the edge cover polynomial of the edge covers of \(G\) that include the edge \(uv\). By the 2-sum lemma, since every edge cover of \(G\) that includes \(uv\) corresponds to an edge cover of the graph with components \(G_1'\) and \(G_2'\), the numbers of the edge covers will be the same. However, when defining the correspondence of edge covers, the edge \(uv\) turns into four edges: \(uw_{1},vw_{2}, uy_{1},\) and \(vy_{2}\). Therefore, in the polynomial, we have an extra \(x^3\) factor on the \(G_i'\) side. Thus, we have the following edge cover polynomial result:
\begin{corollary} \label{cor:2sum_poly} Suppose \(G=G_1 \oplus_2 G_2\), the common identified edge is labeled \(uv\) in \(G\), and \(G_{i}\) and \(G_i'\) are defined as in the 2-sum lemma. Then 
\[E(G;uv,x) = \frac{E(G_{1}^\prime) \cdot E(G_{2}^\prime)}{x^{3}}\,. \]
\end{corollary}

Another similar result, the pendant lemma, applies to graphs with a pendant vertex. 

\begin{lemma}[Pendant Lemma] \label{lem:pendant} Let \(G\) be a graph with a pendant vertex \(v\). Let \(u\) be the neighbor of \(v\), and \(w_i\), \(1\leq i\leq k\), be the neighbors of \(u\) besides \(v\). Then the set of edge covers of \(G\) is in bijection with the set of edge covers of 
\[G'=(G-\{u,v\}) \cup \{w_1u_1, u_1v_1, w_2u_2, u_2v_2, \ldots, w_ku_k, u_kv_k\},\] 
where the \(u_i,v_i\) are added new vertices to \(G\).
\end{lemma}

\begin{proof}
A representative example of the \(G\) and \(G'\) pair is shown in Figure~\ref{fig:pendant}.
\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=1]
\filldraw (0,0) circle (2pt) (2,0) circle (2pt) (2,1) circle (2pt) (0,1) circle (2pt) (1,0.8) circle (2pt)
(1,1.8) circle (2pt) (1,2.8) circle (2pt) (0,2.5) circle (2pt);
\draw (0,0)--(0,1)--(1,1.8)--(2,1)--(2,0)--(0,0)--(1,0.8)--(1,2.8);
\draw (1,1.8)--(0,2.5);
\draw (1,0.8)--(2,0);
\node at (1.5,2.8) {$v$};
\node at (1.5,1.8) {$u$};
\node at (-0.5,1) {$w_2$};
\node at (1,0.4) {$w_3$};
\node at (2.5,1) {$w_4$};
\node at (-0.5,2.5) {$w_1$};
\node at (-1.5,0.2) {$G$}; 
\end{tikzpicture}
\qquad $\to$ \qquad
\begin{tikzpicture}[scale=1]
\filldraw (0,0) circle (2pt) (2,0) circle (2pt) (2,1) circle (2pt) (2,2) circle (2pt) (2,3) circle (2pt) (0,1) circle (2pt) (0,2) circle (2pt) (0,3) circle (2pt) (1,0.8) circle (2pt) (1,1.8) circle (2pt) (1,2.8) circle (2pt) (-1,1) circle (2pt) (-1,2) circle (2pt) (-1,3) circle (2pt);
\draw (2,3)--(2,0)--(0,0)--(0,1)--(0,3);
\draw (-1,1)--(-1,3);
\draw (0,0)--(1,0.8)--(1,2.8);
\draw (1,0.8)--(2,0);
\node at (1.5,2.8) {$v_3$};
\node at (1.5,1.8) {$u_3$};
\node at (-1.5,1) {$w_1$};
\node at (-0.5,1) {$w_2$};
\node at (1,0.4) {$w_3$};
\node at (2.5,1) {$w_4$};
\node at (-0.5,3) {$v_2$};
\node at (-0.5,2) {$u_2$};
\node at (-1.5,3) {$v_1$};
\node at (-1.5,2) {$u_1$};
\node at (2.5,3) {$v_4$};
\node at (2.5,2) {$u_4$};
\node at (-2.5,0.2) {$G'$};
\end{tikzpicture}
\caption{An example of \(G'\) construction.}
\label{fig:pendant}
\end{figure}

The graph \(G'\) is obtained by replacing the vertices \(u,v\) with multiple copies, one for each edge incident with \(u\) besides \(uv\). Every pendant edge must be included in every edge cover of \(G\). Therefore, the vertices \(u\) and \(v\) are already covered, allowing the remaining edges incident with \(u\) to be flexible. Hence, we can represent the pendant instead as an added edge to each edge incident with \(u\). More precisely, an edge cover \(\{e_1, e_2, \ldots, e_r, uv\}\) of \(G\) corresponds to the edge cover \(\{e_1, e_2, \ldots, e_r, u_1v_1, u_2v_2, \ldots, u_kv_k\}\) of \(G'\). In this correspondence, by abuse of notation, for an edge \(e_i=w_ju\)  that might be in the edge cover of \(G\), we still use \(e_i\) to represent the corresponding edge \(w_ju_j\) in \(G'\).
\end{proof}

\begin{corollary} \label{cor:pendant_poly} Let \(G\) be a graph with pendant \(v\), whose neighbor is \(u\). Suppose \(\deg u = k\). Let \(G'\) be as in the pendant lemma. Then \(\#G=\#G'\) and
\[E(G,x) = \frac{1}{x^{k-2}}E(G',x)\,. \]
\end{corollary}

\begin{proof}
The first claim directly follows from the pendant lemma. In the correspondence between edge covers of \(G\) and \(G'\), we replace all of the \(k\) edges incident with \(u\) with  \(k-1\) non-pendant and \(k-1\) pendant edges. Hence, the edge cover polynomial of \(G'\) has an extra \(x^{k-2}\) factor.
\end{proof}


\section{Paths and cycles with pendants}
The two lemmas from the previous section can be applied to path and cycle graphs with one or more pendants to express their edge cover numbers in terms of Fibonacci numbers. By repeatedly splitting the graph at the pendant edge using the pendant lemma, each path or cycle graph with pendants becomes a union of disconnected path graphs.

\subsection{Caterpillars}
A \emph{caterpillar graph} is a tree in which every vertex is either on the longest path or exactly one graph edge away from this path. We will refer to this longest path as the \emph{central stalk} of the caterpillar.

\begin{theorem}\label{thm:caterpillar} A caterpillar graph \(G\) with central stalk \(P_n\) and \(k_1, k_2, \ldots, k_r\) pendants at inner vertices (counting from one pendant vertex of \(P_n\)) located at vertices \(m_1, m_2, \ldots, m_r\), respectively, has a total of 
\[ \#G = F_{m_1} F_{m_2-m_1+2} \cdots F_{m_r-m_{r-1}+2} F_{n-m_r+1}\]
edge covers. Its edge cover polynomial is 
\[ E(G,x) = x^{k_1+k_2+\cdots+k_r - 2r} E(P_{m_1+1},x) E(P_{n-m_r+2},x) \prod_{i=2}^r E(P_{m_i-m_{i-1}+3},x)\, .\]
\end{theorem}

\begin{proof}
Let \(G\) be a caterpillar graph with a central stalk \(P_n\) and additional pendants attached to vertices (counting from one end) \(m_1, m_2, \ldots, m_r\). Without loss of generality, we can assume that exactly one pendant is attached to each spot since an edge cover includes all pendants. Additional pendants only change the edge cover polynomial by a factor of \(x^{k_1+k_2+\cdots+k_r-r}\).

The proof proceeds by induction on the number of added pendants. We demonstrate the idea using the example caterpillar graph shown in Figure~\ref{fig:caterpillar}.
\begin{figure}[H]
\centering
\begin{tikzpicture}
\foreach \i in {0, 1, ..., 10}
\filldraw (\i,0) circle (2pt);
\filldraw (2,1) circle (2pt) (5,1) circle (2pt) (9,1) circle (2pt);
\draw (0,0)--(10,0);
\draw (2,0)--(2,1);
\draw (5,0)--(5,1);
\draw (9,0)--(9,1);
\node at (0,-0.5) {1};
\node at (2,-0.5) {$m_1$};
\node at (5,-0.5) {$m_2$};
\node at (9,-0.5) {$m_3$};
\node at (10,-0.5) {$n$};
\end{tikzpicture}
\caption{A caterpillar graph with three pendants attached to the central stalk.}
\label{fig:caterpillar}
\end{figure}
By applying the pendant lemma at vertex \(m_1\), we obtain a disjoint union of \(P_{m_1+1}\)  and a caterpillar with one fewer pendant. In this specific example, after applying the pendant lemma at \(m_1=3\), we obtain the path \(P_4\) and a caterpillar with two added pendants attached at \(m_2-m_1+2=5\) and \(m_3-m_1+2=9\) on a central stalk \(P_{n-m_1+2}=P_{10}\). This new disconnected graph is shown in Figure~\ref{fig:split_caterpillar}.
\begin{figure}[H]
\centering
\begin{tikzpicture}
\foreach \i in {2,3, ..., 10}
\filldraw (\i,0) circle (2pt);
\filldraw (2,1) circle (2pt) (5,1) circle (2pt) (9,1) circle (2pt);
\filldraw (-0.5,0) circle (2pt);
\filldraw (0.5,0) circle (2pt);
\filldraw (1.5,1) circle (2pt);
\filldraw (1.5,0) circle (2pt);
\draw (-0.5,0)--(1.5,0)--(1.5,1);
\draw (2,0)--(10,0);
\draw (2,0)--(2,1);
\draw (5,0)--(5,1);
\draw (9,0)--(9,1);
\node at (-0.5,-0.5) {1};
\node at (1.5,-0.5) {$m_1$};
\node at (5,-0.5) {$m_2-m_1+2$};
\node at (9,-0.5) {$m_3-m_1+2$};
\node at (10.2,0.3) {$n-m_1+2$};
\end{tikzpicture}
\caption{Caterpillar in Figure~\ref{fig:caterpillar} with one pendant section separated.}
\label{fig:split_caterpillar}
\end{figure}
Therefore, by induction on the number of pendants attached, the number of edge covers is the product of $F_{m_1}$ and \(F_{m_2-m_1+2} \cdot F_{m_3-m_2+2} \cdot F_{n-m_3+1}\). Therefore, the first claim for the total number of edge covers follows.

Regarding the edge cover polynomials, each time we split off a path graph, we need to multiply by \(1/x\) due to Corollary \ref{cor:pendant_poly} since the degree of the pendant vertex is three. Thus, for \(r\) pendants, we have an extra \(x^{-r}\) factor.
\end{proof}

We can generate number sequences out of caterpillars by considering evenly spaced pendants in caterpillars \cite{napier2018cross}. For simplicity, at every vertex of the caterpillar, assume there is at most one pendant. Let \(\cat_{k,n}\) denote a caterpillar with \(n\) pendants where \(k-1\) is the number of edges between consecutive pendants, and before the first and after the last pendants. Using the results above, we have
\[\# \cat_{k,n} = F_k^2 F_{k+1}^{n-1} \,. \]
Fixing \(k\) or \(n\) generates a sequence of numbers. For example, \(k=3\) generates the sequence \seqnum{A003946}, while \(n=2\) generates \seqnum{A066258} in OEIS \cite{oeis}.

\subsection{Cycle graphs with pendants}

When pendants are attached to cycle graphs, we can similarly use the pendant lemma at each pendant to split the graph into paths. 

\begin{theorem} \label{thm:cycle_w_pendant}
Suppose \(G\) is obtained by attaching pendants to a cycle graph \(C_n\) with vertices consecutively labeled \(1, 2, \ldots, n\) and \(k_0, k_1, k_2, \ldots, k_r\) pendants attached to vertices (counting clockwise starting at \(1\)) \(1, m_1, m_2, \ldots, m_r\), respectively. Then \(G\) has a total of 
\[ \#G = F_{m_1+1} F_{m_2-m_1+2} \cdots F_{m_r-m_{r-1}+2} F_{n-m_r+3}\]
edge covers. Its edge cover polynomial is 
\[ E(G,x) = x^{k_0+k_1+k_2+\cdots+k_r - 2(r+1)}  E(P_{m_1+2},x) E(P_{n-m_r+4},x) \prod_{i=2}^r E(P_{m_i-m_{i-1}+3},x)\, .\]
\end{theorem}

\begin{proof}
A representative example labeled cycle with pendants is shown in Figure~\ref{fig:cycle_pendant}.
\begin{figure}[H]
\centering
\begin{tikzpicture}[style = thick, scale=0.88]
    \foreach \x in {90,135,180,225,270,315,0,45}
    \filldraw (\x:2cm) circle (2pt);
    \foreach \x in {85,95,225,235, 215,315}
    \filldraw (\x:3.5cm) circle (2pt);
\draw (90:2cm)--(135:2cm)--(180:2cm)--(225:2cm)--(270:2cm)--(315:2cm)--(0:2cm)--(45:2cm)--cycle;
\draw(90:2cm)--(95:3.5cm)(90:2cm)--(85:3.5cm)(225:2cm)--(225:3.5cm)(225:2cm)--(235:3.5cm) (225:2cm)--(215:3.5cm)(315:2cm)--(315:3.5cm);
\node at (90:1.5cm) {1};
\node at (135:2.5cm) {8};
\node at (45:2.5cm) {2};
\node at (0:2.5cm) {3};
\node at (270:2.5cm) {5};
\node at (180:2.5cm) {7};
\node at (330:2.7cm) {$m_1=4$};
\node at (235:1.2cm) {$m_2=6$};
\end{tikzpicture}
\caption{A cycle with $k_0=2$ pendants at vertex 1, $k_1=1$ pendant at $m_1=4$, and $k_2=3$ pendants at $m_2=6$.}
\label{fig:cycle_pendant}
\end{figure}

Let \(G\) be a cycle with $n$ vertices with $k_0$ pendants attached to vertex 1, $k_1$ attached to $m_1$, \ldots, and $k_r$ attached to $m_r$. As before, without loss of generality, assume there is one pendant at each pendant location. We first apply the pendant lemma at vertex 1 to turn the cycle \(C_n\) with pendants at locations \(1, m_1, m_2, \ldots, m_r\) into a path \(P_{n+3}\) with pendants at locations \(m_1+1, m_2+1, \ldots, m_r+1\). The example graph given in Figure~\ref{fig:cycle_pendant} will turn into the caterpillar in Figure~\ref{fig:cycle_pendant_to_caterpillar} if we first remove the extra pendants at each vertex and apply the pendant lemma. The two pendants in the figure without labels are the added pendants after using the lemma.
\begin{figure}[H]
\centering
\begin{tikzpicture}
\foreach \i in {0, 1, ..., 10}
\filldraw (\i*1.4-1.4,0) circle (2pt);
\filldraw (4.2,1) circle (2pt) (7,1) circle (2pt);
\draw (-1.4,0)--(12.6,0);
\draw (4.2,0)--(4.2,1);
\draw (7,0)--(7,1);
\node at (0,-0.5) {1};
\node at (1.4,-0.5) {2};
\node at (2.8,-0.5) {3};
\node at (4.2,-0.5) {\small{$m_1=4$}};
\node at (5.6,-0.5) {5};
\node at (7,-0.5) {\small{$m_2=6$}};
\node at (8.4,-0.5) {7};
\node at (9.8,-0.5) {8};
\node at (11.2,-0.5) {$1'$};
\end{tikzpicture}
\caption{The caterpillar obtained after applying the pendant lemma.}
\label{fig:cycle_pendant_to_caterpillar}
\end{figure}

Once the graph becomes a caterpillar, we apply Theorem \ref{thm:caterpillar} on caterpillars to obtain the result.
\end{proof}

\subsubsection{Evenly spaced pendants in cycle graphs}

We now consider evenly spaced single pendants on cycles to generate sequences. We denote a cycle with evenly spaced single pendants as \(\pc_{k,n}\), where \(k\) is the number of edges between consecutive pendants and \(n\) is the number of pendants on the graph. As a result, \(\pc_{k,n}\) has \(kn\) vertices on the cycle. After applying the Theorem~\ref{thm:cycle_w_pendant} in this case, we obtain the following theorem.

\begin{theorem} \label{thm:pckn} 
Given a cycle \(\pc_{k,n}\) with evenly spaced pendants, we have
\[\#\pc_{k,n} = (F_{k+2})^{n} \text{ and } \, E(\pc_{k,n},x) = \frac{E(P_{k+3},x)^{n}}{x^{n}} \, .\]
\end{theorem}

To generate sequences, we first fix \(k\), the spacing between the consecutive pendants, and change \(n\). First, let \(k=1\). The graphs \(\pc_{1,n}\) are cycles with a pendant on each vertex. These turn out to be rather uninteresting. By Theorem \ref{thm:pckn}, we have \(\#\pc_{1,n} = 2^n\) and \(E(\pc_{1,n},x) = \frac{(x^3+x^2)^{n}}{x^n} = x^n(x+1)^n\). The triangle formed of coefficients (arranged in descending powers of \(x\)) results in Pascal's triangle.

For \(k=2\), the graphs \(\pc_{2,n}\) are cycles with pendants on every other vertex. The first few examples of these graphs are shown in Figure~\ref{fig:PC_2,n}.
\begin{figure}[H]
\centering
\begin{tikzpicture}[style = thick, scale=0.5]
    \foreach \x in {90,180,270,0}
    \filldraw (\x:2cm) circle (2pt);
    \foreach \x in {90,270}
    \filldraw (\x:3.5cm) circle (2pt);
\draw (90:2cm)--(180:2cm)--(270:2cm)--(0:2cm)--cycle;
\draw(90:2cm)--(90:3.5cm)(270:2cm)--(270:3.5cm);
\end{tikzpicture}\hspace{1.5cm}
\begin{tikzpicture}[style = thick, scale=0.5]
    \foreach \x in {60,120,180,240,300,360}
    \filldraw (\x:2cm) circle (2pt);
    \foreach \x in {60,180,300}
    \filldraw (\x:3.5cm) circle (2pt);
\draw (60:2cm)--(120:2cm)--(180:2cm)--(240:2cm)--(300:2cm)--(360:2cm)--cycle;
\draw(60:2cm)--(60:3.5cm)(180:2cm)--(180:3.5cm)(300:2cm)--(300:3.5cm);
\end{tikzpicture}\hspace{1.5cm}
\begin{tikzpicture}[style = thick, scale=0.5]
    \foreach \x in {90,135,180,225,270,315,0,45}
    \filldraw (\x:2cm) circle (2pt);
    \foreach \x in {90,180,270,0}
    \filldraw (\x:3.5cm) circle (2pt);
\draw (90:2cm)--(135:2cm)--(180:2cm)--(225:2cm)--(270:2cm)--(315:2cm)--(0:2cm)--(45:2cm)--cycle;
\draw(90:2cm)--(90:3.5cm)(180:2cm)--(180:3.5cm)(270:2cm)--(270:3.5cm)(0:2cm)--(0:3.5cm);
\end{tikzpicture}
\caption{From left to right, \(\pc_{2,2}, \pc_{2,3}\), and \(\pc_{2,4}\).}
\label{fig:PC_2,n}
\end{figure}
By Theorem \ref{thm:pckn}, we have \(\#\pc_{2,n} = 3^n\) and \(E(\pc_{2,n},x) = \frac{(x^4+2x^3)^{n}}{x^n} = x^{2n}(x+2)^n\). The coefficients of the polynomials (arranged in descending powers of \(x\)) form the sequence \seqnum{A013609}, described as the sequence of coefficients of \((1+2x)^n\).

When \(k=3\), the first few graphs are shown in Figure~\ref{fig:PC_3,n}.
\begin{figure}[H]
\centering
\begin{tikzpicture}[style = thick, scale=0.5]
    \foreach \x in {90,210,330}
    \filldraw (\x:2cm) circle (2pt);
    \foreach \x in {90}
    \filldraw (\x:3.5cm) circle (2pt);
\draw (90:2cm)--(210:2cm)--(330:2cm)--cycle;
\draw(90:2cm)--(90:3.5cm);
\end{tikzpicture}\hspace{1.5cm}
\begin{tikzpicture}[style = thick, scale=0.5]
    \foreach \x in {60,120,180,240,300,360}
    \filldraw (\x:2cm) circle (2pt);
    \foreach \x in {120,300}
    \filldraw (\x:3.5cm) circle (2pt);
\draw (60:2cm)--(120:2cm)--(180:2cm)--(240:2cm)--(300:2cm)--(360:2cm)--cycle;
\draw(120:2cm)--(120:3.5cm)(300:2cm)--(300:3.5cm);
\end{tikzpicture}\hspace{1.5cm}
\begin{tikzpicture}[style = thick, scale=0.5]
    \foreach \x in {90,130,170,210,250,290,330,10,50}
    \filldraw (\x:2cm) circle (2pt);
    \foreach \x in {90,210,330}
    \filldraw (\x:3.5cm) circle (2pt);
\draw (90:2cm)--(130:2cm)--(170:2cm)--(210:2cm)--(250:2cm)--(290:2cm)--(330:2cm)--(10:2cm)--(50:2cm)--cycle;
\draw(90:2cm)--(90:3.5cm)((210:2cm)--(210:3.5cm)(330:2cm)--(330:3.5cm);
\end{tikzpicture}
\caption{From left to right, \(\pc_{3,1}, \pc_{3,2}\), and \(\pc_{3,3}\).}
\label{fig:PC_3,n}
\end{figure}
By Theorem \ref{thm:pckn}, we have \(\#\pc_{3,n} = 5^n\) and \[E(\pc_{3,n},x) = \frac{(x^5+3x^4+x^3)^{n}}{x^n} = x^{2n}(x^2+3x+1)^n\, .\] 
The sequence formed by these polynomial coefficients (arranged in descending powers of \(x\)) is the sequence \seqnum{A272866}, a triangle made up of Gegenbauer polynomial values, specifically that of \(C_k^{(-n)}\bigl(- \frac{3}{2}\bigr)\) for row \(n\). The correspondence follows from the generating function definition of the Gegenbauer polynomials \cite{mcbride2012obtaining}, which is
\[ (1-2 x t+t^2)^{-\nu} = \sum_{k=0}^\infty C_k^{(\nu)}(x)\,  t^k \, .\]

Now let us consider fixing \(n\), the number of pendants. The first case is when \(n=1\), \(\pc_{k,1}\). These are cycles with one single pendant. We find \(\#\pc_{k,1} = F_{k+2}\) and \(E(\pc_{k,1},x)= \frac{E(P_{k+3},x)}{x}\). This is again an uninteresting case since we obtain the same edge cover numbers and edge cover polynomial coefficients as path graphs.

If we consider two evenly spaced pendants, \(n=2\), things become more interesting. The first few cases of these graphs are shown in Figure~\ref{fig:PC_k,2}.
\begin{figure}[H]
\centering
\begin{tikzpicture}[style = thick, scale=0.5]
    \foreach \x in {90,180,270,0}
    \filldraw (\x:2cm) circle (2pt);
    \foreach \x in {90,270}
    \filldraw (\x:3.5cm) circle (2pt);
\draw (90:2cm)--(180:2cm)--(270:2cm)--(0:2cm)--cycle;
\draw(90:2cm)--(90:3.5cm)(270:2cm)--(270:3.5cm);
\end{tikzpicture}\hspace{1.5cm}
\begin{tikzpicture}[style = thick, scale=0.5]
    \foreach \x in {90,150,210,270,330,30}
    \filldraw (\x:2cm) circle (2pt);
    \foreach \x in {90,270}
    \filldraw (\x:3.5cm) circle (2pt);
\draw (90:2cm)--(150:2cm)--(210:2cm)--(270:2cm)--(330:2cm)--(30:2cm)--cycle;
\draw(90:2cm)--(90:3.5cm)(270:2cm)--(270:3.5cm);
\end{tikzpicture}\hspace{1.5cm}
\begin{tikzpicture}[style = thick, scale=0.5]
    \foreach \x in {90,135,180,225,270,315,0,45}
    \filldraw (\x:2cm) circle (2pt);
    \foreach \x in {90,270}
    \filldraw (\x:3.5cm) circle (2pt);
\draw (90:2cm)--(135:2cm)--(180:2cm)--(225:2cm)--(270:2cm)--(315:2cm)--(0:2cm)--(45:2cm)--cycle;
\draw(90:2cm)--(90:3.5cm)(270:2cm)--(270:3.5cm);
\end{tikzpicture}
\caption{From left to right, \(\pc_{2,2}, \pc_{3,2}\), and \(\pc_{4,2}\).}
\label{fig:PC_k,2}
\end{figure}
We obtain \(\#\pc_{k,2} = (F_{k+2})^{2} \) and 
the edge cover polynomials satisfy 
\[E(\pc_{k,2},x)= \frac{E(P_{k+3},x)^{2}}{x^2}\,.\]
The triangle formed by these coefficients (arranged in descending powers of \(x\)) matches the sequence \seqnum{A123521} (starting at the row \(n=3\)), which counts the tilings of a \(2 \times n\) grid with some pieces being horizontal domino tiles and the remaining pieces being square tiles. Since the dominoes are allowed to be only horizontal, the top row and bottom row act independently of each other. We can show a direct correspondence between these tilings and the edge covers of \(\pc_{k,2}\). Having two pendants \(k\) apart from each other allows each side of the cycle to turn into a path \(P_{k+3}\) behaving independently. For each side, an edge cover of the path corresponds to tiling the \(1\times (k+1)\) board with dominoes and squares in the following way. For each of the \(k+1\) non-pendant vertices of \(P_{k+3}\), we place a square if two edges on both sides cover that vertex and place a domino if only one edge covers it. Considering both sides of the cycle together, we obtain a \(2\times (k+1)\) board to cover. Missing an edge in this edge cover means we have a corresponding domino in the tiling. Therefore, an edge cover of \(\pc_{k,2}\) with \(j\) missing edges corresponds to a tiling of \(2\times (k+1)\) with \(j\) dominoes total.

The first few cases of \(\pc_{k,3}\) are shown in Figure~\ref{fig:PC_k,3}.
\begin{figure}[H]
\centering
\begin{tikzpicture}[style = thick, scale=0.5]
    \foreach \x in {90,210,330}
    \filldraw (\x:2cm) circle (2pt);
    \foreach \x in {90,210,330}
    \filldraw (\x:3.5cm) circle (2pt);
\draw (90:2cm)--(210:2cm)--(330:2cm)--cycle;
\draw(90:2cm)--(90:3.5cm)(210:2cm)--(210:3.5cm)(330:2cm)--(330:3.5cm);
\end{tikzpicture}\hspace{1.5cm}
\begin{tikzpicture}[style = thick, scale=0.5]
    \foreach \x in {90,150,210,270,330,30}
    \filldraw (\x:2cm) circle (2pt);
    \foreach \x in {90,210,330}
    \filldraw (\x:3.5cm) circle (2pt);
\draw (90:2cm)--(150:2cm)--(210:2cm)--(270:2cm)--(330:2cm)--(30:2cm)--cycle;
\draw(90:2cm)--(90:3.5cm)((210:2cm)--(210:3.5cm)(330:2cm)--(330:3.5cm);
\end{tikzpicture}\hspace{1.5cm}
\begin{tikzpicture}[style = thick, scale=0.5]
    \foreach \x in {90,130,170,210,250,290,330,10,50}
    \filldraw (\x:2cm) circle (2pt);
    \foreach \x in {90,210,330}
    \filldraw (\x:3.5cm) circle (2pt);
\draw (90:2cm)--(130:2cm)--(170:2cm)--(210:2cm)--(250:2cm)--(290:2cm)--(330:2cm)--(10:2cm)--(50:2cm)--cycle;
\draw(90:2cm)--(90:3.5cm)((210:2cm)--(210:3.5cm)(330:2cm)--(330:3.5cm);
\end{tikzpicture}
\caption{From left to right, \(\pc_{1,3}, \pc_{2,3}\), and \(\pc_{3,3}\).}
\label{fig:PC_k,3}
\end{figure}
We have \(\#\pc_{k,3} = (F_{k+2})^{3} \), 
which is the sequence \seqnum{A056570}. The edge cover polynomials satisfy 
\[E(\pc_{k,3},x)= \frac{E(P_{k+3},x)^{3}}{x^3}\, ,\]
which form the triangle of coefficients in Table~\ref{tab:PC_k,3}.
\begin{table}[H]
\centering
\begin{tabular}{c|*{10}{p{1.5em}}}
$k$ $\backslash$ $i$&amp;\mbox{}\hfill0&amp;\mbox{}\hfill1&amp;\mbox{}\hfill2&amp;\mbox{}\hfill3&amp;\mbox{}\hfill4&amp;\mbox{}\hfill5&amp;\mbox{}\hfill6&amp;\mbox{}\hfill7&amp;\mbox{}\hfill8&amp;\mbox{}\hfill9\\\hline
 1~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill  3 &amp;\mbox{}\hfill  3 &amp;\mbox{}\hfill  1 \\
 2~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   6&amp;\mbox{}\hfill 12&amp;\mbox{}\hfill 8\\
 3~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   9&amp;\mbox{}\hfill 30&amp;\mbox{}\hfill 45&amp;\mbox{}\hfill 30&amp;\mbox{}\hfill 9&amp;\mbox{}\hfill 1\\
 4~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   12&amp;\mbox{}\hfill 57&amp;\mbox{}\hfill 136&amp;\mbox{}\hfill 171&amp;\mbox{}\hfill 108&amp;\mbox{}\hfill 27\\
 5~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill 15&amp;\mbox{}\hfill 93&amp;\mbox{}\hfill 308&amp;\mbox{}\hfill 588&amp;\mbox{}\hfill 651&amp;\mbox{}\hfill 399&amp;\mbox{}\hfill 123&amp;\mbox{}\hfill 18&amp;\mbox{}\hfill 1\\
\end{tabular}
\caption{Coefficients of the edge cover polynomials of \(\pc_{k,3}\).}
\label{tab:PC_k,3}
\end{table}
In Table~\ref{tab:PC_k,3}, the entry in row \(k\) and column \(i\) represents the number of edge covers of \(\pc_{k,3}\) missing \(i\) edges from the total. In other words, the coefficients of the edge cover polynomials are arranged in descending powers of \(x\). 

\section{Spider graphs}
A \emph{spider graph} is a tree with one vertex \(v\) with \(\deg v \geq 3\) and the rest of the vertices with degree at most 2. Therefore, the vertex \(v\) is the center vertex, and all other vertices are on paths that start from vertex \(v\). We refer to these paths as \emph{branches}. We denote the non-center vertices by \(v_{ij}\), where \(i\) is the branch number and \(j\) is the vertex number on that branch, with \(j=1\) being the closest to \(v\) and increasing outward. Let \(S_{n_1,n_2,\ldots,n_{k}}\) denote a spider graph with \(k\) branches where the \(i\)-th branch has \(n_i\) vertices (not including \(v\)), shown in Figure~\ref{fig:spider_def}. 
\begin{figure}[htb]
\centering
\begin{tikzpicture}[scale=1.4]

\filldraw (0,0) circle (1.5pt);
\foreach \x in {54,126,198,270,342}
\filldraw (\x:5mm) circle (1.5pt);

\foreach \x in {54,126,198,270,342}
\draw (0,0)--(\x:10mm);

\foreach \x in {54,126,198,270,342}
\draw[dashed] (\x:10mm)--(\x:15mm);

\foreach \x in {54,126,198,270}
\draw (\x:15mm)--(\x:20mm);

\filldraw (126:25mm) circle (1.5pt);
\draw (126:15mm)--(126:25mm);

\foreach \x in {54,126,198,270,342}
\filldraw (\x:10mm) circle (1.5pt);

\foreach \x in {54,126,198,270,342}
\filldraw (\x:15mm) circle (1.5pt);

\foreach \x in {54,126,198,270}
\filldraw (\x:20mm) circle (1.5pt);

\draw(0,0) node[anchor=south]{\small\(v\)};
\draw(54:20mm) node[anchor=south]{\small\(v_{k,n_{k}}\)};
\draw(65:5mm) node[anchor=south]{\small\(v_{k,1}\)};
\draw(126:25mm) node[anchor=south]{\small\(v_{1,n_{1}}\)};
\draw(165:6mm) node[anchor=south]{\small\(v_{1,1}\)};
\draw(342:15mm) node[anchor=south west]{\small\(v_{k-1, n_{k-1}}\)};
\draw(338:3.5mm) node[anchor=south west]{\small\(v_{k-1,1}\)};
\end{tikzpicture}
\caption{A spider graph $S_{n_1, n_2, \ldots, n_k}$.}
\label{fig:spider_def} 
\end{figure}

\begin{theorem} \label{thm:spider} Given a spider graph \(S_{n_1,n_2,\ldots,n_{k}}\) , we have
\[\#S_{n_1,n_2,\ldots,n_{k}} = \prod_{i=1}^k F_{n_{i}+1} - \prod_{i=1}^k F_{n_{i}-1} \]
and
\[E(S_{n_1,n_2,\ldots,n_{k}}, x) = E(P_{n_k},x) E(S_{n_1,n_2,\ldots,n_{k-1}}, x) + \frac{1}{x^{k-1}}E(P_{1+n_k},x) \prod_{i=1}^{k-1} E(P_{2+n_i},x) \,.\]
\end{theorem}
\begin{proof}
We prove the first claim by induction on \(k\), the number of branches. First, note that for \(k=1\), \(S_{n_1}=P_{n_1+1}\). This means that \(\#S_{n_1} = F_{n_1}=F_{n_1+1}-F_{n_1-1}\). Therefore, the claim is true for \(k = 1\).

Consider now a spider with \(k\) branches. Let \(e=vv_{k,1}\) be the edge connecting the last branch to the center. We count the edge covers of \(\#S_{n_1,n_2,\ldots,n_{k}}\) using two disjoint cases: those that include \(e\) and those that do not, as in Figure~\ref{fig:spider_cases}.

\begin{figure}[H]
\centering
\begin{subfigure}{.49\linewidth}
\centering
\begin{tikzpicture}[scale=1.4]
\filldraw (0,0) circle (1.5pt);
\foreach \x in {54,126,198,270,342}
\filldraw (\x:5mm) circle (1.5pt);

\foreach \x in {126,198,270,342}
\draw (0,0)--(\x:10mm);
\draw(54:5mm)--(54:10mm);

\foreach \x in {54,126,198,270,342}
\draw[dashed] (\x:10mm)--(\x:15mm);

\foreach \x in {54,126,198,270}
\draw (\x:15mm)--(\x:20mm);

\filldraw (126:25mm) circle (1.5pt);
\draw (126:15mm)--(126:25mm);

\foreach \x in {54,126,198,270,342}
\filldraw (\x:10mm) circle (1.5pt);

\foreach \x in {54,126,198,270,342}
\filldraw (\x:15mm) circle (1.5pt);

\foreach \x in {54,126,198,270}
\filldraw (\x:20mm) circle (1.5pt);
\draw(54:20mm) node[anchor=south]{\small\(v_{k,n_{k}}\)};
\draw(126:25mm) node[anchor=south]{\small\(v_{1,n_{1}}\)};
\draw(342:15mm) node[anchor=south west]{\small\(v_{k-1, n_{k-1}}\)};
\end{tikzpicture}
\caption{\(S_{n_1,n_2,\ldots,n_k}\) without \(e\).}
\end{subfigure}
\begin{subfigure}{.49\linewidth}
\centering
\begin{tikzpicture}[scale=1.4]
\filldraw (0,0) circle (1.5pt);
\foreach \x in {54,126,198,270,342}
\filldraw (\x:5mm) circle (1.5pt);
\foreach \x in {54,126,198,270,342}
\draw (0,0)--(\x:10mm);
\draw [red](0,0)--(54:5mm);
\foreach \x in {54,126,198,270,342}
\draw[dashed] (\x:10mm)--(\x:15mm);
\foreach \x in {54,126,198,270}
\draw (\x:15mm)--(\x:20mm);
\filldraw (126:25mm) circle (1.5pt);
\draw (126:15mm)--(126:25mm);
\foreach \x in {54,126,198,270,342}
\filldraw (\x:10mm) circle (1.5pt);
\foreach \x in {54,126,198,270,342}
\filldraw (\x:15mm) circle (1.5pt);
\foreach \x in {54,126,198,270}
\filldraw (\x:20mm) circle (1.5pt);
\draw(0,.05) node[anchor= east]{\tiny\(v\)};
\draw(54:20mm) node[anchor=south]{\small\(v_{k,n_{k}}\)};
\draw(35:2.5mm) node[anchor=south east][red]{{\tiny \(e\)}};
\end{tikzpicture}
\caption{\(S_{n_1,n_2,\ldots,n_k}\) with \(e\).}
\end{subfigure}
\caption{Two cases of \(S_{n_1,n_2,\ldots,n_{k}}\) edge covers, with or without \(e\).}
\label{fig:spider_cases}
\end{figure}
The edge covers without \(e\) are the same as those of two disconnected graphs, \(P_{n_{k}}\) and the spider graph \(S_{n_1,n_2,\ldots,n_{k-1}}\). This gives us 
\( \#P_{n_{k}} \cdot \#S_{n_1,n_2,\ldots,n_{k-1}}\) edge covers.

To find the number of edge covers with \(e\), we first use the 2-sum lemma. We let the last branch be \(G_1\), one of the graphs in the 2-sum, and the edge connecting that branch to the center vertex $v$ be the identified edge in the 2-sum. Then, the spider \(S_{n_1,n_2,\ldots,n_{k-1}}\) with one pendant edge at the center vertex is \(G_2\), and the pendant edge is the identified edge in the 2-sum. By the 2-sum lemma, we find that the set of edge covers with \(e\) is in bijection with the edge covers of the disconnected graph consisting of \(P_{1+n_{k}}\), a \(P_2\), \(S_{n_1,n_2,\ldots,n_{k-1}}\) with a pendant at the center vertex, and another \(P_2\). We then apply the pendant lemma to this smaller spider graph with a pendant and split it into \(k-1\) paths. This gives 
\[ \#(S_{n_1,n_2,\ldots,n_{k}}; e)=\#P_{1+n_{k}} \cdot \# P_2 \cdot {\displaystyle \prod_{i=1}^{k-1} \#P_{2+n_{i}}} \cdot \# P_2 \,. \]

Adding the two cases and using \(\#P_n=F_{n-1}\), we have 
\[\#S_{n_1,n_2,\ldots,n_{k}} = F_{n_{k}-1} \cdot \#S_{n_1,n_2,\ldots,n_{k-1}} + F_{n_{k}} \cdot {\displaystyle \prod_{i=1}^{k-1} F_{n_{i}+1}} \,.\]
If we substitute the inductive hypothesis into the above expression and simplify, we get
\begin{align*}
\#S_{n_1,n_2,\ldots,n_{k}} &amp;= F_{n_{k}-1} \biggl( \prod_{i=1}^{k-1} F_{n_i+1} - \prod_{i=1}^{k-1} F_{n_i-1} \biggr) + F_{n_{k}} \cdot \prod_{i=1}^{k-1} F_{n_i+1}\\
&amp;= \bigl(F_{n_{k}-1} + F_{n_{k}} \bigr) \prod_{i=1}^{k-1} F_{n_{i}+1} - \prod_{i=1}^{k} F_{n_i-1} \\
&amp;= \prod_{i=1}^{k} F_{n_i+1} - \prod_{i=1}^{k} F_{n_i-1} \,,
\end{align*}
which is the claim. We can also think of this result heuristically as creating an edge cover of the spider by joining edge covers of the branches where the edge to the center vertex may or may not be there. These branch edge covers are in one-to-one correspondence with the edge covers of \(P_{2+n_i}\). Therefore, all these multiplied together gives us \(\displaystyle \prod_{i=1}^k F_{n_i+1}\) covers. We then remove the cases where each of the branches was missing the edge to the center vertex, which corresponds to each edge cover of the branch corresponding to one smaller path. Hence, we obtain a total of \(\displaystyle \prod_{i=1}^k F_{n_i-1}\) covers to exclude. 

Using the same cases, if we apply the 2-sum lemma and pendant lemma corollaries for the edge cover polynomials, specifically Corollaries~\ref{cor:2sum_poly} and \ref{cor:pendant_poly}, we obtain the edge cover polynomial recurrence relation given in the theorem statement.
\end{proof}

\subsection{Spider graphs with equal-length branches}

We obtain a particular case of the spider graphs when all branches are equal in length. We let \(S_{n^k}\) denote such a spider graph, where \(k\) is the number of branches and \(n\) is the number of vertices on each branch (except the center vertex). In this case, we have the following result:

\begin{theorem} Given a spider graph with \(k\geq 1\) branches each of length \(n\geq 1\), we have
\[\#S_{n^{k}} = F_{n+1}^{k}-F_{n-1}^{k} \, \text{ and } \, E(S_{n^{k}},x) = E(P_{n+1},x) \sum _{i=0}^{k-1} \frac{E(P_n,x)^{k-1-i}E(P_{n+2},x)^i}{x^i} \, .\]
\end{theorem}

\begin{proof} By Theorem~\ref{thm:spider}, the first claim follows directly, and we have 
\begin{equation}
E(S_{n^{k}},x) = E(P_{n},x) \cdot E(S_{n^{k-1}},x) + \frac{E(P_{n+1},x) \cdot E(P_{n+2},x)^{k-1}}{x^{k-1}} \,.
\label{eq:spider}
\end{equation}

For \(k=1\), we have \(S_{n^1}=P_{n+1}\), and the edge cover polynomial expression in the second claim holds in this case.

More generally, if \(E(S_{n^k}, x)\) is as claimed, then again, by equation \eqref{eq:spider}, 
\begin{align*}
E(S_{n^{k+1}},x) &amp;= E(P_n,x) E(P_{n+1},x) \sum _{i=0}^{k-1} \frac{E(P_n,x)^{k-1-i}E(P_{n+2},x)^i}{x^i} + \frac{E(P_{n+1},x) \cdot E(P_{n+2},x)^k}{x^k}\\
&amp;= E(P_{n+1},x) \sum _{i=0}^k \frac{E(P_n,x)^{k-i}E(P_{n+2},x)^i}{x^i} \, .
\end{align*}
Therefore, the claim holds for all \(k\).
\end{proof}

An even tidier expression for the edge cover polynomials of the spider graphs can be obtained using Theorem~\ref{thm:general}\ref{thm:generaljoin}. 

\begin{theorem} Given a spider graph with \(k\geq 1\) branches each of length \(n\geq 1\), we have
\[E(S_{n^{k}},x) = (E(P_{n+1},x)+E(P_{n},x))^{k}-E(P_{n},x)^{k} \, .\]
\end{theorem}

\begin{proof}
Since \(S_{n^1}=P_{n+1}\), we have 
\[E(S_{n^{1}},x) = (E(P_{n+1},x)+E(P_{n},x))^{1}-E(P_{n},x)^{1} \,.\]

Now assume the claim is true for \(k\). Recall that \(G_1\cdot uv\cdot G_2\) is formed by combining the graphs \(G_1\) and \(G_2\) by identifying the vertex \(u \in G_1\) with the vertex \(v\in G_2\). Theorem~\ref{thm:general}\ref{thm:generaljoin} provides a formula for the edge cover polynomial of \(G = G_1\cdot uv\cdot G_2\) in terms of those of \(G_1, G_2\), and their subgraphs. Spider graph \(S_{n^{k+1}}\) is \(P_{n+1}\cdot uv\cdot S_{n^k}\), where \(u\) is a pendant of \(P_{n+1}\) and \(v\) is the center of \(S_{n^k}\). By applying Theorem~\ref{thm:general}\ref{thm:generaljoin}, we obtain
\[E(S_{n^{k+1}},x)=E(P_{n+1},x)E(S_{n^{k}},x)+E(P_{n+1}-u,x)E(S_{n^k},x)+E(P_{n+1},x)E(S_{n^k}-v, x)\,.\]
Removing the center vertex in a spider graph \(S_{n^k}\) splits it into \(k\) disconnected paths \(P_n\), and removing the pendant from \(P_{n+1}\) turns it into \(P_n\). Hence, we find
\begin{align*}
E(S_{n^{k+1}},x)&amp;=E(P_{n+1},x)E(S_{n^{k}},x)+E(P_{n},x)E(S_{n^{k}},x)+E(P_{n+1},x)E(P_{n},x)^{k}\\
&amp;=(E(P_{n+1},x)+E(P_n,x))E(S_{n^{k}},x)+E(P_{n+1},x)E(P_{n},x)^k \,.
\end{align*}
Using the assumption about \(E(S_{n^{k}},x)\), we then have
\begin{align*}
E(S_{n^{k+1}},x)&amp;=(E(P_{n+1},x)+E(P_n,x))((E(P_{n+1},x)+E(P_{n},x))^{k}-E(P_{n},x)^{k})\\
&amp;\qquad +E(P_{n+1},x)E(P_{n},x)^k\\
&amp;=(E(P_{n+1},x)+E(P_{n},x))^{k+1}-E(P_{n},x)^{k+1} \,.
\end{align*}
Therefore, the claim holds for all \(k\). Note that if we express \(E(S_{n^k}, x)\) in expanded form in terms of powers of \(E(P_{n+1},x)\) and \(E(P_n,x)\), then the coefficients will form the beheaded Pascal's triangle \seqnum{A074909} since they will be the same as the coefficients of \((x+y)^k-y^k\). The beheaded Pascal's triangle omits the last 1 in each row of Pascal's triangle, which results from subtracting 1 from \((x+1)^k\).
\end{proof}

\subsubsection{Spider graph sequences}

In these spider graphs with branches of equal length, we generate sequences if we further fix \(n\) or \(k\). Let us first consider fixing \(k\), the number of branches. The cases \(k=1, 2\) are boring since these spiders are path graphs. So let \(k=3\). By Theorem \ref{thm:spider}, we have \(\#S_{n^{3}} = (F_{n+1})^{3}-(F_{n-1})^{3}\), which is the sequence \seqnum{A350473}. The edge cover polynomials are
\[E(S_{n^{3}},x) = (E(P_{n+1},x)+E(P_{n},x))^{3}-E(P_{n},x)^{3} \, .\]
These edge cover polynomials produce the triangle of numbers given in Table~\ref{tab:3_branch_spider}. In this table, row \(n\) corresponds to the coefficients of the edge cover polynomial of \(S_n^3\) arranged in descending powers of \(x\). 
\begin{table}[H]
\centering
\begin{tabular}{c|*{7}{p{1.5em}}}
$n$ $\backslash$ $i$&amp;\mbox{}\hfill0&amp;\mbox{}\hfill1&amp;\mbox{}\hfill2&amp;\mbox{}\hfill3&amp;\mbox{}\hfill4&amp;\mbox{}\hfill5&amp;\mbox{}\hfill6\\\hline
 1~~&amp;\mbox{}\hfill  1\\
 2~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   3&amp;\mbox{}\hfill 3\\
 3~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   6&amp;\mbox{}\hfill 12&amp;\mbox{}\hfill 7\\
 4~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   9&amp;\mbox{}\hfill 30&amp;\mbox{}\hfill 44&amp;\mbox{}\hfill 27&amp;\mbox{}\hfill 6\\
 5~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill  12&amp;\mbox{}\hfill 57&amp;\mbox{}\hfill 135&amp;\mbox{}\hfill 165&amp;\mbox{}\hfill 96&amp;\mbox{}\hfill 19\\
\end{tabular}
\caption{Coefficients of \(E(S_{n^3},x)\).}
\label{tab:3_branch_spider}
\end{table}

Now let \(k=4\). The total number of edge covers of \(S_{n^{4}}\) is \(\#S_{n^{4}} = (F_{n+1})^{4}-(F_{n-1})^{4}\), generating the sequence \seqnum{A358917}, which starts with
\[ 1,15,80,609,4015,27936,190385,1307775, \ldots \]
The edge cover polynomials of \(S_{n^{4}}\) are
\[E(S_{n^{4}},x) = (E(P_{n+1},x)+E(P_{n},x))^{4}-E(P_{n},x)^{4}\, ,\]
which generate the triangle in Table~\ref{tab:4_branch_spider}, again in descending powers of \(x\).
\begin{table}[H]
\centering
\begin{tabular}{c|*{10}{p{2em}}}
$n$ $\backslash$ $i$&amp;\mbox{}\hfill0&amp;\mbox{}\hfill1&amp;\mbox{}\hfill2&amp;\mbox{}\hfill3&amp;\mbox{}\hfill4&amp;\mbox{}\hfill5&amp;\mbox{}\hfill6&amp;\mbox{}\hfill7&amp;\mbox{}\hfill8&amp;\mbox{}\hfill9\\\hline
 1~~&amp;\mbox{}\hfill  1\\
 2~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   4&amp;\mbox{}\hfill 6&amp;\mbox{}\hfill 4\\
 3~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   8&amp;\mbox{}\hfill 24&amp;\mbox{}\hfill 32&amp;\mbox{}\hfill 15\\
 4~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   12&amp;\mbox{}\hfill 58&amp;\mbox{}\hfill 144&amp;\mbox{}\hfill 194&amp;\mbox{}\hfill 140&amp;\mbox{}\hfill 52&amp;\mbox{}\hfill 8\\
 5~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill 16&amp;\mbox{}\hfill 108&amp;\mbox{}\hfill 400&amp;\mbox{}\hfill 885&amp;\mbox{}\hfill 1192&amp;\mbox{}\hfill 948&amp;\mbox{}\hfill 400&amp;\mbox{}\hfill 68\\
\end{tabular}
\caption{Coefficients of \(E(S_{n^4},x)\).}
\label{tab:4_branch_spider}
\end{table}

For \(k=5\), we have \(\#S_{n^{5}} = (F_{n+1})^{5}-(F_{n-1})^{5}\), generating the sequence \seqnum{A358934}, which starts with
\[  1,31,242,3093,32525,368168,4051333,499200274, \ldots\]
The edge cover polynomials are
\[E(S_{n^{5}},x) = (E(P_{n+1},x)+E(P_{n},x))^{5}-E(P_{n},x)^{5}\, ,\]
generating the triangle of numbers in Table~\ref{tab:5_branch_spider}.
\begin{table}[H]
\centering
\begin{tabular}{c|*{11}{p{2em}}}
$n$ $\backslash$ $i$&amp;\mbox{}\hfill0&amp;\mbox{}\hfill1&amp;\mbox{}\hfill2&amp;\mbox{}\hfill3&amp;\mbox{}\hfill4&amp;\mbox{}\hfill5&amp;\mbox{}\hfill6&amp;\mbox{}\hfill7&amp;\mbox{}\hfill8&amp;\mbox{}\hfill9&amp;\mbox{}\hfill10\\\hline
 1~~&amp;\mbox{}\hfill  1\\
 2~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   5&amp;\mbox{}\hfill 10&amp;\mbox{}\hfill 10&amp;\mbox{}\hfill 5\\
 3~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   10&amp;\mbox{}\hfill 40&amp;\mbox{}\hfill 80&amp;\mbox{}\hfill 80&amp;\mbox{}\hfill 31\\
 4~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   15&amp;\mbox{}\hfill 95&amp;\mbox{}\hfill 330&amp;\mbox{}\hfill 872&amp;\mbox{}\hfill 680&amp;\mbox{}\hfill 320&amp;\mbox{}\hfill 85&amp;\mbox{}\hfill 10\\
 5~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill 20&amp;\mbox{}\hfill 175&amp;\mbox{}\hfill 880&amp;\mbox{}\hfill 2810&amp;\mbox{}\hfill 5943&amp;\mbox{}\hfill 8420&amp;\mbox{}\hfill 7880&amp;\mbox{}\hfill 4645&amp;\mbox{}\hfill 1540&amp;\mbox{}\hfill 211\\
\end{tabular}
\caption{Coefficients of \(E(S_{n^5},x)\).}
\label{tab:5_branch_spider}
\end{table}

Instead of fixing \(k\) to generate a sequence, we can also fix \(n\) to create spider graphs with fixed branch lengths and an increasing number of branches. 

If \(n=1\), we obtain spider graphs \(S_{1^{k}}\), which are star graphs. These are uninteresting since \( \#S_{1^k} =1\) and \( E(S_{1^{k}},x) =x^k\).

Spider graphs \(S_{2^{k}}\) produce more interesting edge cover numbers than star graphs do. We have \( \#S_{2^k} = F_{3}^k-F_{1}^k=2^{k}-1 \), generating \seqnum{A000225}, and
\[E(S_{2^{k}},x) = (E(P_3,x)+E(P_2,x))^k-E(P_2,x)^k = (x^2+x)^k-x^k=x^k((x+1)^k-1)\,.\]
The triangle generated by the coefficients of these polynomials (arranged in descending powers of \(x\)) is \seqnum{A074909}, the beheaded Pascal's triangle. 
 
For \(n=3\), we have \(\#S_{3^k} = F_{4}^{k}-F_{2}^{k}=3^{k}-1\), generating \seqnum{A024023}, and 
\[ E(S_{3^{k}},x) = (E(P_4,x)+E(P_3,x))^k-E(P_3,x)^k = (x^3+2x^2)^k-x^{2k}=x^{2k}((x+2)^k-1)\,.\]
The coefficients of these edge cover polynomials, in descending powers of \(x\), form Table~\ref{tab:spider_3_length_legs}.
\begin{table}[H]\centering
\begin{tabular}{c|*{11}{p{2em}}}
$k$ $\backslash$ $i$&amp;\mbox{}\hfill0&amp;\mbox{}\hfill1&amp;\mbox{}\hfill2&amp;\mbox{}\hfill3&amp;\mbox{}\hfill4&amp;\mbox{}\hfill5\\\hline
 1~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill  1\\
 2~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   4&amp;\mbox{}\hfill 3\\
 3~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   6&amp;\mbox{}\hfill 12&amp;\mbox{}\hfill 7\\
 4~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill   8&amp;\mbox{}\hfill 24&amp;\mbox{}\hfill 32&amp;\mbox{}\hfill 15\\
 5~~&amp;\mbox{}\hfill  1&amp;\mbox{}\hfill 10&amp;\mbox{}\hfill 40&amp;\mbox{}\hfill 80&amp;\mbox{}\hfill 80&amp;\mbox{}\hfill 31\\
\end{tabular}
\caption{Coefficients of \(E(S_{3^k},x)\).}
\label{tab:spider_3_length_legs}
\end{table}

The edge cover numbers for \(n=4\) generate the sequence \seqnum{A005057}, and for \(n=5\) generate the sequence \seqnum{A190543}. Larger \(n\) values generate sequences not in OEIS.

\section{Acknowledgment}
We thank the Office of Undergraduate Research and Scholarship at Grand Valley State University for providing partial funding to support this work. In addition, we thank our research team members, Rachel Carpenter, Bradley Monarch, Joseph Mazor, and Jacob Ritsema, for their camaraderie and support throughout this research. We also thank Steven Schlicker for introducing us to the topic of edge covers and providing helpful feedback on an earlier draft of this paper. Lastly, we thank the anonymous reviewers who generously offered their time and invaluable feedback.


\begin{thebibliography}{1}

\bibitem{akbari2013edge}
Saieed Akbari and Mohammad~Reza Oboudi, On the edge cover polynomial of a
  graph, {\em European J. Combin.} {\bf 34} (2013), 297--321.

\bibitem{belkconnelly2007realizability}
Maria Belk and Robert Connelly, Realizability of graphs, {\em Discrete Comput.
  Geom.} {\bf 37} (2007), 125--137.

\bibitem{blackburn2009missing}
Chantel~C. Blackburn, Kristina Lund, Steven Schlicker, Patrick Sigmon, and
  Alexander Zupan, A missing prime configuration in the {H}ausdorff metric
  geometry, {\em J. Geom.} {\bf 92} (2009), 28--59.

\bibitem{csikvari2011roots}
P{\'e}ter Csikv{\'a}ri and Mohammad~Reza Oboudi, On the roots of edge cover
  polynomials of graphs, {\em European J. Combin.} {\bf 32} (2011), 1407--1416.

\bibitem{ita2010estimating}
Guillermo De~Ita, J.~Raymundo Marcial-Romero, and H{\'e}ctor~A. Montes-Venegas,
  Estimating the relevance on communication lines based on the number of edge
  covers, {\em Electron. Notes Discret. Math.} {\bf 36} (2010), 247--254.

\bibitem{honigs2013missing}
Katrina Honigs, Missing edge coverings of bipartite graphs and the geometry of
  the {H}ausdorff metric, {\em J. Geom.} {\bf 104} (2013), 107--125.

\bibitem{mcbride2012obtaining}
Elna~B. McBride, {\em Obtaining {G}enerating {F}unctions}, Springer
  Science \&amp; Business Media, 2012.

\bibitem{napier2018cross}
Shannon Napier and Liah Renaud, Cross configurations and their corresponding
  integer sequences.
\newblock Undergraduate honors thesis, Department of Mathematics, Grand Valley
  State University, 2018.

\bibitem{oeis}
{OEIS Foundation Inc.}, The {O}n-{L}ine {E}ncyclopedia of {I}nteger
  {S}equences, 2023.
\newblock Published electronically at \url{https://oeis.org}.

\end{thebibliography}
\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}: Primary  05C30; Secondary 11B83, 05C31.

\noindent \emph{Keywords:} edge cover, pendant, 2-sum, spider graph, caterpillar graph, cycle graph, Fibonacci number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences 
\seqnum{A000045},
\seqnum{A000225},
\seqnum{A003946},
\seqnum{A005057},
\seqnum{A011973},
\seqnum{A013609},
\seqnum{A024023},
\seqnum{A056570},
\seqnum{A066258},
\seqnum{A074909},
\seqnum{A123521},
\seqnum{A190543},
\seqnum{A272866},
\seqnum{A350473},
\seqnum{A358917}, and
\seqnum{A358934}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 26 2022; 
revised versions received December 31 2022; October 14 2023; November 12 2023.
Published in {\it Journal of Integer Sequences}, November 16 2023.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>