# zbMATH — the first resource for mathematics

On the edge cover polynomial of a graph. (English) Zbl 1254.05077
Summary: Let $$G$$ be a simple graph of order $$n$$ and size $$m$$. 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.
In this paper we introduce a new graph polynomial. The edge cover polynomial of $$G$$ is the polynomial $$E(G,x)=\sum^m_{i=1} e(G,i) x^i$$, where $$e(G,i)$$ is the number of edge coverings of $$G$$ of size $$i$$. Let $$G$$ and $$H$$ be two graphs of order $$n$$ such that $$\delta(G) \geq \frac{n}{2}$$, where $$\delta (G)$$ is the minimum degree of $$G$$. If $$E(G,x)=E(H,x)$$, then we show that the degree sequence of $$G$$ and $$H$$ are the same. We determine all graphs $$G$$ for which $$E(G,x)=E(P_{n},x)$$, where $$P_{n}$$ is the path of order $$n$$.
We show that if $$\delta (G)\geq 3$$, then $$E(G,x)$$ has at least one non-real root. Finally, we characterize all graphs whose edge cover polynomials have exactly one or two distinct roots and moreover we prove that these roots are contained in the set $$\{ - 3, - 2, - 1,0\}$$.

##### MSC:
 05C31 Graph polynomials 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
##### Keywords:
edge covering of a graph; graph polynomial
Full Text: