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

05C31 Graph polynomials
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI