Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs

Feryal Alayont and Evan Henning Department of Mathematics Grand Valley State University Allendale, MI 49401 USA

        alayontf@gvsu.edu henninge@mail.gvsu.edu

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 On-Line Encyclopedia of Integer Sequences using these edge covers and provide new combinatorial interpretations of some known sequences.

1 Introduction

A (simple) graph G is an ordered pair (V, E) consisting of a finite set of vertices V (G) = {v_{1}, v_{2}, …, v_{n}} and a finite set of edges E(G) = {e_{1}, e_{2}, …, 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 degree of a vertex is the number of edges that are incident with that vertex, i.e., the number of edges that meet at that vertex. An isolated vertex has degree 0, and a pendant (vertex) has degree 1. An 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 1, 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{matrix}v_{1} \\ v_{2} \\ v_{3} \\ v_{4} \\ v_{5} \\ e_{1} \\ e_{2} \\ e_{3} \\ e_{4} \\ e_{5} \\ e_{6} \\ e_{7} \\ e_{8} \end{matrix}

Figure 1: A graph and two edge covers (red edges and black edges).

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 [3]. Honigs [6] 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 [5].

Let #G denote the total number of edge covers of G. It can be shown [6] 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 \underline{A000045}. By considering cases based on whether there is a fixed edge or not [6], one can also show that for cycle graphs C_{n} with n vertices #C_{n} = L_{n} for n ≥ 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) = ∑_{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 2. Hence, the edge cover polynomial of P_{6} is

E(P_{6}, x) = x^{3} + 3x^{4} + x^{5} .

More generally, we have [1]

E(P_{n}, x) = ∑_{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 \underline{A011973} in the On-Line Encyclopedia of Integer Sequences (OEIS) [9].

Figure 2: Edge covers of P_{6}.

This paper focuses on edge covers of path and cycle graphs with pendants and spider graphs. A 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 [9] and provide new combinatorial interpretations of some known sequences.

2 Some general properties of edge covers

Some known results about the total number of edge covers and edge cover polynomials are

Theorem 1.

(i) Given a graph G with connected components G_{1}, G_{2}, …, G_{k}, we have [1]

#G = ∏_{i=1}^{k} #G_{i} and E(G, x) = ∏_{i=1}^{k} E(G_{i}, x) .

(ii) Given a graph G with edge uv, we have

E(G, x) = (x + 1)E(G − uv, x) + x(E(G − u, x) + E(G − v, x) + E(G − {u, v}, x)),

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 [1, 6].

(iii) Given a graph G with a pendant vertex v whose neighbor is u, we have [1]

E(G, x) = xE(G − v, x) + xE(G − {u, v}, x) .

(iv) Suppose G = G_{1} · uv · G_{2} is formed by combining two graphs G_{1} and G_{2} by identifying the vertex u ∈ G_{1} with the vertex v ∈ G_{2}. Then [4]

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

We now prove two new results, the first of which is about 2-sums of graphs, a particular case of k-sums [2]. Given two graphs, G_{1} and G_{2}, and an edge from each graph, the 2-sum G_{1} ⊕_{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 3.

\begin{matrix}u \\ u \\ v \\ v \\ G_{1} \\ G_{2} \\ ⟶ \end{matrix}  \begin{matrix}u \\ v \\ G_{1} ⊕_{2} G_{2} \end{matrix}

Figure 3: The 2-sum of two graphs.

Lemma 2 (2-sum Lemma). Let G = G_{1} ⊕_{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} ∪ {uw_{1}, vw_{2}}) − uv and G′_{2} = (G_{2} ∪ {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}).

Proof. To clarify the definitions, Figure 4 shows how G′_{1} and G′_{2} would look like using the example of G = G_{1} ⊕_{2} G_{2} shown in Figure 3.

To prove the lemma, we define a map S → (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} 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}, …, e_{r}, e_{r+1}, …, e_{s}},

where e_{1}, …, e_{r} ∈ G_{1} and e_{r+1}, …, e_{s} ∈ G_{2}. Let S_{1} = {uw_{1}, vw_{2}, e_{1}, …, e_{r}} and S_{2} = {uy_{1}, vy_{2}, e_{r+1}, …, e_{s}}. We will show that each S_{i} is an edge cover of G′_{i}.

