ON THE EDGE COVER POLYNOMIAL OF CERTAIN GRAPHS

Document Type : Original Manuscript

Authors

Department of Mathematics, Yazd University, 89195-741, Yazd, Iran.

Abstract

Let

G

be a simple graph of order

n

and size

m

. The edge covering of

G

is a set of edges such that every vertex of

G

is incident to at least one edge of the set. The edge cover polynomial of

G

is the polynomial

E (G, x) = s u m_{i = r h o (G)}^{m} e (G, i) x^{i}

, where

e (G, i)

is the number of edge coverings of

G

of size

i

, and

r h o (G)

is the edge covering number of

G

. In this paper we study the edge cover polynomials of cubic graphs of order

10

. We show that all cubic graphs of order

10

(especially the Petersen graph) are determined uniquely by their edge cover polynomials.

Keywords