Journal of Integer Sequences, Vol. 26 (2023), Article 23.9.4

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


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.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000045 A000225 A003946 A005057 A011973 A013609 A024023 A056570 A066258 A074909 A123521 A190543 A272866 A350473 A358917 A358934.)

Received 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