\begin{matrix}u \\ v \\ G_{1} ⊕_{2} G_{2} \\ ⟶ \end{matrix}  ^{w_{1} u u vvw_{2} y_{2} y_{1} G′_{1} G′_{2}}
Figure 4: An example of constructing G′_{1} and G′_{2} from G = G_{1} ⊕_{2} G_{2}.

If x ∈ G_{i} and x ≠ 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 → (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} and G′_{2}, respectively. Because uw_{1} and uw_{2} are both pendant edges in G′_{1}, 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}, …, e_{r}} for some e_{i} in G_{1}. Similarly, S_{2} = {uy_{1}, vy_{2}, e_{r+1}, …, e_{s}} for some e_{i} in G_{2}. Define

S = S_{1} ∪ S_{2} ∪ {uv} − {uw_{1}, vw_{2}, uy_{1}, vy_{2}} = {uv, e_{1}, …, e_{r}, e_{r+1}, …, 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.

A direct consequence of the 2-sum lemma is

Corollary 3. Let #(G; uv) denote the number of edge covers of G that include the edge uv. Suppose G = G_{1} ⊕_{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} · #G′_{2} .

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:

Corollary 4. Suppose G = G_{1} ⊕_{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}) · E(G′_{2})}{x^{3}} .

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

Lemma 5 (Pendant Lemma). Let G be a graph with a pendant vertex v. Let u be the neighbor of v, and w_{i}, 1 ≤ i ≤ 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}) ∪ {w_{1}u_{1}, u_{1}v_{1}, w_{2}u_{2}, u_{2}v_{2}, …, w_{k}u_{k}, u_{k}v_{k}},

where the u_{i}, v_{i} are added new vertices to G.

Proof. A representative example of the G and G′ pair is shown in Figure 5.

\begin{matrix}v \\ u \\ w_{2} \\ w_{3} \\ w_{4} \\ w_{1} \\ G \end{matrix}  →  ^{v_{3} u_{3} w_{1} w_{2} w_{3} w_{4} v_{2} u_{2} v_{1} u_{1} v_{4} u_{4} G′}

Figure 5: An example of G′ construction.

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}, …, e_{r}, uv} of G corresponds to the edge cover {e_{1}, e_{2}, …, e_{r}, u_{1}v_{1}, u_{2}v_{2}, …, u_{k}v_{k}} of G′. In this correspondence, by abuse of notation, for an edge e_{i} = w_{j}u that might be in the edge cover of G, we still use e_{i} to represent the corresponding edge w_{j}u_{j} in G′.

Corollary 6. 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) .

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.

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

3.1 Caterpillars

A 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 central stalk of the caterpillar.

Theorem 7. A caterpillar graph G with central stalk P_{n} and k_{1}, k_{2}, …, k_{r} pendants at inner vertices (counting from one pendant vertex of P_{n}) located at vertices m_{1}, m_{2}, …, m_{r}, respectively, has a total of

#G = F_{m_{1}}F_{m_{2}−m_{1}+2} ⋯ 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}+···+k_{r}−2r}E(P_{m_{1}+1}, x)E(P_{n−m_{r}+2}, x) ∏_{i=2}^{r} E(P_{m_{i}−m_{i−1}+3}, x) .

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}, …, 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}+···+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 6.

\begin{matrix}1 \\ m_{1} \\ m_{2} \\ m_{3} \\ n \end{matrix}

Figure 6: A caterpillar graph with three pendants attached to the central stalk.

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

\begin{matrix}1 \\ m_{1} \\ m_{2} − m_{1} + 2 \\ m_{3} − m_{1} + 2 \\ n − m_{1} + 2 \end{matrix}

Figure 7: Caterpillar in Figure 6 with one pendant section separated.

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} · F_{m_{3}−m_{2}+2} · 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 6 since the degree of the pendant vertex is three. Thus, for r pendants, we have an extra x^{−r} factor.

We can generate number sequences out of caterpillars by considering evenly spaced pendants in caterpillars [8]. 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 \underline{A003946}, while n = 2 generates \underline{A066258} in OEIS [9].

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

Theorem 8. Suppose G is obtained by attaching pendants to a cycle graph C_{n} with vertices consecutively labeled 1, 2, …, n and k_{0}, k_{1}, k_{2}, …, k_{r} pendants attached to vertices (counting clockwise starting at 1) 1, m_{1}, m_{2}, …, m_{r}, respectively. Then G has a total of

#G = F_{m_{1}+1}F_{m_{2}−m_{1}+2} ⋯ 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}+···+k_{r}−2(r+1)}E(P_{m_{1}+2}, x)E(P_{n−m_{r}+4}, x) ∏_{i=2}^{r} E(P_{m_{i}−m_{i−1}+3}, x) .

Proof. A representative example labeled cycle with pendants is shown in Figure 8.

\begin{matrix}1 \\ 8 \\ 2 \\ 3 \\ 5 \\ 7 \\ m_{1} = 4 \\ m_{2} = 6 \end{matrix}

Figure 8: 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.

Let G be a cycle with n vertices with k_{0} pendants attached to vertex 1, k_{1} attached to m_{1}, …, 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}, …, m_{r} into a path P_{n+3} with pendants at locations m_{1} + 1, m_{2} + 1, …, m_{r} + 1. The example graph given in Figure 8 will turn into the caterpillar in Figure 9 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.

123 m_{1} = 4 5 m_{2} = 6 781′

Figure 9: The caterpillar obtained after applying the pendant lemma.

Once the graph becomes a caterpillar, we apply Theorem 7 on caterpillars to obtain the result.

3.2.1 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 8 in this case, we obtain the following theorem.

Theorem 9. Given a cycle PC_{k,n} with evenly spaced pendants, we have

# PC_{k,n} = (F_{k+2})^{n} and E(PC_{k,n}, x) = \frac{E(P_{k+3}, x)^{n}}{x^{n}} .

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 9, 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 10.

Figure 10: From left to right, PC_{2,2}, PC_{2,3}, and PC_{2,4}.

By Theorem 9, 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 \underline{A013609}, described as the sequence of coefficients of (1 + 2x)^{n}.

When k = 3, the first few graphs are shown in Figure 11.

Figure 11: From left to right, PC_{3,1}, PC_{3,2}, and PC_{3,3}.

By Theorem 9, 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 \underline{A272866}, a triangle made up of Gegenbauer polynomial values, specifically that of C_{k}^{(−n)}(−\frac{3}{2}) for row n. The correspondence follows from the generating function definition of the Gegenbauer polynomials [7], which is

(1 − 2xt + t^{2})^{−ν} = ∑_{k=0}^{∞} C_{k}^{(ν)}(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 12.

Figure 12: From left to right, PC_{2,2}, PC_{3,2}, and PC_{4,2}.

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 \underline{A123521} (starting at the row n = 3), which counts the tilings of a 2 × 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 × (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 × (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 × (k + 1) with j dominoes total.

The first few cases of PC_{k,3} are shown in Figure 13.

Figure 13: From left to right, PC_{1,3}, PC_{2,3}, and PC_{3,3}.

We have # PC_{k,3} = (F_{k+2})^{3}, which is the sequence \underline{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 1.

k \ i 0 1 2 3 4 5 6 7 8 9
1  1 3 3 1
2  1 6 12 8
3  1 9 30 45 30 9 1
4  1 12 57 136 171 108 27
5  1 15 93 308 588 651 399 123 18 1

Table 1: Coefficients of the edge cover polynomials of PC_{k,3}.

In Table 1, 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.

4 Spider graphs

A spider graph is a tree with one vertex v with deg v ≥ 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 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},...,n_{k}} denote a spider graph with k branches where the i-th branch has n_{i} vertices (not including v), shown in Figure 14.

Theorem 10. Given a spider graph S_{n_{1},n_{2},...,n_{k}} , we have

#S_{n_{1},n_{2},...,n_{k}} = ∏_{i=1}^{k} F_{n_{i}+1} − ∏_{i=1}^{k} F_{n_{i}−1}

\begin{matrix}v \\ v_{k,n_{k}} \\ v_{k,1} \\ v_{1,n_{1}} \\ v_{1,1} \\ v_{k−1,n_{k−1}} \\ v_{k−1,1} \end{matrix}

Figure 14: A spider graph S_{n_{1},n_{2},...,n_{k}}.

and

E(S_{n_{1},n_{2},...,n_{k}}, x) = E(P_{n_{k}}, x)E(S_{n_{1},n_{2},...,n_{k−1}}, x) + \frac{1}{x^{k−1}} E(P_{1+n_{k}}, x) ∏_{i=1}^{k−1} E(P_{2+n_{i}}, x) .

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},...,n_{k}} using two disjoint cases: those that include e and those that do not, as in Figure 15.

