• AN INTRODUCTION TO STEINER POLYNOMIALS OF GRAPHS

Abstract

In this paper, we introduce a new concept of Steiner polynomial of a connected graph G. The Steiner polynomial of G is the polynomial S (G, x) = s (G, i) xi , where s(G, i) is the number of Steiner sets of G of size i and s (G) is the Steiner number of G. We obtain some properties of S (G, x) and its coefficients. Also, we compute the polynomials for paths.