On the number of perfect matchings of generalized theta graphs and the edge cover polynomials of friendship graphs


Mohammad Reza Oboudia




Let k ≥ 1 and q1, . . . , qk be some positive integers. The generalized theta graph Θq1 ,...,qk is the graph that is formed by taking a pair of vertices u and v, and joining them by k internally disjoint paths of lengths q1, . . . , qk. Let CΘC be the graph that obtained by attaching some cycles to at most two vertices with degree k of the generalized theta graph Θq1 ,...,qk . An edge covering of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. Let G be a simple graph with m edges. The edge cover polynomial of G is the polynomial E(G, x) = ∑m i=1 e(G, i)xi, where e(G, i) is the number of edge coverings of G of size i. Let t be a positive integer and Ft be the friendship (or Dutch windmill) graph with 2t + 1 vertices and 3t edges. In this paper we obtain the number of perfect matchings of CΘC graphs and then study the edge cover polynomial of friendship graphs. We show that the friendship graphs are determined by their edge cover polynomials. We find that all non-zero roots of the edge cover polynomial of friendship graphs are simple. Finally we prove that the edge cover polynomials of friendship graphs are unimodal