\begin{matrix}v_{k,n_{k}} \\ v_{1,n_{1}} \\ v_{k−1,n_{k−1}} \end{matrix}

(a) S_{n_{1},n_{2},...,n_{k}} without e.

v_{k,n_{k}}_{e}^{v} (b) S_{n_{1},n_{2},...,n_{k}} with e.

Figure 15: Two cases of S_{n_{1},n_{2},...,n_{k}} edge covers, with or without e.

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},...,n_{k−1}}. This gives us #P_{n_{k}} · #S_{n_{1},n_{2},...,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},...,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},...,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},...,n_{k}}; e) = #P_{1+n_{k}} · #P_{2} · ∏_{i=1}^{k−1} #P_{2+n_{i}} · #P_{2} .

Adding the two cases and using #P_{n} = F_{n−1}, we have

#S_{n_{1},n_{2},...,n_{k}} = F_{n_{k}−1} · #S_{n_{1},n_{2},...,n_{k−1}} + F_{n_{k}} · ∏_{i=1}^{k−1} F_{n_{i}+1} .

If we substitute the inductive hypothesis into the above expression and simplify, we get

#S_{n_{1},n_{2},...,n_{k}} = F_{n_{k}−1}(∏_{i=1}^{k−1} F_{n_{i}+1} − ∏_{i=1}^{k−1} F_{n_{i}−1}) + F_{n_{k}} · ∏_{i=1}^{k−1} F_{n_{i}+1}

= (F_{n_{k}−1} + F_{n_{k}}) ∏_{i=1}^{k−1} F_{n_{i}+1} − ∏_{i=1}^{k} F_{n_{i}−1}

= ∏_{i=1}^{k} F_{n_{i}+1} − ∏_{i=1}^{k} F_{n_{i}−1} ,

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 ∏_{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 ∏_{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 4 and 6, we obtain the edge cover polynomial recurrence relation given in the theorem statement.

4.1 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:

Theorem 11. Given a spider graph with k ≥ 1 branches each of length n ≥ 1, we have

#S_{n^{k}} = F_{n+1}^{k} − F_{n−1}^{k} and E(S_{n^{k}}, x) = E(P_{n+1}, x) ∑_{i=0}^{k−1} \frac{E(P_{n}, x)^{k−1−i}E(P_{n+2}, x)^{i}}{x^{i}} .

Proof. By Theorem 10, the first claim follows directly, and we have

E(S_{n^{k}}, x) = E(P_{n}, x) · E(S_{n^{k−1}}, x) + \frac{E(P_{n+1}, x) · E(P_{n+2}, x)^{k−1}}{x^{k−1}} .  (1)

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 (1),

E(S_{n^{k+1}}, x) = E(P_{n}, x)E(P_{n+1}, x) ∑_{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) · E(P_{n+2}, x)^{k}}{x^{k}}

= E(P_{n+1}, x) ∑_{i=0}^{k} \frac{E(P_{n}, x)^{k−i}E(P_{n+2}, x)^{i}}{x^{i}} .

Therefore, the claim holds for all k.

An even tidier expression for the edge cover polynomials of the spider graphs can be obtained using Theorem 1(iv).

Theorem 12. Given a spider graph with k ≥ 1 branches each of length n ≥ 1, we have

E(S_{n^{k}}, x) = (E(P_{n+1}, x) + E(P_{n}, x))^{k} − E(P_{n}, x)^{k} .

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} · uv · G_{2} is formed by combining the graphs G_{1} and G_{2} by identifying the vertex u ∈ G_{1} with the vertex v ∈ G_{2}. Theorem 1(iv) provides a formula for the edge cover polynomial of G = G_{1} · uv · G_{2} in terms of those of G_{1}, G_{2}, and their subgraphs. Spider graph S_{n^{k+1}} is P_{n+1} · uv · S_{n^{k}}, where u is a pendant of P_{n+1} and v is the center of S_{n^{k}}. By applying Theorem 1(iv), 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

E(S_{n^{k+1}}, x) = 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}
= (E(P_{n+1}, x) + E(P_{n}, x))E(S_{n^{k}}, x) + E(P_{n+1}, x)E(P_{n}, x)^{k} .

Using the assumption about E(S_{n^{k}}, x), we then have

E(S_{n^{k+1}}, x) = (E(P_{n+1}, x) + E(P_{n}, x))((E(P_{n+1}, x) + E(P_{n}, x))^{k} − E(P_{n}, x)^{k})
+ E(P_{n+1}, x)E(P_{n}, x)^{k}
= (E(P_{n+1}, x) + E(P_{n}, x))^{k+1} − E(P_{n}, x)^{k+1} .

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 \underline{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}.

4.1.1 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 10, we have #S_{n^{3}} = (F_{n+1})^{3} − (F_{n−1})^{3}, which is the sequence \underline{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 2. In this table, row n corresponds to the coefficients of the edge cover polynomial of S_{n}^{3} arranged in descending powers of x.

n \ i 0 1 2 3 4 5 6
1  1
2  1 3 3
3  1 6 12 7
4  1 9 30 44 27 6
5  1 12 57 135 165 96 19
Table 2: Coefficients of E(S_{n^{3}}, x).

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 \underline{A358917}, which starts with

1, 15, 80, 609, 4015, 27936, 190385, 1307775, …

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 3, again in descending powers of x.

n \ i  0  1  2  3  4  5  6  7  8  9
1  1
2  1  4  6  4
3  1  8 24 32 15
4  1 12 58 144 194 140 52  8
5  1 16 108 400 885 1192 948 400 68
Table 3: Coefficients of E(S_{n^{4}}, x).

For k = 5, we have #S_{n^{5}} = (F_{n+1})^{5} − (F_{n−1})^{5}, generating the sequence \underline{A358934}, which starts with

1, 31, 242, 3093, 32525, 368168, 4051333, 499200274, …

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

n \ i  0  1  2  3  4  5  6  7  8  9 10
1  1
2 1 5 10 10 5
3  1 10 40 80 80 31
4  1 15 95 330 872 680 320 85 10
5  1 20 175 880 2810 5943 8420 7880 4645 1540 211
Table 4: Coefficients of E(S_{n^{5}}, x).

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 \underline{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 \underline{A074909}, the beheaded Pascal’s triangle.

For n = 3, we have #S_{3^{k}} = F_{4}^{k} − F_{2}^{k} = 3^{k} − 1, generating \underline{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 5.

k \ i  0  1  2  3  4  5
1  1  1
2  1  4  3
3  1  6 12  7
4  1  8 24 32 15
5  1 10 40 80 80 31
Table 5: Coefficients of E(S_{3^{k}}, x).

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

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

References

[1] Saieed Akbari and Mohammad Reza Oboudi, On the edge cover polynomial of a graph, European J. Combin. 34 (2013), 297–321.

[2] Maria Belk and Robert Connelly, Realizability of graphs, Discrete Comput. Geom. 37 (2007), 125–137.

[3] Chantel C. Blackburn, Kristina Lund, Steven Schlicker, Patrick Sigmon, and Alexander Zupan, A missing prime configuration in the Hausdorff metric geometry, J. Geom. 92 (2009), 28–59.

[4] Péter Csikvári and Mohammad Reza Oboudi, On the roots of edge cover polynomials of graphs, European J. Combin. 32 (2011), 1407–1416.

[5] Guillermo De Ita, J. Raymundo Marcial-Romero, and Héctor A. Montes-Venegas, Estimating the relevance on communication lines based on the number of edge covers, Electron. Notes Discret. Math. 36 (2010), 247–254.

[6] Katrina Honigs, Missing edge coverings of bipartite graphs and the geometry of the Hausdorff metric, J. Geom. 104 (2013), 107–125.

[7] Elna B. McBride, Obtaining Generating Functions, Springer Science & Business Media, 2012.

[8] Shannon Napier and Liah Renaud, Cross configurations and their corresponding integer sequences. Undergraduate honors thesis, Department of Mathematics, Grand Valley State University, 2018.

[9] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2023. Published electronically at https://oeis.org.

2020 Mathematics Subject Classification: Primary 05C30; Secondary 11B83, 05C31. Keywords: edge cover, pendant, 2-sum, spider graph, caterpillar graph, cycle graph, Fibonacci number.

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

Received December 26 2022; revised versions received December 31 2022; October 14 2023; November 12 2023. Published in Journal of Integer Sequences, November 16 2023.

Return to Journal of Integer Sequences home page.